P-1 / P+1

[ATH]

From the GMP-ECM 6.4.4 (and 7.0) README file:

There is no need to run P-1 several times with the same B1 and B2 as there
is for ECM, since a factor found with one seed will (almost always) be found
by another one.

I did not know there was a small risk of not finding the factor with P-1 if B1 and B2 is high enough. How big is this risk?

Edit: Is this risk due to this: http://www.mersennewiki.org/index.php/P-1

When p-1 has a repeated prime factor greater than sqrt(B1), E will not be multiple of p-1 and the method fails, but this happens with a very low probability.

However not all seeds will succeed: only half of the seeds 'x0' work for P+1
(namely those where the Jacobi symbol of x0^2-4 and P is -1.) Unfortunately,
since P is usually not known in advance, there is no way to ensure that this
holds. However, if the seed is chosen randomly, there is a probability of
about 1/2 that it will give a Jacobi symbol of -1 (i.e., the factor P will
be found if P+1 is smooth enough). A rule of thumb is to run 3 times P+1
with different random seeds. The seeds 2/7 and 6/5 have a slightly higher
chance of success than average as they lead to a group order divisible by
6 or 4,

So I enter these seeds for P+1 with: -x0 2/7 and -x0 6/5 ?

When I try it gives huge x0 values which I guess is the modular fraction of the input number.

[axn]

Originally Posted by ATH

I did not know there was a small risk of not finding the factor with P-1 if B1 and B2 is high enough. How big is this risk?

If the P-1 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.

[ATH]

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²*52387*123456811*4112321431 + 1

So P-1 with B1=1.3*10⁸ and B2=5*10⁹ should find it, but it did not because 11731 > sqrt(B1) ~ 11402.

When I run it again with B1=1.4*10⁸ and B2=5*10⁹ it finds the factor because now B1>11731².


Edit: It is even worse of there is a cube factor. C85=P41*P44 with P41 = 2*277*1031*11953³*52387*123456811*4112321431 + 1. This is not even found with B1=10⁹, so I guess it would not be found with P-1, since you would need B1>11953³ ~ 1.7*10¹²

[MatWur-S530113]

Originally Posted by ATH

...
So P-1 with B1=1.3*10⁸ and B2=5*10⁹ should find it, but it did not because 11731 > sqrt(B1) ~ 11402.
...

This is indeed odd... as far as I understood the stage 1 *all* primes p with p<B1 should be raised to a power, that the power is larger as B1, thus *all* primes p with p<B1 should be squared at least.
Maybe GMP-ECM only calculates powers of a used prime in stage 1, if the prime p<sqrt(B1). But not sure,

That the 'cube-factor' 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...

[LaurV]

Originally Posted by ATH

C81=P37*P44 where P37=2*277*1031*11731²*52387*123456811*4112321431 + 1

This number is not 1.3*10^8-smooth.
Some forget that what we call "B-smooth" means "B-power-smooth", we omit the "power" part because we are lazy when talk/type... We discussed this here on the forum many times.

[LaurV]

Originally Posted by MatWur-S530113

This is indeed odd...

No. it is not. P-1 is an application to Fermat's little theorem. If p is a prime, then b^(p-1)=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 (p-1) number is B-power-smooth, it means that all its factors are in this LCM. So, the LCM is n*(p-1), for some n. This happens if ALL primes in p-1 with their powers are in the LCM. And in this case, we just computed L=b^n(p-1)=(b^p-1)ⁿ=1ⁿ=1 (mod p), or in another words, L-1 is a multiple of p. And because m is a multiple of p too, therefore GCD(L-1,m) will reveal a factor of m. If some factors of p-1 are not contained in the LCM, we can not apply FLT, as the product is not a multiple of p-1.

For example, taking B=5 will find a factor p=31=2*3*5+1, or 61=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 P-1 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, P-1 will find ALL factors which are B-power-smooth, 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²=1 (mod 2047), (it is square root of one, its order is just 2). In this case, we have the diference of squares already (622-1)(622+1)=0 (mod 2047) and one factor of 2047 can be get from GCD(621,2047) and the other from GCD(623,2047)

[ATH]

Thanks. I guess it is not odd then, I always thought it was B-smooth instead of B-power-smooth. I wonder how often you miss factors because of the powers.