mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-08-23, 12:18   #1
S485122
 
S485122's Avatar
 
Sep 2006
Brussels, Belgium

22·383 Posts
Default 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
S485122 is offline   Reply With Quote
Old 2009-08-23, 15:21   #2
MatWur-S530113
 
MatWur-S530113's Avatar
 
Apr 2007
Spessart/Germany

2×34 Posts
Default

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
MatWur-S530113 is offline   Reply With Quote
Reply

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

All times are UTC. The time now is 19:21.

Mon Jul 13 19:21:40 UTC 2020 up 110 days, 16:54, 1 user, load averages: 1.92, 1.68, 1.65

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.