Dmitry Eremin-Solenikov dbaryshkov@gmail.com writes:
Ok, thanks for the clarification. Is it only the case for 521-bit curve and for redc-based reduce? Because for all other cases 2 * p > B, so mul (and sqr) can not return value greater or equal to 2*m (= 2 * p).
Not sure I understand the question. For a reduced value t (output of ecc->mod or ecc->reduce), we always have both r < B (fits in ecc->size limbs) and r < 2 m.
Now, it's true that for many of the ecc-related moduli, we have 2 m > B, so that r < B ==> r < 2 m, but that makes little difference in this context. In either case, to reduce r to the canonical range 0 <= r < m, one conditional subtraction is needed.
One complication is that ecc_mod_add and ecc_mod_sub do *not* ensure r < 2 m, only r < B. So for moduli where 2 m < B, it's possible to get outputs t >= 2m.
Regards, /Niels