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 13×43 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 11111102 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 13×43 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

24×613 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

13×43 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 12:39.

Thu Dec 2 12:39:41 UTC 2021 up 132 days, 7:08, 0 users, load averages: 1.48, 1.48, 1.28