GNU bug report logs - #78476
GNU 'factor' problems with 128-bit word

Previous Next

Full log

View this message in rfc822 format

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: 78476 <at> debbugs.gnu.org
Cc: Torbjorn Granlund <tg <at> gmplib.org>
Subject: bug#78476: GNU 'factor' problems with 128-bit word
Date: Sun, 18 May 2025 00:39:38 -0700

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.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.