 mersenneforum.org > Math P-1 question
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read 2011-10-06, 12:51 #1 Bdot   Nov 2010 Germany 3·199 Posts 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   2011-10-06, 13:23 #2 LaurV Romulan Interpreter   Jun 2011 Thailand 33·347 Posts 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   2011-10-06, 14:14 #3 Prime95 P90 years forever!   Aug 2002 Yeehaw, FL 11100111011002 Posts Brent-Suyama extension: http://www.mersenneforum.org/showthread.php?t=8190   2011-10-07, 11:34   #4
Mr. P-1

Jun 2003

7×167 Posts Quote:
 Originally Posted by Bdot 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.   2011-10-10, 08:08   #5
Bdot

Nov 2010
Germany

11258 Posts 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 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.  Thread Tools Show Printable Version Email this Page

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

Tue Apr 13 21:46:45 UTC 2021 up 5 days, 16:27, 1 user, load averages: 1.68, 1.65, 1.73

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.