Several Points ... redc1

[Kevin Ryde]

Josh Liu <zliu2 at student.gsu.edu> writes:
>
> The single-precision Montgomery multiplication requires 3
> multiplication instructions

Sounds right.

> 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...
Name: redc1.h
Type: text/x-chdr
Size: 12868 bytes
Desc: not available
Url : /list-archives/gmp-devel/attachments/20040501/d9c1ff49/redc1-0001.bin