mersenneforum.org  

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

Closed Thread
 
Thread Tools
Old 2020-12-14, 21:05   #1
ZFR
 
ZFR's Avatar
 
Feb 2008
Bray, Ireland

14010 Posts
Default Question about selection of a in the P-1 algorithm

From https://www.mersenne.org/various/math.php

Quote:
The P-1 method is quite simple. In stage 1 we pick a bound B1. P-1 factoring will find the factor q as long as all factors of k are less than B1 (k is called B1-smooth). We compute E – the product of all primes less than B1. Then we compute x = 3E*2*P. Finally, we check the GCD (x-1, 2P-1) to see if a factor was found.
When computing x, why are we taking 3E*2*P instead of 2E*2*P?

Wouldn't any coprime number do? If so, why not choose the smaller one?

Last fiddled with by ZFR on 2020-12-14 at 21:13
ZFR is online now  
Old 2020-12-15, 00:53   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5×172 Posts
Default

The reason: 2^(E*2*p)==1 mod 2^p-1.
R. Gerbicz is offline  
Old 2020-12-15, 01:30   #3
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

13×379 Posts
Default

Quote:
Originally Posted by ZFR View Post
From https://www.mersenne.org/various/math.php

When computing x, why are we taking 3E*2*P instead of 2E*2*P?

Wouldn't any coprime number do? If so, why not choose the smaller one?
E is not just the product of the primes < B1, it's the product of maximum integral powers of each prime fitting < B1 individually, called powersmooth.
The exponentiation aE*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 small-numbers example early in https://magazine.odroid.com/article/...tical-history/ Later on, this same source includes, also in the context of primality testing, rather than P-1 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 base-2 pseudoprimes, irrespective of whether they are
prime or composite. The two best-known such classes are, firstly, the 
Mersenne numbers M(p) = 2p−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, 211−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 2020-12-15 at 01:35
kriesel is offline  
Old 2020-12-15, 08:44   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

927510 Posts
Default

Quote:
Originally Posted by kriesel View Post
the product of maximum integral powers of each prime fitting < B1 individually
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 2020-12-15 at 08:45
LaurV is offline  
Old 2020-12-15, 09:36   #5
ZFR
 
ZFR's Avatar
 
Feb 2008
Bray, Ireland

22·5·7 Posts
Default

Ah, OK. So for base a=2 we'll have pseudoprimes only because 2^(E*2*p) is always 1 mod 2^p-1

Thanks, everyone.

Thanks for the article link, kriesel.
ZFR is online now  
Old 2020-12-15, 21:28   #6
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

13×379 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
Instead of criticizing from the stands, try entering the arena. "It is not the critic who counts; not the man who points out how the strong man stumbles, or where the doer of deeds could have done them better. The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood; who strives valiantly; who errs, who comes short again and again, because there is no effort without error and shortcoming; but who does actually strive to do the deeds; who knows great enthusiasms, the great devotions; who spends himself in a worthy cause; who at the best knows in the end the triumph of high achievement, and who at the worst, if he fails, at least fails while daring greatly, so that his place shall never be with those cold and timid souls who neither know victory nor defeat."
https://www.mentalfloss.com/article/...elts-man-arena
kriesel is offline  
Old 2020-12-15, 23:30   #7
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

2×33×5×43 Posts
Default

@OP: Suggest you try a tiny M(p) example: n = M(11) = 2^11-1 = 23*89. The 2 prime factors have p-1 decompositions:

p = 23: p-1 = 2*11
q = 89: q-1 = 2^3*11

So taking E = 2*11 in p-1 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 2020-12-15 at 23:54 Reason: Used onmodded-E in my first go - revised as exercise.
ewmayer is offline  
Old 2020-12-16, 10:29   #8
jnml
 
Feb 2012
Prague, Czech Republ

132 Posts
Default

Quote:
Originally Posted by kriesel View Post
Instead of criticizing from the stands, try entering the arena. "It is not the critic who counts; not the man who points out how the strong man stumbles, or where the doer of deeds could have done them better. The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood; who strives valiantly; who errs, who comes short again and again, because there is no effort without error and shortcoming; but who does actually strive to do the deeds; who knows great enthusiasms, the great devotions; who spends himself in a worthy cause; who at the best knows in the end the triumph of high achievement, and who at the worst, if he fails, at least fails while daring greatly, so that his place shall never be with those cold and timid souls who neither know victory nor defeat."
https://www.mentalfloss.com/article/...elts-man-arena
Please don't overreact. AFAICS, LaurV's comment talked about no _person_ at all and
I believe having opinions about _ideas_ is always fine.
jnml is offline  
Old 2020-12-16, 10:32   #9
ZFR
 
ZFR's Avatar
 
Feb 2008
Bray, Ireland

22·5·7 Posts
Default

Quote:
Originally Posted by ewmayer View Post
@OP: Suggest you try a tiny M(p) example: n = M(11) = 2^11-1 = 23*89. The 2 prime factors have p-1 decompositions:

p = 23: p-1 = 2*11
q = 89: q-1 = 2^3*11

So taking E = 2*11 in p-1 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.
Thanks.

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^p-1.
imply that
gcd(2^(E*2*p)-1, 2^p-1) = 2^p -1

Last fiddled with by ZFR on 2020-12-16 at 10:35
ZFR is online now  
Old 2020-12-16, 10:37   #10
axn
 
axn's Avatar
 
Jun 2003

4,861 Posts
Default

Quote:
Originally Posted by ZFR View Post
How does
2^(E*2*p)==1 mod 2^p-1.
imply that
gcd(2^(E*2*p)-1, 2^p-1) = 2^p -1
2^(E*2*p)==1 mod 2^p-1
==>
2^(E*2*p)-1 == 0 mod 2^p-1

Therefore gcd(2^(E*2*p)-1, 2^p-1) = gcd(0, 2^p-1) = 2^p-1
axn is offline  
Old 2020-12-16, 10:53   #11
ZFR
 
ZFR's Avatar
 
Feb 2008
Bray, Ireland

22·5·7 Posts
Default

Quote:
Originally Posted by axn View Post
2^(E*2*p)==1 mod 2^p-1
==>
2^(E*2*p)-1 == 0 mod 2^p-1

Therefore gcd(2^(E*2*p)-1, 2^p-1) = gcd(0, 2^p-1) = 2^p-1
OK, thanks for explaining. Yeah, it's pretty basic, I can be blind at times.

One last question: when Prime95 does the P-1 algorithm, that time-consuming part of it would be the exponentiation of 3 (and modulo n)? The gcd itself is pretty fast comparatively, right?
ZFR is online now  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sin/cos algorithm question #2 Prime95 Programming 6 2020-07-15 06:09
Karatsuba algorithm relation to Matrix Multiplication (Strassen Algorithm)? neomacdev Computer Science & Computational Number Theory 1 2019-07-30 01:40
Polynomial selection stage question rawbinary Msieve 12 2010-08-02 23:41
Any ideas on v26 FFT selection algorithm? Prime95 Software 20 2010-06-25 23:35
Motherboard Selection Help jugbugs Hardware 13 2004-06-04 15:59

All times are UTC. The time now is 15:25.

Sun Mar 7 15:25:46 UTC 2021 up 94 days, 11:37, 1 user, load averages: 1.75, 1.73, 1.58

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.