redc_c

[Zimmermann Paul]

> Hi everyone, I'm a grad student at the University of Massachusetts.  I work
> on high precision arithmetic for GPUs.I was looking at the implementation of
> the redc_n function and was blown away.   It's such a clever useof
> mpn_mulmod_bnm1.   From reading the docs / change log, it looks like the
> mpn_mulmod_bnm1 stuff can be used to accelerate other functions as well.   
> So, here's my question -- is there a main paper tocite for the origin of
> this idea (i.e. using mulmod_bnm1 to accelerate various computations)?  
> And further,is there a paper to cite for the specific use of mulmod_bnm1 in
> REDC?
> Many thanks,Niall Emmart  

the idea behind redc_n is simply the Chinese Remainder Theorem: if you have a
number C of 2n limbs, and know its low n limbs (mullo) and its value mod B^n-1,
where B correspond to one limb, then you can easily reconstruct C.

For large n what is interesting is that the value mod B^n-1 can be computed
faster using FFT: it is equivalent to multiplying two numbers of n/2 limbs.
This is known as the "wrap-around trick", see for example Section 3.4 of
Modern Computer Arithmetic, Richard Brent and Paul Zimmermann, Cambridge
University Press, 2010 (also available online).

Paul Zimmermann