mersenneforum.org > Math Possible extension to P-1 Stage 2
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2021-06-16, 02:51 #1 JuanTutors     Mar 2004 22×33×5 Posts 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?
 2021-06-16, 07:01 #2 Zhangrc   "University student" May 2021 Beijing, China 2·3·13 Posts 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!)
 2021-06-16, 20:44 #3 JuanTutors     Mar 2004 22×33×5 Posts Ahh, I see my error. I was comparing 3^Mp-1 to 2^n-1 instead of 3^(2^n-1).
2021-06-17, 16:46   #4
LaurV
Romulan Interpreter

Jun 2011
Thailand

3·3,251 Posts

Quote:
 Originally Posted by JuanTutors 3^(2*E*p*(2^n-1))-1 mod Mp
Then you take the GCD step, and... what?

2021-06-17, 19:00   #5
JuanTutors

Mar 2004

22·33·5 Posts

Quote:
 Originally Posted by LaurV 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

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post LaurV Data 9 2019-04-14 00:13 vsuite GPU Computing 7 2017-07-10 20:45 D. B. Staple Factoring 2 2007-12-14 00:21 bsquared Factoring 9 2007-05-18 19:24 Matthias C. Noc PrimeNet 5 2004-08-25 15:42

All times are UTC. The time now is 08:43.

Tue Sep 21 08:43:48 UTC 2021 up 60 days, 3:12, 0 users, load averages: 0.99, 1.26, 1.36

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.