There are many "extensions" of P1. You still need the small terms, with all their powers, in your random expression, because many numbers (i.e. the "q1" in "q is a prime that divides m=2^p1, 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 P1, then you can try to do the GCD phase after a couple of iterations \(c_i=c_{i1}^{random\cdot big\cdot number}\). The chances are slim, but you may get lucky, and \(gcd(c_i1,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 20161125 at 05:21
