Subject: bug#78476: closed (Re: bug#78476: GNU 'factor' problems with 128-bit word)

From: [email-masked] (GNU bug Tracking System)
Date: Sun, 27 Jul 2025 14:43:03 +0000

Your bug report

#78476: GNU 'factor' problems with 128-bit word

which was filed against the coreutils package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
78476: https://debbugs.gnu.org/cgi/bugreport.cgi?bug=78476
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#78476: GNU 'factor' problems with 128-bit word
From: Paul Eggert <[email-masked]>
To: Torbjörn Granlund <[email-masked]>
Cc: [email-masked], [email-masked]
Date: Sun, 27 Jul 2025 07:42:30 -0700
List-Id: <debbugs-submit.debbugs.gnu.org>

On 2025-07-27 01:51, Torbjörn Granlund wrote:
> Thank you for merging the new mpn-based factoring code!
> 
> The code looks good, I did not see anything which needs improvements.
> 
> I believe the factoring speedup for numbers of 3 or more limb is quite
> significant (2x-3x), even when not considering the time saved by not
> proving primality of found factors.
> 
> You might want mention that in the header about the 2025 improvements.

Thanks for the review and for the kind words. I installed the attached 
further doc fix and am closing this bug report.
From 4a2402dcfa8b705b63f43b76d7be8418e08f8f8f Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email-masked]>
Date: Sun, 27 Jul 2025 07:30:29 -0700
Subject: [PATCH] doc: mention 2025 speedup on large composites

---
 NEWS         | 3 ++-
 src/factor.c | 3 ++-
 2 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/NEWS b/NEWS
index 17a43b064..0b2be7116 100644
--- a/NEWS
+++ b/NEWS
@@ -4,7 +4,8 @@ GNU coreutils NEWS                                    -*- outline -*-
 
 ** Changes in behavior
 
-  'factor' is now much faster at identifying large prime numbers.
+  'factor' is now much faster at identifying large prime numbers,
+  and significantly faster on composite numbers greater than 2^128.
 
 ** Bug fixes
 
diff --git a/src/factor.c b/src/factor.c
index 44c0deb6a..b3af25b5f 100644
--- a/src/factor.c
+++ b/src/factor.c
@@ -19,7 +19,8 @@
    Arbitrary-precision code adapted by James Youngman from Torbjörn
    Granlund's factorize.c, from GNU MP version 4.2.2.
    In 2012, the core was rewritten by Torbjörn Granlund and Niels Möller.
-   In 2025, Torbjörn Granlund and Paul Eggert sped up primality checking.
+   In 2025, Torbjörn Granlund and Paul Eggert sped up primality checking,
+   and improved performance on composite numbers greater than 2^128.
    Contains code from GNU MP.  */
 
 /* Efficiently factor numbers that fit in one or two words (word = mp_limb_t),
-- 
2.48.1

Subject: GNU 'factor' problems with 128-bit word
From: Paul Eggert <[email-masked]>
To: Coreutils bugs <[email-masked]>
Cc: Torbjorn Granlund <[email-masked]>
Date: Sun, 18 May 2025 00:39:38 -0700
List-Id: <debbugs-submit.debbugs.gnu.org>

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.