20210616, 02:51  #1 
Mar 2004
21F_{16} Posts 
Possible extension to P1 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 P1 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^n1 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^n1))1 mod Mp for such a value of n? 
20210616, 07:01  #2 
"University student"
May 2021
Beijing, China
2^{2}×5^{2} 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 subproducts for PRP either, unless you calculate modular inverses (higher complexity!)

20210616, 20:44  #3 
Mar 2004
3×181 Posts 
Ahh, I see my error. I was comparing 3^Mp1 to 2^n1 instead of 3^(2^n1).

20210617, 16:46  #4 
Romulan Interpreter
Jun 2011
Thailand
2630_{16} Posts 

20210617, 19:00  #5 
Mar 2004
3·181 Posts 
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.
https://mersenneforum.org/showthread.php?t=26863&page=2 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Extension request  LaurV  Data  9  20190414 00:13 
PCIE USB 3.0 Extension Cable  vsuite  GPU Computing  7  20170710 20:45 
Stage 1 with mprime/prime95, stage 2 with GMPECM  D. B. Staple  Factoring  2  20071214 00:21 
brent suyama extension in P1  bsquared  Factoring  9  20070518 19:24 
Stage 1 and stage 2 tests missing  Matthias C. Noc  PrimeNet  5  20040825 15:42 