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

[Paul Eggert]

On 5/19/25 15:23, Torbjörn Granlund wrote:
> Paul Eggert <eggert@cs.ucla.edu> writes:
>
>    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.
>
> Why is it incorrect?

Because when you run it on a machine with 128-bit unsigned long (or 
whatever type is being used for the word size), N can be 155 and 155 is 
not prime.


> I actually find it extremely worrying that a change is motivated by "We
> don't know why the code misbehaves when wide_uint is wider;" and then
> the presumed bug is masked with a pretty questionable change.  Really?

The change is questionable only because it hurts performance when the 
word size exceeds 64 bits. It's not questionable on correctness grounds. 
And it doesn't affect performance in the usual 64-bit case.


> How about debugging it?

Yes, that'd be better and that's why I filed the bug report. However, 
what's a good way to debug it?

My *guess* is that prime_p is sometimes called in a context where it's 
already guaranteed that we have cast out small primes, and it's 
sometimes called in a context where there is no such guarantee. The 
latter context is the bug. It appears that this context can occur in 
factor_using_pollard_rho (n, a, factors), which contains this code after 
the "factor_found:" label:

      if (!prime_p (g))
        factor_using_pollard_rho (g, a + 1, factors);
      else
        factor_insert (factors, g);

If I understand things correctly, there's no guarantee here that G 
cannot be a small prime, which means factor_insert can be called even 
when G is not prime, and that is a bug.


> Let's use our time and effort on improving things for the word we live
> in.

That would be reasonable if we knew that the existing code works for all 
cases in 64 bits. Is there some way to show that? (We can't exhaustively 
test it.)

Even a comment would be helpful. And, if the code is not designed to 
work with any word size other than 64 bits, there should be a static 
check to that effect. (There's already a static check that words must be 
at least 64 bits.)