Cryptography Reference
In-Depth Information
given bound B and factor as many z t as possible over the factor base. In our example,
we may choose as factor base the set of the primes
{
,
,
,
}
, and we find
that z 0 , z 1 and z 5 can be completely factored over the factor base and they give
the required congruence. But note that, in contrast with what happens in this small
example, not all primes
7, i.e.,
2
3
5
7
B should be members of the factor base in general. This is
because the only odd primes that may occur in the factorization of an integer of the
form x t
n are those p for which the congruence x 2
has a solution
( x t mod p will, in this case, be a solution) and these are precisely the primes p
such that n is a quadratic residue modulo p . As we have seen, this property is easy
to verify by using the Legendre symbol and so we only include in the factor base
the odd primes
n
(
mod p
)
B that satisfy p
1. For example, there would be no point in
including 11 in the factor base when trying to factor 1261 because
=
> numtheory:-legendre(1261, 11);
-1
and hence 11 cannot appear as a factor of the z t in this case. But, in addition to 2 and
the odd primes modulowhich n is a quadratic residue, wemay include something else
in the factor base, namely, the integer
1. This may seem strange at first sight because
we are looking for squares, which are always positive, but it is easy to realize that,
when searching for squares,
1 behaves in a similar way to a prime factor because
what we need is, again, that its exponent is even. Thus including
1 in the factor
base allows us t o consider negative values for the z t . The advantage is that, instead
of starting at
n
and letting the x t run up throug h the integers, we may let the x t
run through a sequence of integers centered at
n
by letting t also run through
negative values, ie., t
for an appropriate positive integer M . This will
cause about half of the z t , namel y those corresponding to negative values of t and
hence to values of x t less than
∈[−
M
,
M
]
n
, to be negative. These negative values are easily
dealt with because we have included
1 in the factor base and, on the other hand,
this method has the advantage that the absolute values of the z t are now somewhat
smaller on average and this makes it more likely that these values are completely
factored over the factor base. We return to our earlier example to see what happens
if we add
1 to the factor base.
Example 6.14 Consider again n
=
1261 and take as factor base the set
{−
1
,
2
,
3
,
5
,
7
}
.
We l e t t run thro ugh the interval [
2,2] which will produce two values for the x t
preceding 1261
51 and three following it. Thus we will obtain two negative
values and three positive values for the z t =
35
.
x t
n . Only the last of these values does
not completely factor over the factor base (as we have seen in the preceding example,
z 2 =
·
3
61) and the result of factoring the first four z t is given in the following table:
x t
x t
t
x t
z t
=
n
Factorization of z t
2
34
1156
105
1 ·
3 · 5 · 7
2 2
3 2
1
35
1225
36
1
·
·
0
36
1296
35
5
·
7
2 2
3 3
1
37
1369
108
·
 
 
Search WWH ::




Custom Search