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