mersenneforum.org  

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

Reply
 
Thread Tools
Old 2011-10-06, 12:51   #1
Bdot
 
Bdot's Avatar
 
Nov 2010
Germany

3·199 Posts
Default P-1 question

Hi,

quite a while ago, P-1(B1=635,000, B2=18,097,500) found factor 1919565392651028059642113943994258791 of M53470619. This factor has k=5 × 29 × 13463 × 17477 × 34327 × 449437 × 34101721.

Can someone please explain why P-1 was able to find this factor?
From math.php: "Stage 2 will find the factor q if k has just one factor between B1 and B2 and all remaining factors are below B1."

Here, the biggest factor of k is bigger than B2, but I found no explanation under which conditions P-1 may find such factors. What are the chances of this happening? All of my other 37 P-1 factors have their k's prime factors below B2.

Thanks
Bdot is offline   Reply With Quote
Old 2011-10-06, 13:23   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

22×7×11×29 Posts
Default

When you raise 3E it could happen that the order of 3 is smaller then 2kp/h, with h the highest factor of k. This happens often.

Edit: assume you want to factor M11=2047. You pick a B1 and B2 both equal with 2. You will not find any factor by rising 3 at the power of 2. You have to raise 3 at a power which is a multiple of 88/2p to find any factor, as the order of 3 in 2047 is 88, (388=1 mod 2047) which is 2*4*11. So your B1 and B2 have to be slightly larger, 4 would be enough. But there is nothing magic in that 3. Any other number below 2047 would suffice, and assuming you pick from a magic hat the number 622, then 622^2=1 mod 2047 (is a square root of 1, so its order is 2). So you could find the factors even if your B1 and B2 are both 2.

This was a not so fortunate example. P-1 tries to find the order of 3 (or any x) in m (the number you try to factor). If this m is prime, then Fermat's theorem says that xp-1=1 mod m. It means that the order of x can be any divisor (prime or not prime factor) of p-1. For example, the order of 3 in 11 is 5 (a divisor of 11-1, as 11 is prime, 35=1 mod 11). When you multiply two primes, m=p*q, then the order of x in m will be the lcm of the orders of x in p and q. It means that lcm(q-1, p-1) will always be a multiple of the order you look for. P-1 tries to find this order by taking all numbers below B1, making the LCM of their product, and raising x (in our case 3) at that number (multiplied by 2p for mersenne). If the order of 3 is there, then you have a power of 3 which is 1 mod m (because you rose 3 at a multiple of its order), and you go back on the chain to find exactly how much the order is, and extract the factor, no matter if the factor is much bigger. This generally speaking, and without any optimization.

Last fiddled with by LaurV on 2011-10-06 at 14:01
LaurV is offline   Reply With Quote
Old 2011-10-06, 14:14   #3
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

2·3·1,193 Posts
Default

Brent-Suyama extension: http://www.mersenneforum.org/showthread.php?t=8190
Prime95 is offline   Reply With Quote
Old 2011-10-07, 11:34   #4
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7·167 Posts
Default

Quote:
Originally Posted by Bdot View Post
Can someone please explain why P-1 was able to find this factor?
Check your results.txt file. If you see the parameter E=6 (or some higher number) in the status line, then the Brent-Suyama extension to stage 2 was used, which will occasionally find a factor with one prime factor of k > B2 and all others < B1. This optimisation requires additional memory, so it is not usually in effect unless the available memory is particularly generous.

There are other possibilities, even without the the B-S extension. The Stage 2 code uses an optimisation called prime pairing, which sometimes includes two primes between B1 and B2 per iteration, instead of the one per iteration that a naive implementation would do. This is primarily a speed-up - you need fewer iterations to include all the primes - but it does have a potentially beneficial side-effect: Stage 2 can find a factor whose k has two prime factors between B1 and B2 if those primes happen to be paired. The likelihood is small, and I have never heard of such a case.

With the B-S extension there are yet further possibilities, such as Stage 2 finding a factor whose k has one prime factor between B1 and B2 and one > B2, or more than two > B1. The likelihood is even smaller, and again I have never heard of such a discovery.
Mr. P-1 is offline   Reply With Quote
Old 2011-10-10, 08:08   #5
Bdot
 
Bdot's Avatar
 
Nov 2010
Germany

3×199 Posts
Default

Thanks a lot for explanations and links. With that I found some more reading on the topic. Good to know it was not a bug that made the factor appear

Quote:
Originally Posted by Mr. P-1 View Post
Check your results.txt file. If you see the parameter E=6 ...
This particular result line did not have the E= parameter because factor-found-results seem to omit it. But most (262) of my "P-1 completed"-results have E=12, some (71) have E=6 and only 6 did not have either. So it's very likely that memory was sufficient for B-S to find this factor.
Bdot is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 12:07.

Fri Nov 27 12:07:06 UTC 2020 up 78 days, 9:18, 4 users, load averages: 1.50, 1.29, 1.24

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.