|
I've been playing around with MPQS on UBASIC, to
see if I could find a factor of M727 and/or RSA232 ...
First I tried the approach of using very large
factor bases ... i.e. I'd sieve to 131071 using UBASIC's PRMDIV function,
then check the remaining residues up to about 2^48 using P-1 ... after
testing 2^32 numbers, I had a couple of full-relations, useless
combinations ...
When dealing with numbers of this magnitude, that
kind of sieving needs to be done on distributed-computing platforms, with
hundreds of machines taking little sections to sieve and reporting back to a
main server ... like PrimeNet etc.
So then I tried a different approach of using a
much smaller factor base, and looking only for partials / double partials
...
For the formula F(x) = a2x2 + 2abx + c, where b2 -
N = a2c, and checking over the range x = 0 to x = 2^32-1 ...
First I look for F(n) where it is the product of
small primes x one large prime P (proved by pseudo-primality testing on a few
bases),
For each P, I find the two roots n1,n2 == 0 mod P
for F(x),
For n1,n2, then n1+P, n2+P, n1+2P, n2+2P, n1+3P etc
I checked F(m) where it is product of small primes x P x one other large prime Q
(again proved by pseudo-primality testing),
Then I scan through the resulting list looking for
two results with different n and P, and the same Q ...
So I end up with some Partial Relations
thus
f ---> some small primes x P1
g ---> some small primes x P2
h ---> some small primes x P1 x
Q
j ---> some small primes x P2 x
Q
And a bit of work ...
Uf = a2f + b, Vf = a2 x some small primes x
P1
Ug = a2g + b, Vg = a2 x some small primes x P2
Uh = a2h + b, Vh = a2 x
some small primes x P1 x Q
Uj = a2j + b, Vj = a2 x some small primes x P2 x
Q
Then, multiplying the relations together ...
Uf.Uf.Ug.Ug.Uh.Uh.Uj.Uj == a2.a2.a2.a2.lots of small primes multiplied
together.P1.P2.P1.P2.Q.Q (mod N)
If the 'lots of small primes multiplied together' is square, I end up
with a Complete Relation of the form X2 == Y2 (mod N)
Unfortunately, after checking about 1000 Complete Relations derived with
the above system, they all have one common problem ...
X == Y (mod N) ... so (X-Y) is always a multiple of N ... and
GCD(X-Y,N) = 1 ...Damn !!!
What am I missing here ... I understood that with MPQS, each
complete relation had a 50:50 chance of yielding a factor of N ?
On much smaller N's, i.e. 2^64 or below, the 50:50 yield looks correct, but
when I try on larger N's i.e. M727 or RSA-232, I'm not getting anything
...
I suspect my process of "manufacturing relations" is flawed, can anyone
advise what I'm doing wrong ?
Dave
|
