mersenneforum.org P-1 factoring anyone?
 Register FAQ Search Today's Posts Mark Forums Read

 2012-02-03, 10:55 #1112 MrHappy     Dec 2003 Paisley Park & Neverland 5×37 Posts Oh! worktodo got somewhat corrupted... I guess I should have seen that earlier.
2012-02-03, 12:38   #1113
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

332710 Posts

Quote:
 Originally Posted by axn Where did you get this information? Neither 5,27 nor 5,9 will find this. A stage 1 bound of 27 is needed to find this.
Probably from my exponent page for M2011. The smaller factor (2171881) is split up (per my standard k-value practice) into 2171881 - 1 = 23 × 33 × 5 × 2011. Then stripping out the exponent (2011) and a 2, you're left with 22 × 33 × 5.

Now I've been told that B2 should be the largest [forgive probably-wrong math term] powered prime factor, and B1 the second-largest, so chosing between 22=4, 33=27 and 5 I list B1=5, B2=27.

Is this approach wrong? If a smaller prime exponent (3<5) gives a larger value than a larger prime exponent when raised to the appropriate power (33 > 51) should that override the minimum B1?

2012-02-03, 13:14   #1114
axn

Jun 2003

4,919 Posts

Quote:
 Originally Posted by James Heinrich The smaller factor (2171881) is split up (per my standard k-value practice) into 2171881 - 1 = 23 × 33 × 5 × 2011. Then stripping out the exponent (2011) and a 2, you're left with 22 × 33 × 5.
So far, so good.

Quote:
 Originally Posted by James Heinrich Now I've been told that B2 should be the largest [forgive probably-wrong math term] powered prime factor, and B1 the second-largest, so chosing between 22=4, 33=27 and 5 I list B1=5, B2=27.
Close, but not quite. Stage 2 can't really do powers of prime factors. It can cover a single prime factor > B1 and <= B2.

So the 3^3 will not be caught in Stage 2. It has to be caught in Stage 1.

The 5 could conceivably be caught by stage 2, but...

Quote:
 Originally Posted by James Heinrich If a smaller prime exponent (3<5) gives a larger value than a larger prime exponent when raised to the appropriate power (33 > 51) should that override the minimum B1?
Yep. For each prime <= B1, you compute the largest power of that prime <= B1. The product of these is what constitutes the B1 exponent. So if we use a B1 of 3, and B2 of 5, it'll cover the 2^2, a 3, and the 5. but the remaining 3^2 will be missed.

So in that case, B1=27 is needed to cover the 3^3, which incidentally takes care of the 5 also (as shown in the previous post) -- thus no need for a stage 2.

EDIT:- Algorithm

Scan the list for the largest and second largest prime factor (ignoring power).
If largest has a power > 1 (very rare), set B1=B2=large^power. Stop. (only stage 1 can find this one. stage 2 not needed)
Set B2 = large
Set B1 = second large.
for all the factors other then large, if factor^power > B1, set B1 = factor^power
if B1 > B2, set B2 = B1 (stage 1 bound subsumes stage 2 bound. only stage 1 is needed).

Last fiddled with by axn on 2012-02-03 at 13:23 Reason: tags

 2012-02-03, 13:23 #1115 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 13×491 Posts The B2 step (at least the cleverer B2 step in gmp-ecm) does not account for non-trivial powers of a prime. Which is why the code below doesn't find the factor until B2 contains p^2 Code: driver@tractor:/home/nfsworld/aliquot$echo "70*65537^2+1" | ecm -pm1 -c 1 1e4 1e9 GMP-ECM 6.2 [powered by GMP 4.3.2] [P-1] Input number is 70*65537^2+1 (12 digits) Using B1=10000, B2=1024792678, polynomial x^1, x0=2755809201 Step 1 took 0ms Step 2 took 80ms driver@tractor:/home/nfsworld/aliquot$ echo "70*65537^2+1" | ecm -pm1 -c 1 1e4 1e11 GMP-ECM 6.2 [powered by GMP 4.3.2] [P-1] Input number is 70*65537^2+1 (12 digits) Using B1=10000, B2=117865359558, polynomial x^1, x0=2752419731 Step 1 took 0ms ********** Factor found in step 2: 300656885831 Found input number N
2012-02-03, 13:29   #1116
axn

Jun 2003

491910 Posts

Quote:
 Originally Posted by fivemack The B2 step (at least the cleverer B2 step in gmp-ecm) does not account for non-trivial powers of a prime. Which is why the code below doesn't find the factor until B2 contains p^2
