Module monty

Structs

MontyReducer 🔒

Functions

add_mul_vvw 🔒

add_ww 🔒

z1<<_W + z0 = x+y+c, with c == 0 or 1

inv_mod_alt 🔒

montgomery 🔒

Computes z mod m = x * y * 2 ** (-n*_W) mod m assuming k = -1/m mod 2**_W See Gueron, “Efficient Software Implementations of Modular Exponentiation”. https://eprint.iacr.org/2011/239.pdf In the terminology of that paper, this is an “Almost Montgomery Multiplication”: x and y are required to satisfy 0 <= z < 2**(n*_W) and then the result z is guaranteed to satisfy 0 <= z < 2**(n*_W), but it may not be < m.

monty_modpow 🔒

Calculates x ** y mod m using a fixed, 4-bit window.

mul_add_www 🔒

z1 << _W + z0 = x * y + c

sub_vv 🔒

The resulting carry c is either 0 or 1.