partial mod reduction

[Zimmermann Paul]

       Hi Paul,

> Date: Sun, 16 Jun 2013 19:53:20 -0400
> From: "Paul Underwood" <paulunderwood at mindless.com>
> 
> I had an idea for partial mod reduction, equivalent to 1 schoolbook multiplication during exponentiation, to be followed by full reduction at the end of the loop. Two initial full mod reductions are needed. Optionally, a table of such initial values could be done, the size of which is log_2(W) where W is the number of limbs of n. The latter method would allow Karasuba/Toom-Cook to be done for some of the bigger multiplications.
> 
> Working in base 1000 for example, suppose the modulus is n=12,345,678,910,111.
> 
> 1. Compute 1,000,000,000,000,000 (mod n)
> 
> 2. Compute 1,000,000,000,000,000,000 (mod n)
> 
> 3. During the exponentiation loop maintain partial mods, by multiplying the top word of the result of multiplication/squaring by the value "2." shifted and adding it to the mult. result. and so on with the next word down to the limb size of W+1, and then multiply the {W+1}st word by "1." and adding to the lower W limbss, until there are W limbs left. [...]

this is the folding technique described on page 63 and Table 2.2 of "Modern
Computer Arithmetic" [1]. See reference [118] from that book.

Best regards,
Paul Zimmermann

[1] http://www.loria.fr/~zimmerma/mca/pub226.html