20141213, 10:12  #1  
Einyen
Dec 2003
Denmark
101111011101_{2} Posts 
P1 / P+1
From the GMPECM 6.4.4 (and 7.0) README file:
Quote:
Edit: Is this risk due to this: http://www.mersennewiki.org/index.php/P1 Quote:
Quote:
When I try it gives huge x0 values which I guess is the modular fraction of the input number. Last fiddled with by ATH on 20141213 at 10:42 

20141213, 10:45  #2 
Jun 2003
1001011111000_{2} Posts 
If the P1 is B1/B2 smooth, all seeds will find them. Some seeds can find factors that are not smooth. Think about it. Suppose that you are using a seed x. Unbeknownst to you, x = y^c (mod N). Then effectively x^whatever = y^(whatever * c) (mod N). So you're getting a factor of c for free.

20141213, 18:21  #3 
Einyen
Dec 2003
Denmark
3,037 Posts 
Thanks, that is good to know. But I guess there is a (very?) small risk of missing a factor even if your B1 and B2 are large enough, if there is a repeating factor that is larger than sqrt(B1).
I created a number to test it, and it is real: C81=P37*P44 where P37=2*277*1031*11731^{2}*52387*123456811*4112321431 + 1 So P1 with B1=1.3*10^{8} and B2=5*10^{9} should find it, but it did not because 11731 > sqrt(B1) ~ 11402. When I run it again with B1=1.4*10^{8} and B2=5*10^{9} it finds the factor because now B1>11731^{2}. Edit: It is even worse of there is a cube factor. C85=P41*P44 with P41 = 2*277*1031*11953^{3}*52387*123456811*4112321431 + 1. This is not even found with B1=10^{9}, so I guess it would not be found with P1, since you would need B1>11953^{3} ~ 1.7*10^{12} Last fiddled with by ATH on 20141213 at 18:41 
20141213, 19:20  #4  
Apr 2007
Spessart/Germany
2×3^{4} Posts 
Quote:
Maybe GMPECM only calculates powers of a used prime in stage 1, if the prime p<sqrt(B1). But not sure, That the 'cubefactor' will not be found is a small risk to miss a factor. But maybe it is meant that there is a risk to find *all* factors of n at once with huge (B1,B2) pairs... 

20141214, 16:18  #5  
Romulan Interpreter
Jun 2011
Thailand
5^{2}×7×53 Posts 
Quote:
Some forget that what we call "Bsmooth" means "Bpowersmooth", we omit the "power" part because we are lazy when talk/type... We discussed this here on the forum many times. 

20141214, 16:33  #6 
Romulan Interpreter
Jun 2011
Thailand
10010000111011_{2} Posts 
No. it is not. P1 is an application to Fermat's little theorem. If p is a prime, then b^(p1)=1 (mod p). Now, if m=p*q, where p and q are not known, we can pick some base b, and some limit B, and compute b^LCM(x, x<B). This LCM (least common multiple, or lowest) is a product that contains all numbers smaller than B, and products of them, and if our unknown (p1) number is Bpowersmooth, it means that all its factors are in this LCM. So, the LCM is n*(p1), for some n. This happens if ALL primes in p1 with their powers are in the LCM. And in this case, we just computed L=b^{n(p1)}=(b^{p1})^{n}=1^{n}=1 (mod p), or in another words, L1 is a multiple of p. And because m is a multiple of p too, therefore GCD(L1,m) will reveal a factor of m. If some factors of p1 are not contained in the LCM, we can not apply FLT, as the product is not a multiple of p1.
For example, taking B=5 will find a factor p=31=2*3*5+1, or 61=2^{2}*3*5+1, but will not find a factor p=41=2^3*5+1, for that, we will need B>=8. That is why P1 method does not find the factors "in order" according with their size, smaller factors can be missed if they are not "power smooth enough". Once B is picked, P1 will find ALL factors which are Bpowersmooth, regardless of "seed" (the seed is the "base b" we pick). Of course, we may be lucky when selecting b, for example, we can run in some b with a low modular order** mod m, as axn said, but that is a different story. edit ** the "modular order (mod m)" of b is the smallest integer n for which b^n=1 (mod m). For example, we would need a B>=11 to factor 2047, for a random b. But if we are lucky and pick b=622, we can factor 2047 even with B=2, because 622^{2}=1 (mod 2047), (it is square root of one, its order is just 2). In this case, we have the diference of squares already (6221)(622+1)=0 (mod 2047) and one factor of 2047 can be get from GCD(621,2047) and the other from GCD(623,2047) Last fiddled with by LaurV on 20141214 at 16:51 
20141214, 18:58  #7 
Einyen
Dec 2003
Denmark
5735_{8} Posts 
Thanks. I guess it is not odd then, I always thought it was Bsmooth instead of Bpowersmooth. I wonder how often you miss factors because of the powers.
