Cryptography Reference
In-Depth Information
Remarks 2.7
1. If n is itself prime, then the Jacobi symbol n is just the Legendre symbol. Thus
the Jacobi symbol is a generalization of the Legendre symbol and, like the latter,
it clearly depends only on the congruence class of a modulo n .
2. The Jacobi symbol is multiplicative in both arguments, namely a n = n n
and mn = m n .
3. If a is a quadratic residue modulo n , then it is clear that a is also a quadratic
residue modulo p for every prime p that divides n , and hence it follows from the
definition that, in this case, n =
1. But what about the converse? If n is prime
we know that the converse is also true but suppose, for example that n
=
pq is
the product of two different odd primes. Then it may happen that p
=−
1
and q
1, in which case n =
1 but, clearly, a is not a quadratic residue
modulo n (as this would imply that it is a quadratic residue modulo p and also
=−
modulo q ). A concrete example is 15 = 3 5 = (
1
)(
1
) =
1 where, as
we have seen, 2 is a quadratic non-residue modulo 15.
∈ Z n | n =
J n
={
}
Exercise 2.43 Let
a
1
. Prove that if n is a square, then
= Z n and otherwise
Z n are in
J n
J n .
(Hint: If n is not a square then there exists a prime factor p of n such that the largest
power of p that divides n has an odd exponent. Use the Chinese remainder theorem to
find an element which is not a quadratic residue modulo p but is a quadratic residue
modulo all the remaining prime divisors of n and show that multiplication by this
element gives a bijective map from
| J n |= φ(
)/
n
2, i.e., half of the elements of
Z n .)
The Jacobi symbol can be efficiently computed if one knows the factorization of
n for, in that case, it reduces to the computation of Legendre symbols which may be
done, for example, by means of Euler's criterion. But there is another method that
allows the computation of the Jacobi symbol without doing any factoring—except
pulling out powers of 2, which is easy—and the amazing thing is that it gives an even
more efficient algorithm to compute Legendre symbols. This method is based on the
Law of Quadratic Reciprocity that was proved by Gauss for the Legendre symbol
and holds equally for the Jacobi symbol. There are more than 200 known proofs
of quadratic reciprocity (see [125]) and we refer to any topic introducing number
theory—like, for example, [77]—for some of them; among the topics related to
cryptography we refer to [118, 180] for proofs.
J n to its complement in
Theorem 2.24
Let m and n be positive odd integers. Then the following conditions
hold:
(i) n = (
1 if n
1
(
mod 4
)
) ( n 1 )/ 2
1
=
1 if n
3
(
mod 4
).
1 if n
(ii) n = (
≡±
1
(
mod 8
)
) ( n 2
1
)/
8
1
=
≡±
(
).
1 if n
3
mod 8
(iii) (Law of Quadratic Reciprocity)
 
Search WWH ::




Custom Search