Module reduction 

Modular reduction implementation.

Functions

montgomery_reduction 🔒

Algorithm 14.32 in Handbook of Applied Cryptography https://cacr.uwaterloo.ca/hac/about/chap14.pdf

montgomery_reduction_inner 🔒

Algorithm 14.32 in Handbook of Applied Cryptography https://cacr.uwaterloo.ca/hac/about/chap14.pdf

montgomery_retrieve

For input x < modulus in Montgomery form, compute x•R^-1 mod modulus.

montgomery_retrieve_inner

This algorithm corresponds to a Montgomery reduction of the wide input (x, 0), Algorithm 14.32 in Handbook of Applied Cryptography https://cacr.uwaterloo.ca/hac/about/chap14.pdf Or to a Montgomery multiplication of x by 1 (Algorithm 14.36). This version does not produce a carry and does not need further correction by subtracting the modulus as long as x < modulus. This is guaranteed because x < modulus => u < modulus => ((x + u•modulus) << N) < modulus.