2009-08-23, 12:18 | #1 |
Sep 2006
Brussels, Belgium
3^{3}·61 Posts |
Brent-Suyama extension of P-1 factoring
The Brent-Suyama extension of P-1 factoring DOES find factors ;-)
I stumbled upon this when looking the last factor I found by P-1 factoring : [Sun Aug 23 03:49:05 2009] P-1 found a factor in stage #2, B1=540000, B2=18225000. UID: S485122/Q67-P3, M21909863 has a factor: 5349424617695409539087 The 73 bits factor 5349424617695409539087 = 2 x 1069 x 2269 x 21909863 x 50329801 + 1 The 50329801 factor of q-1 is is about 2,76 times the B2 bound ! It must be the Brent-Suyama extension doing its work. I then looked through my previous factors found and stumbled upon this : [Mon Nov 12 09:58:01 2007] P-1 found a factor in stage #2, B1=100000, B2=3000000. UID: S485122/Q67-P3, M2824333 has a factor: 89849066709690811889 67 bits factor 89849066709690811889 = 2^4 * 6481 * 306786091 * 2824333 + 1 The 306786091 factor of q-1 is more than 100 times the B2 bound !!! Those are the only cases I found in my results files where the largest factor of q-1 is bigger than the B2 bound, out of 930 P-1 factoring attempts with E=6 and 214 P-1 factoring attempts with E=12. What is the probability of the Brent-Sumaya extension of finding a factor during P-1 factoring of Mersenne numbers ? As a side note : am I right in thinking that there is no limit (except the number to factor of course ;-) to the factor that could be found with even a small B1 bound. For fun one could search for a (large) prime number q = 2 * Product( k_{i}^j ) * p + 1 {k_{i} < B1} that is factor of 2^p - 1. It would be reversing the search : start with the factor and find the corresponding Mersenne number. Each number to check does no imply much work : check if q is congruent to 1 or 7 mod 8, check if it is prime and then check if it divides 2^p - 1 for different values of p. Of course the searching algorithm is still to be written. Perhaps that last paragraph should be in the puzzles (or Misc Math) sub-forum. Jacob |
2009-08-23, 15:21 | #2 |
Apr 2007
Spessart/Germany
A2_{16} Posts |
Hello,
you can find some notes on the Brent-Suyama extension in the Readme file of GMP-ECM, but I don't know anything about the increasing of the chance to find a factor, too. Of course it is true: if q divides 2^p-1 then 2p divides q-1. But this statement is true for other bases, too: f.e.: if q divides 5^p-1 then 2p divides q-1. Thus if you sieve out the primes q congruent 1 mod 2p you have 2 problems: 1) is it the correct exponent p or is another prime p' (which divides q-1, too) the correct exponent? 2) if p is the correct exponent which base is the correct one? and another problem: is there always a base b and a prime p that q==1 mod 2p divides b^p-1 ? And reducing this problems to Mersenne numbers only results in a slow kind of trial factoring the Mersenne number. I know it because I tried to find an 80-digit factor this way... of course without success ;-) best regards, Matthias |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Brent tables reservations | chris2be8 | Factoring | 446 | 2020-04-29 17:08 |
Extension request | LaurV | Data | 9 | 2019-04-14 00:13 |
PCI-E USB 3.0 Extension Cable | vsuite | GPU Computing | 7 | 2017-07-10 20:45 |
Curious about the Suyama test | siegert81 | Math | 2 | 2014-11-23 21:12 |
brent suyama extension in P-1 | bsquared | Factoring | 9 | 2007-05-18 19:24 |