Fast modular reduction for prime modulii close to powers of two

pseduo-fastmod.js

/*
 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
 * @param {Array<Integer>} m - Modulus of the form 2^e - k
 * @param {Integer} e
 * @param {Integer} k
 * @returns {Array<Integer>}
 */
function fastMod(n, m, e, k) {
  var m2 = mul(modulus, [ 2 ])
  while (cmp(n, m2) > 0) {
    var u = slice(n, e)//upper bits
    n = slice(n, 0, e)//lower digits
    if (len(u) > 0) {
      n = add(n, mul(u, [ k ]))
    }
  }
  return cmp(n, m) > 0 ? sub(n, m) : n
}

/**
 * Calculates a + b
 * @param {Array<Integer>} a
 * @param {Array<Integer>} b
 * @returns {Array<Integer>}
 */
function add(a, b) { ... }

/**
 * Calculates b - a
 * @param {Array<Integer>} a
 * @param {Array<Integer>} b
 * @returns {Array<Integer>}
 */
function sub(a, b) { ... }

/**
 * Calculates a * b
 * @param {Array<Integer>} a
 * @param {Array<Integer>} b
 * @returns {Array<Integer>}
 */
function mul(a, b) { ... }

/**
 * Returns 0 if a and b are equal, 1 if a > b, -1 if b < a
 * @param {Array<Integer>} a
 * @param {Array<Integer>} b
 * @returns {Integer}
 */
function cmp(a, b) { ... }

/**
 * Returns the number of digits required to represent the given number (as array length may be greater)
 * @param {Array<Integer>} a
 * @returns {Integer}
 */
function len(a) { ... }

/**
 * Returns a new number formed by a subset of the bits of the input number
 * @param {Array<Integer>} a - The input number
 * @param {Array<Integer>} s - The start index
 * @param {Array<Integer>} e - The end index
 * @returns {Array<Integer>}
 */
function slice(a, s, e) { ... }

The slice operation can be a simple array slice if 2^e is a power of the bigint base e.g. with a base of 2^32 and a modulus of 2^3072 - 77405.

Another note - 2^3072 - 77405 = 43902130 * q + 1, where q is prime. This means that 2^3072 - 77405 is a Schnorr group, although much stronger than the required 160-256 bits for q. There is no scheme which recommends a "strong" public prime (p = 2q + 1) that gains any practical security by using a strong prime instead of this one - the security comes from the raw bit length of q, not the difference in bit length with p.