A fun property of Pollard-Brent's factorization algorithm

Primes, divisors, arithmetic, number properties, ...
Post Reply
nightcracker
Posts: 3
Joined: Sun Jan 02, 2011 9:30 pm

A fun property of Pollard-Brent's factorization algorithm

Post by nightcracker » Mon Jan 12, 2015 12:15 pm

As some of you know, you can speed up repeated modular multiplication using Montgomery reduction. The conversion takes some time, but if you do quite some multiplications it should speed up by a lot. At first look Pollard-Brent doesn't seem like it could benefit that much from this, since it doesn't do too many modular multiplications in a row, so you'd think you'd spend too much time converting back and forth.

However, as it turns out, absolutely no conversions are needed! The initial random parameters are supposed to be uniform over [1, N), so there's absolutely no reason to convert them - the result would be another uniform random variable over [1, N). So we'll just generate random parameters as usual, and treat them as if they were of the form aR mod N. Then in the algorithm you replace all multiplications with Montgomery multiplication.

I don't know exactly how the end result is still correct, but it I think just so happens to be because you are working with aR mod N and R and N are coprime, thus not affecting the algorithm logic which checks gcd(aR mod N, N) = 1.

Either way, here's some code implementing this (sorry, only GCC on x86-64 because I need inline assembly): http://coliru.stacked-crooked.com/a/f57f11426d06acd8

This trick made the implementation 4 times faster.

Post Reply