On Wed, 2012-06-27 at 12:31 +0200, Torbjorn Granlund wrote: > ni...@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 _______________________________________________ gmp-devel mailing list gmp-devel@gmplib.org http://gmplib.org/mailman/listinfo/gmp-devel