numbers (version 0.8-5)

legendre_sym: Legendre and Jacobi Symbol

Description

Legendre and Jacobi Symbol for quadratic residues.

Usage

legendre_sym(a, p)
jacobi_sym(a, n)

Value

Returns 0, 1, or -1 if p divides a, a is a quadratic residue, or if not.

Arguments

a, n

integers.

p

prime number.

Details

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.

See Also

quadratic_residues

Examples

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

if (FALSE) {
# 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
  }

jacobi_sym(11, 12)                      # -1