Cryptography Reference
In-Depth Information
the function be a permutation, i.e., bijective. We may consider the
Blum-Williams
function
:
BW
n
−→
QR
n
QR
n
x
2
mod
n
x
−→
.
BW
n
is not a permutation in general but there is a special case in which this
is true.
Definition 3.13
A
Blum integer
is an integer
n
such that
n
=
pq
, where
p
and
q
are distinct primes such that
p
≡
q
≡
3 (mod 4) (as we have already mentioned, a
prime
p
such that
p
≡
3
(
mod 4
)
is also called a Blum prime).
The modular squaring map
BW
n
defined above has an especially good behavior
when
n
is a Blum integer. In this case we have:
Z
n
, and
BW
n
the modular squaring map. Then B W
n
:
QR
n
−→
QR
n
is a permutation.
Theorem 3.6
Let n be a Blum integer,
QR
n
the set of quadratic residues in
Proof
First we show that if
p
is a Blum prime and
x
∈
QR
p
then
−
x
∈
QR
p
.
Since
p
is a Blum prime there exists an integer
k
such that
p
=
4
k
+
3 and hence
we have that
)
(
p
−
1
)/
2
2
k
+
1
(
−
1
=
(
−
1
)
≡−
1
(
mod
p
).
∈
QR
p
and,
since the product of a quadratic residue by a quadratic non-residue is a quadratic
non-residue because of the multiplicativity of the Legendre symbol, we see that
−
Thus, from Euler's criterion (Proposition 2.12) if follows that
−
1
x
=
(
−
1
)
x
∈
QR
p
.
Now let
n
=
pq
where
p
and
q
are Blum primes. Taking into account that the
Z
n
is finite, to prove that
BW
n
is a permutation it suffices
to show that it is injective. Suppose then that
BW
n
(
set
QR
n
of squares of
, i.e, that
x
2
x
)
=
BW
n
(
y
)
≡
y
2
(
mod
n
)
. We have to show that
x
≡
y
(
mod
n
)
. Since
x
,
y
∈
QR
n
we have that
also
x
,
y
∈
QR
p
and
x
,
y
∈
QR
q
, so that their opposites satisfy
−
x
,
−
y
∈
QR
p
and
−
x
,
−
y
∈
QR
q
and, in particular, we also have that
−
x
,
−
y
∈
QR
n
.Our
hypothesis
x
2
y
2
≡
(
mod
n
)
means that
n
|
(
x
+
y
)(
x
−
y
)
and, since
x
∈
QR
n
and
−
y
∈
QR
n
, we have that
x
≡−
y
(
mod
n
)
or, equivalently,
n
does not divide
x
+
y
. Thus either each of the two prime factors of
n
divides one of the terms
x
+
y
,
x
−
y
, or, alternatively,
n
|
(
x
−
y
)
. In the first case we may assume without loss of
generality, that
p
|
(
x
+
y
)
, i.e.,
x
≡−
y
(
mod
p
)
but, as
x
∈
QR
p
, this implies
∈
QR
p
which is a contradiction. Thus we are only left with the second
alternative, i.e.,
n
−
that
y
|
(
−
)
≡
(
)
x
y
or, in other words,
x
y
mod
n
, which completes the
proof.
Remark 3.7
We have seen in Corollary 2.7 that if
n
is a product of two distinct odd
primes, then each quadratic residue has exactly four square roots modulo
n
.Fromthe
preceding theorem it follows that if, furthermore,
n
is a Blum integer, then exactly
one of these four square roots is also a quadratic residue modulo
n
.
