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

[Paul Eggert]

On 2025-05-18 02:07, Torbjörn Granlund wrote:

> I don't think is makes much sense to handle two 128-bit words in this
> code.  In fact, the use of uintmax_t was a mistake, it should use
> "unsigned long" or "unsigned long long" whichever is efficiently
> supported directly by the hardware.

Fine, but the 128-bit bug is independent of uintmax_t. Suppose we change 
factor.c to never use uintmax_t, and suppose we have a (theoretical but 
allowed) platform where unsigned long is 128 bits and where factor.c 
uses that type for its words. Then before my Saturday coreutils 
commit[1], this code in prime_p:

  /* We have already cast out small primes.  */
  if (n < (wide_uint) FIRST_OMITTED_PRIME * FIRST_OMITTED_PRIME)
    return true;

was incorrect. The problem is that when given 2**128 - 101, 
factor_using_pollard_rho generates 155 and tests it with prime_p, and 
the above code causes prime_p to incorrectly report that 155 is prime.


> While uintmax_t could be made to work also for the cases you report, it
> will be inefficient.
>
> A few months ago, I contributed a suggested new core factoring function
> to GNU coreutils, which is, IIRC, 2-3 times faster than the current code
> for the bignum range.  It uses GMP's mpn functions with "Montgomery
> multiplication".
>
> There were two problems with my new core code:
>
> 1. It will not work with mini-GMP, which I think is undesiable.
>
> 2. It did not optimise for smaller factoring tasks.  The fix for this
> would be to merge that from the current coreutils factor.c.

Thanks, I didn't know about all that. I plan to take a look at it.


[1]: 
https://git.savannah.gnu.org/cgit/coreutils.git/commit/?id=fe51b33859d2e7286425d6d5600288ce9ae43bd1