20120203, 10:55  #1112 
Dec 2003
Paisley Park & Neverland
5×37 Posts 
Oh! worktodo got somewhat corrupted... I guess I should have seen that earlier.

20120203, 12:38  #1113  
"James Heinrich"
May 2004
exNorthern Ontario
3327_{10} Posts 
Quote:
Now I've been told that B2 should be the largest [forgive probablywrong math term] powered prime factor, and B1 the secondlargest, so chosing between 2^{2}=4, 3^{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^{3} > 5^{1}) should that override the minimum B1? 

20120203, 13:14  #1114  
Jun 2003
4,919 Posts 
Quote:
Quote:
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:
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 20120203 at 13:23 Reason: tags 

20120203, 13:23  #1115 
(loop (#_fork))
Feb 2006
Cambridge, England
13×491 Posts 
The B2 step (at least the cleverer B2 step in gmpecm) does not account for nontrivial 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 GMPECM 6.2 [powered by GMP 4.3.2] [P1] 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 GMPECM 6.2 [powered by GMP 4.3.2] [P1] 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 
20120203, 13:29  #1116  
Jun 2003
4919_{10} Posts 
Quote:
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 GMPECM 6.3.1 [configured with GMP 5.0.2, enableasmredc] [P1] 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 Last fiddled with by axn on 20120203 at 13:42 

20120203, 14:57  #1117 
Oct 2011
7·97 Posts 
Ok, I must be missing something. How does the P1 'break out' 2^2*3^3*5 from what you list above?

20120203, 16:37  #1118 
Jun 2003
4919_{10} Posts 

20120204, 00:47  #1119  
"James Heinrich"
May 2004
exNorthern Ontario
3×1,109 Posts 
Quote:
I have updated my code accordingly, and the smaller factor of M2011 now shows B1=B2=27. 

20120205, 14:16  #1120 
Jun 2003
7×167 Posts 
To do a stage 1 P1, 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 p1. 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 191 is smother than 231.
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 powersmooth 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 p1. 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" P1 then, chooses two bound, B1 and B2, computes E powersmooth 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 powersmooth 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 gmpecm does both. 
20120205, 20:26  #1121 
Aug 2010
Kansas
547 Posts 
For the P1 method, does the number have to be taken mod 2^P1 each step, or could we compute, say, 3^50000, take that mod 2^P1, and take it to the P power?

20120205, 21:28  #1122  
"Nathan"
Jul 2008
Maryland, USA
5×223 Posts 
Quote:
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. 
