View Single Post
Old 2016-11-25, 05:14   #2
Romulan Interpreter
LaurV's Avatar
Jun 2011

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
LaurV is offline   Reply With Quote