]> git.ipfire.org Git - thirdparty/coreutils.git/commit
factor: speed up multiprecision Pollard’s rho
authorPaul Eggert <eggert@cs.ucla.edu>
Wed, 11 Jun 2025 00:40:34 +0000 (17:40 -0700)
committerPaul Eggert <eggert@cs.ucla.edu>
Thu, 10 Jul 2025 00:12:39 +0000 (17:12 -0700)
commit442c164ae043b58c1aeced3816dbed55a67ca99c
treef570f2fad851d48902ea86cb15cc0f980108f799
parent54a2d18b1f47fe6d5e663bacb2bd8971f7a58a49
factor: speed up multiprecision Pollard’s rho

These changes are taken from a proposal by Torbjörn Granlund in:
https://lists.gnu.org/r/coreutils/2025-01/msg00000.html
On my x86-64 platform, they improve speed by more than 8× when
factoring 340282366920938463463374607431768211457.
* src/factor.c (mp_modadd, mp_modsub, mp_modadd_1, mp_mulredc):
New functions.
(MP_FACTOR_USING_POLLARD_RHO_N_MAX): New macro.
(mp_factor_using_pollard_rho): Act on mpn not mpz, and on
mp_limb_t not unsigned long int.  Reorder args.  All uses changed.
src/factor.c