mersenneforum.org  

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

Reply
 
Thread Tools
Old 2021-06-16, 02:51   #1
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

54010 Posts
Default Possible extension to P-1 Stage 2

I know lots of these ideas come along, and I am getting more comfortable with the math involved with Stage 2 as I write this, so please forgive me if I missed something.

From what I understand, in the P-1 factoring stage 1, Given Mp, we calculate 3^(2*E*p)-1 mod Mp where E is the product of many powers of prime factors less than a number B1. In stage 2, for various primes q between B1 and B2, we then calculate 3^(2*E*p*q)-1 mod Mp.

Noting that every prime q divides 2^n-1 for some value of n (and in fact all integer multiples of n), would it be feasible in some cases to instead calculate 3^(2*E*p*(2^n-1))-1 mod Mp for such a value of n?
JuanTutors is offline   Reply With Quote
Old 2021-06-16, 07:01   #2
Zhangrc
 
"University student"
May 2021
北京

31 Posts
Default

That's right, but the extension is not economic. You need even more iterations to calculate it. Also you can't directly use your sub-products for PRP either, unless you calculate modular inverses (higher complexity!)
Zhangrc is online now   Reply With Quote
Old 2021-06-16, 20:44   #3
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

22×33×5 Posts
Default

Ahh, I see my error. I was comparing 3^Mp-1 to 2^n-1 instead of 3^(2^n-1).
JuanTutors is offline   Reply With Quote
Old 2021-06-17, 16:46   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

3×132×19 Posts
Default

Quote:
Originally Posted by JuanTutors View Post
3^(2*E*p*(2^n-1))-1 mod Mp
Then you take the GCD step, and... what?
LaurV is offline   Reply With Quote
Old 2021-06-17, 19:00   #5
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

21C16 Posts
Default

Quote:
Originally Posted by LaurV View Post
Then you take the GCD step, and... what?
I did realize my error as I explained above but I did post in another thread by Zhangrc a more correct modification of this test. I'll reply there.

https://mersenneforum.org/showthread.php?t=26863&page=2
JuanTutors is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Extension request LaurV Data 9 2019-04-14 00:13
PCI-E USB 3.0 Extension Cable vsuite GPU Computing 7 2017-07-10 20:45
Stage 1 with mprime/prime95, stage 2 with GMP-ECM D. B. Staple Factoring 2 2007-12-14 00:21
brent suyama extension in P-1 bsquared Factoring 9 2007-05-18 19:24
Stage 1 and stage 2 tests missing Matthias C. Noc PrimeNet 5 2004-08-25 15:42

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


Sun Jul 25 07:25:56 UTC 2021 up 2 days, 1:54, 0 users, load averages: 1.56, 2.25, 2.15

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.