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 1
89 100101
001110
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
