Cryptography Reference
In-Depth Information
than Pollard's original rho method. Adapting this modification, Brent and
Pollard found a factor, 1238926361552897, of the eighth Fermat number F 8 =
2 2 8 + 1 in approximately two hours on a mainframe computer (see [44]).
Pollard's two methods above may be invoked when trial division fails to be
useful. However, if the methods of Pollard fail to be useful, which they will for
large prime factors, say, with the number of digits in the high teens, then we
need more powerful machinery. The following is one of those.
In the early 1980s, Carl Pomerance was able to fine-tune the parameters in
Kraitchik's sieve method (see [190]). The following is taken from [169].
C.5 The Quadratic Sieve (QS)
(1)
Choose a factor base
F
=
{
p 1 ,p 2 ,...,p k }
, where the p j are primes for
j =1 , 2 ,...,k
N
.
n
+ t ) 2
(2) For each nonnegative integer j , let t =
±
j . Compute y t =(
n
until k + 2 such values are found that are p k -smooth. For each such t ,
k
p a i, i ,
y t =
±
(C.4)
i =1
and we form the binary k + 1-tuple, v t =( v 0 ,t ,v 1 ,t ,v 2 ,t ,...,v k,t ), where
v i,t is the least nonnegative residue of a i,t modulo 2 for 1
i
k , v 0 ,t =0
if y t > 0, and v 0 ,t =1if y t < 0.
(3)
Obtain a subset
S
of the values of t found in step (2) such that for each
i =0 , 1 , 2 ,...,k ,
v i,t
0 (mod 2) .
(C.5)
t
S
In this case, x 2 = t S
x t t S
n
y t = y 2 (mod n ), where x t =
+ t ,
so gcd( x
±
y,n ) provides a nontrivial factor of n if x
≡±
y (mod n ).
x t (mod n ). Thus, if a prime p y t = x t
In step (2), we have that y t
n ,
we have x t
n (mod p ). Thus, we must exclude from the factor base any primes
p for which there is no solution x
to the congruence x 2
n (mod p ). In
other words, we exclude from the factor base any primes p for which n is not a
quadratic residue modulo p .
Z
Example C.5 Let n = 30167. From Footnote C.2, k = 11, so we choose the
first eleven primes for which n is a quadratic residue. They comprise our factor
base
F
=
{
2 , 7 , 11 , 17 , 29 , 31 , 37 , 41 , 43 , 53 , 67
}
.
We see, by inspection, that a
S
subset
of the values of t in the table on page 518 (which we computed given
Search WWH ::




Custom Search