mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > PrimeNet

Reply
 
Thread Tools
Old 2012-02-03, 10:55   #1112
MrHappy
 
MrHappy's Avatar
 
Dec 2003
Paisley Park & Neverland

5×37 Posts
Default

Oh! worktodo got somewhat corrupted... I guess I should have seen that earlier.
MrHappy is offline   Reply With Quote
Old 2012-02-03, 12:38   #1113
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

332710 Posts
Default

Quote:
Originally Posted by axn View Post
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?
James Heinrich is offline   Reply With Quote
Old 2012-02-03, 13:14   #1114
axn
 
axn's Avatar
 
Jun 2003

4,919 Posts
Default

Quote:
Originally Posted by James Heinrich View Post
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 View Post
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 View Post
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
axn is online now   Reply With Quote
Old 2012-02-03, 13:23   #1115
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

13×491 Posts
Default

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
fivemack is offline   Reply With Quote
Old 2012-02-03, 13:29   #1116
axn
 
axn's Avatar
 
Jun 2003

491910 Posts
Default

Quote:
Originally Posted by fivemack View Post
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
axn is online now   Reply With Quote
Old 2012-02-03, 14:57   #1117
bcp19
 
bcp19's Avatar
 
Oct 2011

7·97 Posts
Default

Quote:
Originally Posted by axn View Post
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?
bcp19 is offline   Reply With Quote
Old 2012-02-03, 16:37   #1118
axn
 
axn's Avatar
 
Jun 2003

491910 Posts
Default

Quote:
Originally Posted by bcp19 View Post
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.
axn is online now   Reply With Quote
Old 2012-02-04, 00:47   #1119
James Heinrich
 
James Heinrich's Avatar
 
"James Heinrich"
May 2004
ex-Northern Ontario

3×1,109 Posts
Default

Quote:
Originally Posted by axn View Post
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.
James Heinrich is offline   Reply With Quote
Old 2012-02-05, 14:16   #1120
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7×167 Posts
Default

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.
Mr. P-1 is offline   Reply With Quote
Old 2012-02-05, 20:26   #1121
c10ck3r
 
c10ck3r's Avatar
 
Aug 2010
Kansas

547 Posts
Default

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?
c10ck3r is offline   Reply With Quote
Old 2012-02-05, 21:28   #1122
NBtarheel_33
 
NBtarheel_33's Avatar
 
"Nathan"
Jul 2008
Maryland, USA

5×223 Posts
Default

Quote:
Originally Posted by c10ck3r View Post
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.
NBtarheel_33 is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 11:31.

Tue Apr 20 11:31:33 UTC 2021 up 12 days, 6:12, 0 users, load averages: 1.58, 1.81, 1.90

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.