simple-squiggle

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

invmod.js (2214B)

      1 "use strict";
      2 
      3 var _interopRequireDefault = require("@babel/runtime/helpers/interopRequireDefault");
      4 
      5 Object.defineProperty(exports, "__esModule", {
      6   value: true
      7 });
      8 exports.createInvmod = void 0;
      9 
     10 var _slicedToArray2 = _interopRequireDefault(require("@babel/runtime/helpers/slicedToArray"));
     11 
     12 var _factory = require("../../utils/factory.js");
     13 
     14 var name = 'invmod';
     15 var dependencies = ['typed', 'config', 'BigNumber', 'xgcd', 'equal', 'smaller', 'mod', 'add', 'isInteger'];
     16 var createInvmod = /* #__PURE__ */(0, _factory.factory)(name, dependencies, function (_ref) {
     17   var typed = _ref.typed,
     18       config = _ref.config,
     19       BigNumber = _ref.BigNumber,
     20       xgcd = _ref.xgcd,
     21       equal = _ref.equal,
     22       smaller = _ref.smaller,
     23       mod = _ref.mod,
     24       add = _ref.add,
     25       isInteger = _ref.isInteger;
     26 
     27   /**
     28    * Calculate the (modular) multiplicative inverse of a modulo b. Solution to the equation `ax ≣ 1 (mod b)`
     29    * See https://en.wikipedia.org/wiki/Modular_multiplicative_inverse.
     30    *
     31    * Syntax:
     32    *
     33    *    math.invmod(a, b)
     34    *
     35    * Examples:
     36    *
     37    *    math.invmod(8, 12)             // returns NaN
     38    *    math.invmod(7, 13)             // return 2
     39    *    math.invmod(15151, 15122)      // returns 10429
     40    *
     41    * See also:
     42    *
     43    *    gcd, xgcd
     44    *
     45    * @param {number | BigNumber} a  An integer number
     46    * @param {number | BigNumber} b  An integer number
     47    * @return {number | BigNumber }  Returns an integer number
     48    *                              where `invmod(a,b)*a ≣ 1 (mod b)`
     49    */
     50   return typed(name, {
     51     'number, number': invmod,
     52     'BigNumber, BigNumber': invmod
     53   });
     54 
     55   function invmod(a, b) {
     56     if (!isInteger(a) || !isInteger(b)) throw new Error('Parameters in function invmod must be integer numbers');
     57     a = mod(a, b);
     58     if (equal(b, 0)) throw new Error('Divisor must be non zero');
     59     var res = xgcd(a, b);
     60     res = res.valueOf();
     61 
     62     var _res = res,
     63         _res2 = (0, _slicedToArray2.default)(_res, 2),
     64         gcd = _res2[0],
     65         inv = _res2[1];
     66 
     67     if (!equal(gcd, BigNumber(1))) return NaN;
     68     inv = mod(inv, b);
     69     if (smaller(inv, BigNumber(0))) inv = add(inv, b);
     70     return inv;
     71   }
     72 });
     73 exports.createInvmod = createInvmod;