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

22216 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
Beijing, China

22×33 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

2·3·7·13 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

9,787 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 online now   Reply With Quote
Old 2021-06-17, 19:00   #5
JuanTutors
 
JuanTutors's Avatar
 
Mar 2004

2×3×7×13 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 01:08.


Sat Oct 23 01:08:55 UTC 2021 up 91 days, 19:37, 0 users, load averages: 1.28, 1.31, 1.29

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.