News for hackers. Stuff that matters.
Re:The keys to the keydom by sparky_z on Sunday October 27, 2013 @09:22PM (#6624525)
1. Multiply all of the keys together: Y= X1 * X2 * ... * Xn.

2. For each key, Xi, use Euclid's algorithm to find the gcd of Xi and (Y/Xi). If the gcd of Xi is greater than 1, then you've factored Xi.

Even taking into account the arbitrary-size int arithmetic, this is more efficient then performing Euclid's algorithm on each pair (Xi, Xj) because gcds are so much more expensive then multiplications. N multiplications and n gcds on enormous ints is faster than n^2 - n gcds with 1024 bit ints.

There are no comments on this comment yet.