P-1 factoring anyone?

[MrHappy]

Oh! worktodo got somewhat corrupted... I guess I should have seen that earlier.

[James Heinrich]

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 = 2³ × 3³ × 5 × 2011. Then stripping out the exponent (2011) and a 2, you're left with 2² × 3³ × 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 2²=4, 3³=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 (3³ > 5¹) should that override the minimum B1?

[axn]

Originally Posted by James Heinrich

The smaller factor (2171881) is split up (per my standard k-value practice) into 2171881 - 1 = 2³ × 3³ × 5 × 2011. Then stripping out the exponent (2011) and a 2, you're left with 2² × 3³ × 5.

So far, so good.

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 2²=4, 3³=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...

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 (3³ > 5¹) 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).

[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

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

[axn]

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

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

[bcp19]

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?

[axn]

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.

[James Heinrich]

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.

[Mr. P-1]

To do a stage 1 P-1, you start by choosing a composite number E then compute 3^E-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 3^E*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.

[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?

[NBtarheel_33]

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.