Cryptography Reference
In-Depth Information
Z
101
, namely 50 elements, are
We check that exactly one half of the elements of
quadratic residues:
> nops(qr101);
50
Z
101
:
Next, we compute a generator of
> findgenerator(101);
42
∈ Z
101
:
> evenpowers42mod101 := map(x -> 42&ˆx mod 101, {seq(2*i, i=1..50)});
{1, 4, 5, 6, 9, 13, 14, 16, 17, 19, 20, 21, 22, 23, 24, 25, 30, 31, 33, 36,
37, 43, 45, 47, 49, 52, 54, 56, 58, 64, 65, 68, 70, 71, 76, 77, 78, 79, 80,
81, 82, 84, 85, 87, 88, 92, 95, 96, 97, 100}
We compute all the even-exponent powers of the generator 42
Z
101
:
Finally, we check that these powers coincide with the quadratic residues in
> evalb(qr101 = evenpowers42mod101);
true
The following result gives a simple way to compute the Legendre symbol:
Proposition 2.12
(Euler's criterion)
Let p be an odd prime and a an integer. Then
a
p
a
(
p
−
1
)/
2
≡
(
mod
p
).
Proof
a
then both sides of the congruence are congruent to 0 modulo
p
. Hence
we may suppose that
p
does not divide
a
and, by Fermat's little theorem (Theorem
2.2) we have that
a
p
−
1
If
p
|
so that
a
(
p
−
1
)/
2
≡
1
(
mod
p
)
≡±
1
(
mod
p
)
.Let
g
be a
g
i
. Since
a
is a quadratic residue if and only if
i
is even, we
see that the left side of the congruence in the statement of the proposition is equal to
1 if and only if
i
is even. The right side of this congruence is then equal to
g
i
(
p
−
1
)/
2
,
which is 1 if and only if
Z
p
and
a
generator of
=
(
p
−
1
)
divides
i
(
p
−
1
)/
2, i.e., if and only if
i
is even. Thus
both sides of the congruence are
±
1 and each side is 1 if and only if
i
is even, which
completes the proof.
Remark 2.9
Euler's criterion provides a polynomial-time algorithm to compute the
Legendre symbol and hence to decide whether an element of
Z
p
is a quadratic residue
or not. The algorithm performs a modular exponentiation modulo
p
with an exponent
less than
p
and hence its complexity is
O
3
(
(
)
)
. However, we shall see later that
there is a faster algorithm to compute the Legendre symbol.
len
p
The next proposition collects several basic properties of the Legendre symbol:
Proposition 2.13
Let p be an odd prime. Then the Legendre symbol satisfies:
then
p
p
.
(i) If a
≡
b
(
mod
p
)
=
(ii)
a
p
p
p
.
=
