-   Math (
-   -   P-1 question (

Bdot 2011-10-06 12:51

P-1 question

quite a while ago, P-1(B1=635,000, B2=18,097,500) found factor [URL=""]1919565392651028059642113943994258791[/URL] 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.


LaurV 2011-10-06 13:23

When you raise 3[SUP]E[/SUP] 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[SUP]88[/SUP]=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 x[SUP]p-1[/SUP]=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, 3[SUP]5[/SUP]=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.

Prime95 2011-10-06 14:14

Brent-Suyama extension: [url][/url]

Mr. P-1 2011-10-07 11:34

[QUOTE=Bdot;273568]Can someone please explain why P-1 was able to find this factor?[/QUOTE]

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.

Bdot 2011-10-10 08:08

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 :smile:

[QUOTE=Mr. P-1;273674]Check your results.txt file. If you see the parameter E=6 ...[/QUOTE]

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.

All times are UTC. The time now is 14:05.

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