mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Math (https://www.mersenneforum.org/forumdisplay.php?f=8)
-   -   Possible extension to P-1 Stage 2 (https://www.mersenneforum.org/showthread.php?t=26912)

 JuanTutors 2021-06-16 02:51

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?

 Zhangrc 2021-06-16 07:01

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

 JuanTutors 2021-06-16 20:44

Ahh, I see my error. I was comparing 3^Mp-1 to 2^n-1 instead of 3^(2^n-1).

 LaurV 2021-06-17 16:46

[QUOTE=JuanTutors;581108] 3^(2*E*p*(2^n-1))-1 mod Mp [/QUOTE]
Then you take the GCD step, and... what?

 JuanTutors 2021-06-17 19:00

[QUOTE=LaurV;581254]Then you take the GCD step, and... what?[/QUOTE]

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.