Cryptography Reference
In-Depth Information
has no prime factors less than or equal to the smoothness bound
B
(these factors are
easily obtained by trial division). Since their behavior is different, we will analyze
separately the following three cases: odd primes in the factor base not dividing
m
,
odd primes dividing
m
, and the prime 2.
Suppose first that
p
is an odd prime
B
such that
m
p
≤
=
1 (so that
p
does not
divide
m
). In this case the equation
x
2
has, as we have seen, exactly
two solutions, and this means that in the sequence
x
0
,
≡
mn
(
mod
p
)
x
1
,...,
x
p
−
1
there are two
values, say
x
t
1
and
x
t
2
, such that
p
divides
x
t
1
−
mn
and
x
t
2
−
mn
. Then
p
also divides
each of the values
x
t
1
+
sp
−
2
mn
and
x
t
2
+
sp
−
2
=
(
x
t
1
+
)
−
=
(
x
t
2
+
)
−
mn
for all integers
s
, i.e.,
p
appears as a factor twice for each
p
numbers in the sequence
of
z
-values. This would give an average of
mn
sp
mn
sp
2
p
for the exponent of
p
in each
z
-value,
except that it does not take into account the possibility that these values may be
divisible by higher powers of
p
. But the power
p
2
occurs twice for each
p
2
z
-values
being tried and this adds two more
p
-factors for each
p
2
z
-values. Similarly, if
i
2,
each
p
i
occurs twice for each
p
i
values and so the total contribution of
p
or, in other
words, the average exponent of
p
is:
≥
1
∞
2
p
+
2
p
2
+
2
p
3
+··· =
2
p
1
p
i
2
p
(
1
2
+
=
1
+
1
)
=
1
.
p
−
p
−
i
=
1
Now suppose that
p
is an odd prime that divides
m
. Then
p
is a factor of
x
t
mn
precisely when
p
divides
x
t
and, since
m
is square-free,
p
2
does
z
t
=
−
not divide
x
t
1
p
in this case.
Finally, let us look at the prime 2, whose contribution also depends, as we
are going to see, on the value of
mn
. Notice first that just one-half of the values
z
t
−
mn
. Thus the average exponent of
p
per
z
-value is just
x
t
mn
are even. Assuming that
z
t
is even, we distinguish two cases:
mn
odd—in which case
x
t
is also odd and hence
x
t
=
−
≡
(
)
—and
mn
even. In
the first of these cases we have three subcases. The first is that
mn
1
mod 8
≡
(
)
1
mod 8
and then, since
x
t
≡
1
(
mod 8
)
too, we have that
z
t
≡
0
(
mod 8
)
. Moreover,
we shall see that this is the only situation in which
z
t
≡
0
(
mod 8
)
. Indeed,
the second subcase is when
mn
≡
5
(
mod 8
)
and then
z
t
≡
0
(
mod 4
)
but
z
t
≡
0
(
mod 8
)
. These two subcases exhaust the possibility that
mn
≡
1
(
mod 4
)
and hence the remaining subcase will be
mn
≡
3
(
mod 4
)
which implies that
z
t
≡
2
(
mod 4
)
, so that
z
t
is even (as assumed by hypothesis) but not divisi-
ble by 4.
Let us now compute the average exponent of 2 in the
z
-values for each of these
three subcases. In the first, namely, when
mn
,wehave2
3
as a factor in
one of each two
z
-values (in the even one) which gives a contribution to the average
exponent of
2
. But there will be also some higher powers of 2 as factors in this case,
so there will be one more factor 2 for each 2
i
≡
1
(
mod 8
)
z
-values, for
i
≥
2, and hence the
average exponent of 2 will be:
