Dana Jacobsen

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.

Back in 2013, I wrote Factoring integers in Perl. My goal then was practical factoring of 50–80 digit numbers from Perl. The GMP backend had recently gained a quadratic sieve based on William Hart’s SIMPQS implementation.

That code served the module for more than a decade. My port left out some features that mattered for larger inputs, but it worked well enough that writing a replacement kept slipping down the list.

In 2024, Hugo van der Sanden submitted an improved version, SIMPQS2. He addressed the things I’d been concerned about since 2013: combining useful partial results, a better solver for the final stage, and lower memory use. In August this year, he reminded me that I’d been sitting on his work for too long. I integrated it, and it was much better. His contribution also finally got me moving on the implementation I’d been thinking about for years.

The result was a new SIQS -- Self-Initializing Quadratic Sieve. It handles both the smaller inputs previously covered by the separate TinyQS implementation and the larger ones handled by SIMPQS. Hugo’s SIMPQS2 became an important development checkpoint, although it never appeared in a released module version.

Here’s how those implementations compare:

These tests use numbers made from two similarly sized primes: difficult factoring inputs that give the quadratic sieve some real work. Each implementation received the same inputs, using one thread on an M1 MacBook. The timings measure direct C calls to the quadratic-sieve implementations, excluding startup and the general factor() strategy.

The new implementation is faster across the old implementation’s useful range, and continues well beyond it. The memory comparison is encouraging too. The evolution notes have the history and measurement details.

Once it was working well against our older code, I started comparing it with other factoring programs. That was where things got surprising.

I expected a useful improvement for the Perl module. I hadn’t expected it to do so well against established SIQS implementations, including on machines other than my MacBook. There’s no hand-written assembly or explicit SIMD code in it, while YAFU has carefully optimized assembly and SIMD code on x86.

At that point, it seemed worth giving the implementation its own home. That became msiqs: a C/GMP library and command-line program, with support for multiple threads and saving work so an interrupted run can resume. Rather than mixing Perl threads and C pthreads, I chose to make the Perl module serial but thread-safe. You can run independent jobs concurrently using Perl threads or MCE.

For one example, the standalone program factored RSA-100, a 100-digit number, in about four minutes and 43 seconds using eight threads on my 2021 M1 Pro laptop. I put some comparisons in the first announcement on mersenneforum.org. Both msiqs and YAFU are being actively developed; Ben Buhrow’s new L2sieve work has already made those comparisons more interesting.

I’ve learned a great deal from earlier implementations and their authors. Hugo’s contribution was especially important in getting this work started. I also used OpenAI Codex extensively: discussing algorithms, implementing ideas, reviewing code, debugging, and running experiments. That has been quite a change from my usual development process.

For Perl users, this brings better factoring behind an existing interface. For anyone curious about how far that work went, msiqs has the code, benchmarks, and implementation notes.