Cryptography Reference
In-Depth Information
= x
p
x
q
x
n
·
Contrary to the Legendre symbol, the Jacobi symbol of x modulo n is not
only 1 if x
QR n ; it is 1 either if x
QR p and x
QR q or if x/
QR p and
x/
QR q . Among these two possibilities, only the first refers to the situation in
which x
QR n . Consequently, all quadratic residues have Jacobi symbol 1, but the
opposite is not necessarily true (as further addressed later).
More generally, let n
3 be odd with prime factorization n = p e 1
p e 2
...p e k
.
Then the Jacobi symbol n is defined as follows:
= x
p 1
e 1 x
p 2
e 2 ... x
p k
e k
x
n
Again, note that if n is prime, then the Jacobi symbol is just the Legendre
symbol. In any case, n is 0, 1, or
1,and n =0if and only if gcd ( x, n )
=1.
y (mod n ), then the equation n = n holds.
Similar to the Legendre symbol,
If x
1
n
=1 .
Furthermore,
=(
1
n
1) ( n− 1) / 2
and
2
n
=(
1) ( n 2 1) / 8 .
The Jacobi symbol is multiplicative in both the numerator and the de-
nominator:
xy
n
= x
n
y
n
·
Search WWH ::




Custom Search