mini-gmp: mpz_abs_sub_bit needs more normalization

[Niels Möller]

tg at gmplib.org (Torbjörn Granlund) writes:

> A pretty obvious bug, and the result of over-agressive optimisation
> which might not have place in mini-gmp.

We do a lot of micro-optimizations, and I think almost any optimization
which doesn't make the code less concise has it's place in mini-gmp.

When I wrote that code, I forgot the case of clearing the MSB; if one
subtracts any smaller power of two, the number can shrink by at most
one bit.

> Will you please take a look to see if this is done in more places?

Other cases of n -= (p[n-1] == 0) look fine to me. They're related to
the result of multiplication and division with normalized inputs.
mpz_abs_sub_bit appears to be the only use of mpn_sub* which lacked full
normalization.

> Then fix for the 6.0 repo as well as the head repo (and perhaps 5.1
> repo if the bug is there).

Fixed in all three repos now.

I haven't added any testcase. The case where I stumbled on the bug was

      bits = mpz_sizeinbase (ecc->q, 2);
      mpz_set (t, ecc->q);
      mpz_clrbit (t, bits-1);
      mbits = mpz_sizeinbase (t, 2);

where ecc->q was the number

  0x1000000000000000000000000000000014def9dea2f79cd65812631a5cf5d3ed,

the order of the base point on djb's curve25519. (Most other curves in
cryptographic have order q = 2^k - q' with q' at least a limb smaller
than q, but for curve25519, we instead have q = 2^k + q', with small q'.
And this nice structure matters for optimized reductions mod q).

So I've confirmed that the fix does solve the problem.

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.