I recently found out that GNU coreutils 'factor' misbehaves if its
internal word is 128 bits rather than the usual 64. This could happen if
one builds Coreutils 9.7 on a platform with 128-bit uintmax_t, something
that POSIX allows (though it's only theoretical now as far as I know).
The problem occurs when src/factor.c's prime_p function assumes that as
a quick test, its argument N must be prime if N is less than
FIRST_OMITTED_PRIME * FIRST_OMITTED_PRIME. I guess this quick-test
assumption is true for 64-bit uintmax_t, but not for 128-bit.
I worked around the bug by installed a patch
<https://git.savannah.gnu.org/cgit/coreutils.git/commit/?id=fe51b33859d2e7286425d6d5600288ce9ae43bd1>.
This patch changes prime_p to rely on the quick-test assumption only
when the internal word size is 64 bits. On platforms with wider words,
the code now tests smaller numbers for primes too; this works around the
bug, but is slower.
It'd be nice if the underlying problem were fixed, so that the code is
more portable to 128-bit word.
The issue might be related to Bug#25135 "Infinite loop in factor"
<https://bugs.gnu.org/25135> so I am cc'ing this to Torbjörn. The
current factor.c is not the same as what Torbjörn contributed years ago
so it is of course possible that I or someone else introduced the bug
more recently.
To reproduce the problem on Fedora 42 x86-64:
git clone https://git.savannah.gnu.org/git/coreutils.git
cd coreutils
git checkout fe51b33859d2e7286425d6d5600288ce9ae43bd1
./bootstrap
./configure
make CFLAGS='-DUSE_INT128 -DEXHIBIT_INT128_BUG' WERROR_CFLAGS=
echo 340282366920938463463374607431768211355 | src/factor
The output is:
340282366920938463463374607431768211355: 155
2195370109167344925570158757624311041
which is wrong, as 155 is not prime.
