Factoring integers in Perl, thirteen years later
I’ve been working again on faster integer factoring in my Perl module Math::Prime::Util::GMP. My latest work grew into msiqs, a standalone factoring program that is competitive with specialized software I've been recommending for years, such as YAFU.
But first, what does this mean for Perl users?
The upcoming Math::Prime::Util::GMP 0.55 replaces its old quadratic sieve with a new implementation. For the difficult numbers where this algorithm is useful, factoring gets considerably faster, uses less memory, and works at larger sizes. You get those improvements through the familiar Math::Prime::Util interface:
use Math::Prime::Util qw(factor);
my $n = "861718837045131266076605675795055735226483972739042530561207";
print join(" * ", factor($n)), "\n";
Math::Prime::Util automatically uses its optional GMP backend when installed. Passing a large integer as a decimal string is fine; you don’t need to construct a Math::BigInt object just to factor it. The factoring code is written in C, with GMP handling the large integers.