Wraparound multiplicaton vs mullo

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> nisse at lysator.liu.se (Niels Möller) writes:
>
>   Nut it *is* mod 2^n - 1, for certain values of n.
>   
> Which values of n?

For the current code, bitsize n must be a multiple of GMP_NUMB_BITS
(for the ref code), 2*GMP_NUMB_BITS (for x^2-1) or 4*GMP_NUMB_BITS
(for x^4-1).

> I don't see how zero can be generated ever in the ref code, except
> when multiplying zero.  (The mul_2nm1_2 and mul_2nm1_4 functions
> are more likely to generate zero, I think.)

That might be the case: Whenever zero is represented as B^n-1 rather
than 0 in the inputs, a zero output is also represented as B^n-1. But
I haven't thought carefully about that.

> The testing code does not seem to think that the two representations of
> zero are equal.  :-)

The relevant test cases would be all zeros inputs, and inputs that
contain factors of B^n-1. The random numbers used by the testcode
probably doesn't include such inputs.

Regards,
/Niels