Legendre and Jacobi Symbol
Legendre and Jacobi Symbol for quadratic residues.
legendre_sym(a, p) jacobi_sym(a, n)
a, n |
integers. |
p |
prime number. |
The Legendre Symbol (a/p), where p must be a prime number,
denotes whether a is a quadratic residue modulo p or not.
The Jacobi symbol (a/p) is the product of (a/p) of all prime
factors p on n.
Returns 0, 1, or -1 if p divides a, a is a quadratic
residue, or if not.
Lsym <- Vectorize(legendre_sym, 'a') # all quadratic residues of p = 17 qr17 <- which(Lsym(1:16, 17) == 1) # 1 2 4 8 9 13 15 16 sort(unique((1:16)^2 %% 17)) # the same ## Not run: # how about large numbers? p <- 1198112137 # isPrime(p) TRUE x <- 4652356 a <- mod(x^2, p) # 520595831 legendre_sym(a, p) # 1 legendre_sym(a+1, p) # -1 ## End(Not run) jacobi_sym(11, 12) # -1
Please choose more modern alternatives, such as Google Chrome or Mozilla Firefox.