The MPQS, the NFS, and several other factoring algorithms accumulate a list of
relations of the form x^2=a*b*c*d*e (mod n), where a-e are members of a set of
small primes and units called the factorbase. Then these relations are fed into
a matrix algebra step, which results in an equation of the form x^2=y^2(mod n),
x<>y, x+y<>n. Then x+y is divisible by one factor of n, and x-y by the other.
Here is an example: Factor 3977. The program below calculates numbers whose
squares mod 3977 are congruent to products of -1, 2, 3, 5, 7, 11, and 13, and
outputs the results in binary. The first few lines of the output are:
1 0
87 111001
88 11111
89 100101
1111001110
168 111000
209 100111
2971101000
309 100100
3441110100
3541110110
373 100111
3751101010
3891001100
3901110101
414 111000
446 100110
4981101010
Ignoring the trivial relation of 414 and 168, (87*168)^2 and (373*446)^2 have
the same parity. So:
(87*168)^2=-25*49*121
(373*446)^2=-4*9*121
(87*168*2*3)^2=(373*446*5*7)^2
202=202, so this tells us nothing.
Try another: 375, 390, and 88.
(375*390)^2=-2*3*5*7*121*169
88^2=-2*3*5*7
(375*390)^2=(88*143)^2
3078^2=653^2
This tells us something: 3731 and 2425. 41|3731, 97|2425, and the number is
factored.
phma
---
( The method common to the number field sieve, the mpqs, and similar factoring methods
)
3977 constant comp ( a composite number to be factored )
create factorbase comp 1- , 2 , 3 , 5 , 7 , 11 , 13 ,
7 constant factors
: fprod ( n - n )
1 factors 0 do
over 1 i lshift and if
factorbase i cells + @ * comp mod
then
loop nip ;
: factor ( n - n | -1 )
( Returns >=0 if n is a product of some subset of factorbase. )
-1 swap 1 factors lshift 0 do
i fprod over = if
nip i swap leave
then
loop drop ;
: .squares
comp 1 do
i dup * comp mod factor 1+ ?dup if
cr i 5 .r 1- base @ swap 2 base ! factors .r base !
then
loop ;
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
