simple-squiggle

A restricted subset of Squiggle
Log | Files | Refs | README

invmod.js (1645B)

      1 import { factory } from '../../utils/factory.js';
      2 var name = 'invmod';
      3 var dependencies = ['typed', 'config', 'BigNumber', 'xgcd', 'equal', 'smaller', 'mod', 'add', 'isInteger'];
      4 export var createInvmod = /* #__PURE__ */factory(name, dependencies, _ref => {
      5   var {
      6     typed,
      7     config,
      8     BigNumber,
      9     xgcd,
     10     equal,
     11     smaller,
     12     mod,
     13     add,
     14     isInteger
     15   } = _ref;
     16 
     17   /**
     18    * Calculate the (modular) multiplicative inverse of a modulo b. Solution to the equation `ax ≣ 1 (mod b)`
     19    * See https://en.wikipedia.org/wiki/Modular_multiplicative_inverse.
     20    *
     21    * Syntax:
     22    *
     23    *    math.invmod(a, b)
     24    *
     25    * Examples:
     26    *
     27    *    math.invmod(8, 12)             // returns NaN
     28    *    math.invmod(7, 13)             // return 2
     29    *    math.invmod(15151, 15122)      // returns 10429
     30    *
     31    * See also:
     32    *
     33    *    gcd, xgcd
     34    *
     35    * @param {number | BigNumber} a  An integer number
     36    * @param {number | BigNumber} b  An integer number
     37    * @return {number | BigNumber }  Returns an integer number
     38    *                              where `invmod(a,b)*a ≣ 1 (mod b)`
     39    */
     40   return typed(name, {
     41     'number, number': invmod,
     42     'BigNumber, BigNumber': invmod
     43   });
     44 
     45   function invmod(a, b) {
     46     if (!isInteger(a) || !isInteger(b)) throw new Error('Parameters in function invmod must be integer numbers');
     47     a = mod(a, b);
     48     if (equal(b, 0)) throw new Error('Divisor must be non zero');
     49     var res = xgcd(a, b);
     50     res = res.valueOf();
     51     var [gcd, inv] = res;
     52     if (!equal(gcd, BigNumber(1))) return NaN;
     53     inv = mod(inv, b);
     54     if (smaller(inv, BigNumber(0))) inv = add(inv, b);
     55     return inv;
     56   }
     57 });