bdiv vs redc

[Paul Leyland]

On Wed, 2012-06-27 at 12:31 +0200, Torbjorn Granlund wrote:
> nisse at lysator.liu.se (Niels Möller) writes:
> 

>   I think the reason for the redc changes was to let the caller decide if
>   the final conditional subtraction should be done unsing a constant time
>   method (powm_sec) or faster but with data-dependent timing (regular
>   powm).
>   
> Yes.  (And in some situation, the subtraction is not needed at all.
> Paul Zimmermann told me that the GMP-ECM code does not need it.  It
> might be possible to do without it also in powm.)

It appears that this result isn't as well known as it ought to be.

The reason why the subtraction need not be performed, in general, is
very simple.   Without the subtraction, the result lies in the range
0<x<2M-1 (where M is the modulus).  If the Montgomery modulus R >= 4M a
subsequent Montgomery multiplication can not overflow.  For modular
powering only the very final conditional subtraction needs to be
performed.  The price for this convenience, of course, is a dynamic
range reduction of two bits.

This observation is much used in RNS implementations of Montgomery
arithmetic where conditional subtracts tend to be *very* expensive.


Paul