Skip to content

Instantly share code, notes, and snippets.

@tristanhoy
tristanhoy / pseduo-fastmod.js
Created September 21, 2017 23:48
Fast modular reduction for prime modulii close to powers of two
/*
Pseudo-code implementation of
https://crypto.stackexchange.com/questions/24014/what-are-the-computational-benefits-of-primes-close-to-the-power-of-2
The prime must be of the form m = 2^e - k, where k is less than the bigint base (and should be as small as possible)
*/
/**
* Calculates n % m
* @param {Array<Integer>} n - Number to calculate modulo (remainder) of, must be less than m^2