Technically, a "pure" implementation shouldn't find it. Only a lazy implementation (which doesn't sieve out all the composites from the prime list) will find it. It is probably going to be hit and miss as to which prime powers are found (even if the prime power is < B2).

At least in P95, it attempts to only deal with pure primes (but prime pairing logic does let in others too).

EDIT:- Cute trick
Code:
echo 70*65537^^^^2+1 | ecm -pm1 -c 1 7e4 1e6
GMP-ECM 6.3.1 [configured with GMP 5.0.2, --enable-asm-redc] [P-1]
Input number is 70*65537^2+1 (12 digits)
Using B1=70000, B2=1589656, polynomial x^1, x0=1488548802
Step 1 took 16ms
Step 2 took 15ms
********** Factor found in step 2: 300656885831
Found input number N
Take care of 1 factor of 65537 using B1. The other will popup some where in stage 2

Last fiddled with by axn on 2012-02-03 at 13:42

2012-02-03, 14:57   #1117
bcp19

Oct 2011

7·97 Posts

Quote:
 Originally Posted by axn Where did you get this information? Neither 5,27 nor 5,9 will find this. A stage 1 bound of 27 is needed to find this. With B1=27, you'd use an exponent of 2^4*3^3*5^2*7*11*13*17*19*23, which'd find the factor.
Ok, I must be missing something. How does the P-1 'break out' 2^2*3^3*5 from what you list above?

2012-02-03, 16:37   #1118
axn

Jun 2003

491910 Posts

Quote:
 Originally Posted by bcp19 Ok, I must be missing something. How does the P-1 'break out' 2^2*3^3*5 from what you list above?
When you understand that, you'd have understood the P-1 algorithm.

2012-02-04, 00:47   #1119
James Heinrich

"James Heinrich"
May 2004
ex-Northern Ontario

3×1,109 Posts

Quote:
 Originally Posted by axn Stage 2 can't really do powers of prime factors. It can cover a single prime factor > B1 and <= B2. So the 3^3 will not be caught in Stage 2. It has to be caught in Stage 1.
Thank you for the explanation, very easy for even me to follow.

I have updated my code accordingly, and the smaller factor of M2011 now shows B1=B2=27.

 2012-02-05, 14:16 #1120 Mr. P-1     Jun 2003 7×167 Posts To do a stage 1 P-1, you start by choosing a composite number E then compute 3E-1. The method will then find a factor p if E is divisible by p-1. This will work for any E, not just smooth E. So for example if we chose E=66=2*3*11, then we would find the factor 23, but not the factor 19, even though 19-1 is smother than 23-1. The thing to realize is that the smoothness 'rule' isn't something inherent in the algorithm itself. Rather, it arises out of the optimisation of the algorithm. Every E power-smooth to some B1 is optimal in the sense that all other choices are either less likely to find a factor, more expensive to compute, or both. Stage 2 computes 3E*q for a range of different prime q and will find a factor p if any E*q is divisible by p-1. Again, the algorithm will work (in the sense that it will find these factors) for an arbitrary set of primes q, but it's only worth doing if it can be implemented efficiently, which it can on large blocks of consecutive primes. The "standard" P-1 then, chooses two bound, B1 and B2, computes E power-smooth to B1 for stage 1, and uses all primes q between B1 and B2 for stage 2. Variants on this are worth considering, for example one might compute E smooth to B1 but power-smooth to B2, or one might run stage 2 from 2 to B2 instead of from B1 to B2. The examples supplied above by axn and fivemack suggest that gmp-ecm does both.
 2012-02-05, 20:26 #1121 c10ck3r     Aug 2010 Kansas 547 Posts For the P-1 method, does the number have to be taken mod 2^P-1 each step, or could we compute, say, 3^50000, take that mod 2^P-1, and take it to the P power?
2012-02-05, 21:28   #1122
NBtarheel_33

"Nathan"
Jul 2008
Maryland, USA

5×223 Posts

Quote:
 Originally Posted by c10ck3r For the P-1 method, does the number have to be taken mod 2^P-1 each step, or could we compute, say, 3^50000, take that mod 2^P-1, and take it to the P power?
Given the size of the exponents p that we usually work with, 3^50000 ~ 10^23856 (mod 2^p - 1) is likely to simply be 3^50000 (i.e. modular reduction does nothing to reduce the size of 3^50000).

In practice, however, where 3^E is huge, modular reduction at each step is likely done for the same purpose for which it is done in an LL test: it keeps the size of the numbers involved from very quickly outgrowing the universe.