mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > GMP-ECM

Reply
 
Thread Tools
Old 2014-12-13, 10:12   #1
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

1011110111012 Posts
Default P-1 / P+1

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

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

Quote:
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.




Quote:
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.

Last fiddled with by ATH on 2014-12-13 at 10:42
ATH is offline   Reply With Quote
Old 2014-12-13, 10:45   #2
axn
 
axn's Avatar
 
Jun 2003

10010111110002 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
axn is offline   Reply With Quote
Old 2014-12-13, 18:21   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3,037 Posts
Default

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

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

When I run it again with B1=1.4*108 and B2=5*109 it finds the factor because now B1>117312.


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

Last fiddled with by ATH on 2014-12-13 at 18:41
ATH is offline   Reply With Quote
Old 2014-12-13, 19:20   #4
MatWur-S530113
 
MatWur-S530113's Avatar
 
Apr 2007
Spessart/Germany

2×34 Posts
Default

Quote:
Originally Posted by ATH View Post
...
So P-1 with B1=1.3*108 and B2=5*109 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...
MatWur-S530113 is offline   Reply With Quote
Old 2014-12-14, 16:18   #5
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

52×7×53 Posts
Default

Quote:
Originally Posted by ATH View Post
C81=P37*P44 where P37=2*277*1031*117312*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 is offline   Reply With Quote
Old 2014-12-14, 16:33   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

100100001110112 Posts
Default

Quote:
Originally Posted by MatWur-S530113 View Post
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=bn(p-1)=(bp-1)n=1n=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=22*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 6222=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)

Last fiddled with by LaurV on 2014-12-14 at 16:51
LaurV is offline   Reply With Quote
Old 2014-12-14, 18:58   #7
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

57358 Posts
Default

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.
ATH is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 09:54.

Wed Mar 3 09:54:13 UTC 2021 up 90 days, 6:05, 0 users, load averages: 1.57, 1.52, 1.66

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.