GPU and Random P-1

[jocelynl]

Has anyone ever done any work on random P-1

3^{random 0's and 1's}@(2^p-1)

Where every n iteration you do a GCD (B-1,2^p-1)

Now that there are many thousands GPU working on distributed computing.
(working at B1 level only would not take that much RAM.)

Now that many numbers are out of reach of NFS or even ECM. Would that be an avenue?
or is too much of a lottery just to find one.

[LaurV]

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").