20111006, 12:51  #1 
Nov 2010
Germany
1125_{8} Posts 
P1 question
Hi,
quite a while ago, P1(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 P1 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 P1 may find such factors. What are the chances of this happening? All of my other 37 P1 factors have their k's prime factors below B2. Thanks 
20111006, 13:23  #2 
Romulan Interpreter
Jun 2011
Thailand
5^{2}×7×53 Posts 
When you raise 3^{E} 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, (3^{88}=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. P1 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 x^{p1}=1 mod m. It means that the order of x can be any divisor (prime or not prime factor) of p1. For example, the order of 3 in 11 is 5 (a divisor of 111, as 11 is prime, 3^{5}=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(q1, p1) will always be a multiple of the order you look for. P1 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 20111006 at 14:01 
20111006, 14:14  #3 
P90 years forever!
Aug 2002
Yeehaw, FL
1CBD_{16} Posts 
BrentSuyama extension: http://www.mersenneforum.org/showthread.php?t=8190

20111007, 11:34  #4 
Jun 2003
491_{16} Posts 
Check your results.txt file. If you see the parameter E=6 (or some higher number) in the status line, then the BrentSuyama 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 BS 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 speedup  you need fewer iterations to include all the primes  but it does have a potentially beneficial sideeffect: 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 BS 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. 
20111010, 08:08  #5 
Nov 2010
Germany
3·199 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
This particular result line did not have the E= parameter because factorfoundresults seem to omit it. But most (262) of my "P1 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 BS to find this factor. 