Several Points ... redc1
user42 at zip.com.au
Sat May 1 00:12:22 CEST 2004
Josh Liu <zliu2 at student.gsu.edu> writes:
> The single-precision Montgomery multiplication requires 3
> multiplication instructions
> as well as 2 subtract with borrow instructions.
Not sure about that.
> I would want to know if two of these multiplications can
> be reduced to one because the computation $a + (- m' a \bmod b) m$
> seems redundant, where m' is the modular inverse of m modulo b.
Without thinking too hard, I believe the reduction has to be two
multiplies. One the low half of lowdata*inverse to get a quotient,
the other the high half of quot*modulus to get a value to subtract.
The macros below are what I've used for 1-limb redc, I think they
worked when I last used them.
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 12868 bytes
Desc: not available
Url : /list-archives/gmp-devel/attachments/20040501/d9c1ff49/redc1-0001.bin
More information about the gmp-devel