20201214, 21:05  #1  
Feb 2008
Bray, Ireland
139 Posts 
Question about selection of a in the P1 algorithm
From https://www.mersenne.org/various/math.php
Quote:
Wouldn't any coprime number do? If so, why not choose the smaller one? Last fiddled with by ZFR on 20201214 at 21:13 

20201215, 00:53  #2 
"Robert Gerbicz"
Oct 2005
Hungary
1442_{10} Posts 
The reason: 2^(E*2*p)==1 mod 2^p1.

20201215, 01:30  #3  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
3^{2}×5×109 Posts 
Quote:
The exponentiation a^{E*2*p} is done mod Mp. So smaller a doesn't really save run time, or operand size after relatively few operations. In practice the exponentiation is done with a full length fft transform from the start, so it saves no run time to use a smaller base. https://en.wikipedia.org/wiki/Pollar...92_1_algorithm As to why not 2 instead of 3, there's a smallnumbers example early in https://magazine.odroid.com/article/...ticalhistory/ Later on, this same source includes, also in the context of primality testing, rather than P1 factoring, the following: Code:
In the more general context of testing numbers of arbitrary size, however, it is important to realize that there are certain classes of numbers, all of which are Fermat base2 pseudoprimes, irrespective of whether they are prime or composite. The two bestknown such classes are, firstly, the Mersenne numbers M(p) = 2^{p}−1 (for which we restrict the definition to prime exponents since that is required for a number of this form to have a chance of being prime); for example, 2^{11}−1 passes the test even though it factors as 23 × 89. The second class of such numbers is the Fermat numbers Last fiddled with by kriesel on 20201215 at 01:35 

20201215, 08:44  #4 
Romulan Interpreter
Jun 2011
Thailand
5×17×109 Posts 
Haha, so complicate said. E is the LCM(x such as x<=B1). The "power trick" just happens to be the fastest known way to calculate it.
Last fiddled with by LaurV on 20201215 at 08:45 
20201215, 09:36  #5 
Feb 2008
Bray, Ireland
139 Posts 
Ah, OK. So for base a=2 we'll have pseudoprimes only because 2^(E*2*p) is always 1 mod 2^p1
Thanks, everyone. Thanks for the article link, kriesel. 
20201215, 21:28  #6  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
3^{2}·5·109 Posts 
Quote:
https://www.mentalfloss.com/article/...eltsmanarena 

20201215, 23:30  #7 
∂^{2}ω=0
Sep 2002
República de California
2·7·829 Posts 
@OP: Suggest you try a tiny M(p) example: n = M(11) = 2^111 = 23*89. The 2 prime factors have p1 decompositions:
p = 23: p1 = 2*11 q = 89: q1 = 2^3*11 So taking E = 2*11 in p1 stage 1 should turn up the smaller factor, i.e. in this case we don't even need any of the other smaller primes, just the 2*p bit, in E. Try it to the 2 bases in question and see what happens. Last fiddled with by ewmayer on 20201215 at 23:54 Reason: Used onmoddedE in my first go  revised as exercise. 
20201216, 10:29  #8  
Feb 2012
Prague, Czech Republ
13^{2} Posts 
Quote:
I believe having opinions about _ideas_ is always fine. 

20201216, 10:32  #9  
Feb 2008
Bray, Ireland
139 Posts 
Quote:
gcd(4194303, 2047) = 2047 gcd(31381059608, 2047) = 23 So using base 2 gives us n, while using base 3 gives us the right answer. I played around with some other Mersenne numbers. The gcd always returns n. I might be overlooking something very obvious here, but I'm still missing one step. How does 2^(E*2*p)==1 mod 2^p1. imply that gcd(2^(E*2*p)1, 2^p1) = 2^p 1 Last fiddled with by ZFR on 20201216 at 10:35 

20201216, 10:37  #10 
Jun 2003
1001011111000_{2} Posts 

20201216, 10:53  #11  
Feb 2008
Bray, Ireland
139 Posts 
Quote:
One last question: when Prime95 does the P1 algorithm, that timeconsuming part of it would be the exponentiation of 3 (and modulo n)? The gcd itself is pretty fast comparatively, right? 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Sin/cos algorithm question #2  Prime95  Programming  6  20200715 06:09 
Karatsuba algorithm relation to Matrix Multiplication (Strassen Algorithm)?  neomacdev  Computer Science & Computational Number Theory  1  20190730 01:40 
Polynomial selection stage question  rawbinary  Msieve  12  20100802 23:41 
Any ideas on v26 FFT selection algorithm?  Prime95  Software  20  20100625 23:35 
Motherboard Selection Help  jugbugs  Hardware  13  20040604 15:59 