Cryptography Reference
In-Depth Information
For some choice of k of the g -primes where 1
i 1 <i 2 <
···
<i k
r , let
a = g i 1 g i 2 ···
g i k .
Now, solve for b i with i =1 , 2 ,...,r in
b i
n (mod g i ) .
Then use the Chinese remainder theorem A.12 on page 478, to solve the
system of congruences, for a specific choice of signs:
b i 1 (mod g i 1 ); b
b i 2 (mod g i 2 );
b i k (mod g i k ) .
b
≡±
≡±
···
b
≡±
For this solution b , set c =( b 2
n ) /a 2 . Then we select
W ( x )= a 2 x 2 +2 bx + c,
where the above generation guarantees that a , b , c satisfy
2 n/M, b 2
<a 2 / 2 . (C.6)
(4) ( Test W ( x ) for divisibility by factor base elements ): If q i W ( j ) for
some j
a 2
n = a 2 c,
|
b
|
M,M ], called a sieve number , then q i ( a 2 j + b ) 2
[
n ,so
a 2 (
j
±
t q i
b ) (mod q i ) ,
since gcd( a,q i ) = 1 from step (3). We compute a 2 (mod q i ) for all such
q i via
a 2
g 2
i 1 g 2
g 2
i k (mod q i ) .
Thus, for eGciency, with the calculation of g -primes by the methodology
in in step (3), we also compute and save, for i =1 , 2 ,...,r , all the numbers
g 2
i
···
i 2
(mod q i ) for each q i = p a i
<B where p i F
.
i
(5) ( Sieving C.4 ): Define a (2 M + 1)-tuple:
s =( s (
M ) ,s (
M +1) ,...,s ( j ) ,...,s ( M )) ,
which we initialize by setting s ( j ) = 0 for all j
[
M,M ]. For each sieve
M,M ], i.e., those for which some prime power q i = p a i i
number j
[
W ( j ), reset
s ( j )=ln p i + s ( j ) .
(6) ( Selection of factor candidates ): Define the report threshold C.5
to be
RT =ln 1
2 M n/ 2 .
C.4 In general with the MPQS, the amount of time spent on sieving takes more than 85% of
the total computing time.
C.5 The report threshold is the average of ln |W ( j ) | for j ∈ [ −M,M ]. When s ( j ) ≥ RT , W ( j )
is a good candidate for factoring over the factor base.
Search WWH ::




Custom Search