mini-gmp: mpz_abs_sub_bit needs more normalization
nisse at lysator.liu.se
Wed Aug 27 11:09:19 UTC 2014
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
> 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
> 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
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.
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.
More information about the gmp-bugs