Cryptography Reference
In-Depth Information
x
mn
=
x
m
x
n
·
∈
Z
n
x
n
=
n
·
n
=1.
Last but not least,
Gauss' law of quadratic reciprocity
suggests that if
gcd
(
m, n
)=1and
m, n >
2,then
Consequently, for
x
m
n
n
m
=(
1)
(
m−
1)(
n−
1)
/
4
.
−
Thanks to these properties, there is an efficient
27
(and recursive) algorithm
for computing
n
, which does not require the prime factorization of
n
. We don't
elaborate on this algorithm. For the purpose of this topic, it is sufficient to know that
an efficient algorithm for computing
n
exists.
As mentioned earlier, the fact that the Jacobi symbol of
x
modulo
n
is 1 does
not necessarily imply that
x
Z
n
with
∈
QR
n
.Let
J
n
be the set of all elements of
Jacobi symbol 1:
x
n
=1
∈
Z
n
|
J
n
=
{
x
}
∈
Z
n
that are quadratic
nonresidue, but still have Jacobi symbol 1. These elements are called
pseudosquares
modulo
n
, denoted as
QR
n
(i.e.,
QR
n
=
J
n
\
Obviously,
QR
n
⊂
J
n
and there are elements
x
QR
n
).
Let
n
=
pq
be the product of two primes. Then
Z
n
has
φ
(
n
)=(
p
1)
elements, and these elements can be partitioned into two equally large sets. One half
of the elements (i.e.,
J
n
) has Jacobi symbol 1, and the other half of the elements
has Jacobi symbol
−
1)(
q
−
−
1.
J
n
can be further partitioned into two equally large sets (i.e.,
QR
n
) with
|QR
n
|
QR
n
and
|
QR
n
|
=(
p
−
1)(
q
−
1)
/
4. For example, if
p
=3
=
and
q
=7,then
n
=3
·
Z
21
=
{
1
,
2
,
4
,
5
,
8
,
10
,
11
,
13
,
16
,
17
,
19
,
20
}
7=21,
,and
φ
(21) = 2
·
6=12.
J
21
has 6 elements and these elements can be partitioned as
follows :
J
21
=
{
1
,
4
,
5
,
16
,
17
,
20
}
QR
21
=
{
1
,
4
,
16
}
QR
21
{
5
,
17
,
20
}
=
The algorithm has a running time of
O
((ln
n
)
3
) bit operations.
27
