mersenneforum.org > Math Possible extension to P-1 Stage 2
 Register FAQ Search Today's Posts Mark Forums Read

 2021-06-16, 02:51 #1 JuanTutors     Mar 2004 54010 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 北京 31 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×132×19 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

21C16 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.

 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 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