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     "Juan Tutors" Mar 2004 10001100002 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×53 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     "Juan Tutors" Mar 2004 23016 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

"name field"
Jun 2011
Thailand

100110111010102 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

"Juan Tutors"
Mar 2004

23016 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 15:04.

Sat May 21 15:04:07 UTC 2022 up 37 days, 13:05, 0 users, load averages: 1.20, 1.15, 1.23