-   Math (
-   -   Possible extension to P-1 Stage 2 (

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.


All times are UTC. The time now is 23:45.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.