Thread: GPU and Random P-1 View Single Post
 2016-11-25, 05:14 #2 LaurV Romulan Interpreter     Jun 2011 Thailand 34·113 Posts There are many "extensions" of P-1. You still need the small terms, with all their powers, in your random expression, because many numbers (i.e. the "q-1" in "q is a prime that divides m=2^p-1, with prime p") have lots of small factors. You may, for a random base b which is not a power of 2, compute $$c=b^E$$, where $$E$$ is the product we use in stage 1 of P-1, then you can try to do the GCD phase after a couple of iterations $$c_i=c_{i-1}^{random\cdot big\cdot number}$$. The chances are slim, but you may get lucky, and $$gcd(c_i-1,m)$$ reveal a factor of m, or m itself (in which case a factor can be found by "backtracking"). Last fiddled with by LaurV on 2016-11-25 at 05:21