 mersenneforum.org > Math Brent-Suyama extension of P-1 factoring
 Register FAQ Search Today's Posts Mark Forums Read 2009-08-23, 12:18 #1 S485122   Sep 2006 Brussels, Belgium 33·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( ki^j ) * p + 1 {ki < 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 MatWur-S530113   Apr 2007 Spessart/Germany A216 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 Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post chris2be8 Factoring 446 2020-04-29 17:08 LaurV Data 9 2019-04-14 00:13 vsuite GPU Computing 7 2017-07-10 20:45 siegert81 Math 2 2014-11-23 21:12 bsquared Factoring 9 2007-05-18 19:24

All times are UTC. The time now is 20:23.

Mon Jan 18 20:23:54 UTC 2021 up 46 days, 16:35, 0 users, load averages: 1.55, 1.85, 1.81