Question about modular reduction algorithm

[Zimmermann Paul]

       Hi,

> I was looking through the Algorithms section of the documentation to see if I could figure out what algorithm is used for modular reduction so I can compare the cost of reduction a 2048-bit integer by a 1024 bit integer vs reducing a 384-bit number by a 192-bit number.  Unfortunately I didn't exactly understand the Exact Remainder section.  Can anybody either help me figure out the difference in cost or point me towards different documentation that will clear up this issue?  Thanks.

the Exact Remainder section refers to the Exact Division section just before,
which explains the division by the low words, also known as Hensel division.
When only the remainder is wanted, this is also known as Montgomery's REDC.
See [1], section 1.4.8.

In theory, if you use a quadratic algorithm, a 2048/1024 division will cost
(16/3)^2 times more than a (384/192) division.

Best regards,
Paul Zimmermann

[1] Modern Computer Arithmetic, Richard Brent and Paul Zimmermann, Cambridge
University Press, 2010. Also available online from the authors web pages.