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
·