bigint-crypto-utils - npm Package Compare versions

Comparing version 3.0.5 to 3.0.6

lib/index.browser.mod.js

@@ -1,5 +0,217 @@
-import { bitLength, eGcd, modInv, modPow, toZn } from 'bigint-mod-arith'
-export { abs, bitLength, eGcd, gcd, lcm, max, min, modInv, modPow, toZn } from 'bigint-mod-arith'
+/**
+ * Absolute value. abs(a)==a if a>=0. abs(a)==-a if a<0
+ *
+ * @param {number|bigint} a
+ *
+ * @returns {bigint} the absolute value of a
+ */
+function abs (a) {
+  a = BigInt(a)
+  return (a >= 0n) ? a : -a
+}
 
 /**
+ * Returns the bitlength of a number
+ *
+ * @param {number|bigint} a
+ * @returns {number} - the bit length
+ */
+function bitLength (a) {
+  a = BigInt(a)
+  if (a === 1n) { return 1 }
+  let bits = 1
+  do {
+    bits++
+  } while ((a >>= 1n) > 1n)
+  return bits
+}
+
+/**
+ * @typedef {Object} egcdReturn A triple (g, x, y), such that ax + by = g = gcd(a, b).
+ * @property {bigint} g
+ * @property {bigint} x
+ * @property {bigint} y
+ */
+/**
+ * An iterative implementation of the extended euclidean algorithm or extended greatest common divisor algorithm.
+ * Take positive integers a, b as input, and return a triple (g, x, y), such that ax + by = g = gcd(a, b).
+ *
+ * @param {number|bigint} a
+ * @param {number|bigint} b
+ *
+ * @returns {egcdReturn} A triple (g, x, y), such that ax + by = g = gcd(a, b).
+ */
+function eGcd (a, b) {
+  a = BigInt(a)
+  b = BigInt(b)
+  if (a <= 0n | b <= 0n) throw new RangeError('a and b MUST be > 0') // a and b MUST be positive
+
+  let x = 0n
+  let y = 1n
+  let u = 1n
+  let v = 0n
+
+  while (a !== 0n) {
+    const q = b / a
+    const r = b % a
+    const m = x - (u * q)
+    const n = y - (v * q)
+    b = a
+    a = r
+    x = u
+    y = v
+    u = m
+    v = n
+  }
+  return {
+    g: b,
+    x: x,
+    y: y
+  }
+}
+
+/**
+ * Greatest-common divisor of two integers based on the iterative binary algorithm.
+ *
+ * @param {number|bigint} a
+ * @param {number|bigint} b
+ *
+ * @returns {bigint} The greatest common divisor of a and b
+ */
+function gcd (a, b) {
+  a = abs(a)
+  b = abs(b)
+  if (a === 0n) { return b } else if (b === 0n) { return a }
+
+  let shift = 0n
+  while (!((a | b) & 1n)) {
+    a >>= 1n
+    b >>= 1n
+    shift++
+  }
+  while (!(a & 1n)) a >>= 1n
+  do {
+    while (!(b & 1n)) b >>= 1n
+    if (a > b) {
+      const x = a
+      a = b
+      b = x
+    }
+    b -= a
+  } while (b)
+
+  // rescale
+  return a << shift
+}
+
+/**
+ * The least common multiple computed as abs(a*b)/gcd(a,b)
+ * @param {number|bigint} a
+ * @param {number|bigint} b
+ *
+ * @returns {bigint} The least common multiple of a and b
+ */
+function lcm (a, b) {
+  a = BigInt(a)
+  b = BigInt(b)
+  if (a === 0n && b === 0n) return BigInt(0)
+  return abs(a * b) / gcd(a, b)
+}
+
+/**
+ * Maximum. max(a,b)==a if a>=b. max(a,b)==b if a<=b
+ *
+ * @param {number|bigint} a
+ * @param {number|bigint} b
+ *
+ * @returns {bigint} maximum of numbers a and b
+ */
+function max (a, b) {
+  a = BigInt(a)
+  b = BigInt(b)
+  return (a >= b) ? a : b
+}
+
+/**
+ * Minimum. min(a,b)==b if a>=b. min(a,b)==a if a<=b
+ *
+ * @param {number|bigint} a
+ * @param {number|bigint} b
+ *
+ * @returns {bigint} minimum of numbers a and b
+ */
+function min (a, b) {
+  a = BigInt(a)
+  b = BigInt(b)
+  return (a >= b) ? b : a
+}
+
+/**
+ * Modular inverse.
+ *
+ * @param {number|bigint} a The number to find an inverse for
+ * @param {number|bigint} n The modulo
+ *
+ * @returns {bigint|NaN} the inverse modulo n or NaN if it does not exist
+ */
+function modInv (a, n) {
+  try {
+    const egcd = eGcd(toZn(a, n), n)
+    if (egcd.g !== 1n) {
+      return NaN // modular inverse does not exist
+    } else {
+      return toZn(egcd.x, n)
+    }
+  } catch (error) {
+    return NaN
+  }
+}
+
+/**
+ * Modular exponentiation b**e mod n. Currently using the right-to-left binary method
+ *
+ * @param {number|bigint} b base
+ * @param {number|bigint} e exponent
+ * @param {number|bigint} n modulo
+ *
+ * @returns {bigint} b**e mod n
+ */
+function modPow (b, e, n) {
+  n = BigInt(n)
+  if (n === 0n) { return NaN } else if (n === 1n) { return BigInt(0) }
+
+  b = toZn(b, n)
+
+  e = BigInt(e)
+  if (e < 0n) {
+    return modInv(modPow(b, abs(e), n), n)
+  }
+
+  let r = 1n
+  while (e > 0) {
+    if ((e % 2n) === 1n) {
+      r = (r * b) % n
+    }
+    e = e / 2n
+    b = b ** 2n % n
+  }
+  return r
+}
+
+/**
+ * Finds the smallest positive element that is congruent to a in modulo n
+ * @param {number|bigint} a An integer
+ * @param {number|bigint} n The modulo
+ *
+ * @returns {bigint} The smallest positive representation of a in modulo n
+ */
+function toZn (a, n) {
+  n = BigInt(n)
+  if (n <= 0) { return NaN }
+
+  a = BigInt(a) % n
+  return (a < 0) ? a + n : a
+}
+
+/**
  * The test first tries if any of the first 250 small primes are a factor of the input number and then passes several
@@ -625,2 +837,2 @@ * iterations of Miller-Rabin Probabilistic Primality Test (FIPS 186-4 C.3.1)
 
-export { isProbablyPrime, prime, primeSync, randBetween, randBits, randBitsSync, randBytes, randBytesSync }
+export { abs, bitLength, eGcd, gcd, isProbablyPrime, lcm, max, min, modInv, modPow, prime, primeSync, randBetween, randBits, randBitsSync, randBytes, randBytesSync, toZn }

lib/index.node.js

 'use strict'
 
-var bigintModArith = require('bigint-mod-arith')
+/**
+ * Absolute value. abs(a)==a if a>=0. abs(a)==-a if a<0
+ *
+ * @param {number|bigint} a
+ *
+ * @returns {bigint} the absolute value of a
+ */
+function abs (a) {
+  a = BigInt(a)
+  return (a >= 0n) ? a : -a
+}
 
 /**
+ * Returns the bitlength of a number
+ *
+ * @param {number|bigint} a
+ * @returns {number} - the bit length
+ */
+function bitLength (a) {
+  a = BigInt(a)
+  if (a === 1n) { return 1 }
+  let bits = 1
+  do {
+    bits++
+  } while ((a >>= 1n) > 1n)
+  return bits
+}
+
+/**
+ * @typedef {Object} egcdReturn A triple (g, x, y), such that ax + by = g = gcd(a, b).
+ * @property {bigint} g
+ * @property {bigint} x
+ * @property {bigint} y
+ */
+/**
+ * An iterative implementation of the extended euclidean algorithm or extended greatest common divisor algorithm.
+ * Take positive integers a, b as input, and return a triple (g, x, y), such that ax + by = g = gcd(a, b).
+ *
+ * @param {number|bigint} a
+ * @param {number|bigint} b
+ *
+ * @returns {egcdReturn} A triple (g, x, y), such that ax + by = g = gcd(a, b).
+ */
+function eGcd (a, b) {
+  a = BigInt(a)
+  b = BigInt(b)
+  if (a <= 0n | b <= 0n) throw new RangeError('a and b MUST be > 0') // a and b MUST be positive
+
+  let x = 0n
+  let y = 1n
+  let u = 1n
+  let v = 0n
+
+  while (a !== 0n) {
+    const q = b / a
+    const r = b % a
+    const m = x - (u * q)
+    const n = y - (v * q)
+    b = a
+    a = r
+    x = u
+    y = v
+    u = m
+    v = n
+  }
+  return {
+    g: b,
+    x: x,
+    y: y
+  }
+}
+
+/**
+ * Greatest-common divisor of two integers based on the iterative binary algorithm.
+ *
+ * @param {number|bigint} a
+ * @param {number|bigint} b
+ *
+ * @returns {bigint} The greatest common divisor of a and b
+ */
+function gcd (a, b) {
+  a = abs(a)
+  b = abs(b)
+  if (a === 0n) { return b } else if (b === 0n) { return a }
+
+  let shift = 0n
+  while (!((a | b) & 1n)) {
+    a >>= 1n
+    b >>= 1n
+    shift++
+  }
+  while (!(a & 1n)) a >>= 1n
+  do {
+    while (!(b & 1n)) b >>= 1n
+    if (a > b) {
+      const x = a
+      a = b
+      b = x
+    }
+    b -= a
+  } while (b)
+
+  // rescale
+  return a << shift
+}
+
+/**
+ * The least common multiple computed as abs(a*b)/gcd(a,b)
+ * @param {number|bigint} a
+ * @param {number|bigint} b
+ *
+ * @returns {bigint} The least common multiple of a and b
+ */
+function lcm (a, b) {
+  a = BigInt(a)
+  b = BigInt(b)
+  if (a === 0n && b === 0n) return BigInt(0)
+  return abs(a * b) / gcd(a, b)
+}
+
+/**
+ * Maximum. max(a,b)==a if a>=b. max(a,b)==b if a<=b
+ *
+ * @param {number|bigint} a
+ * @param {number|bigint} b
+ *
+ * @returns {bigint} maximum of numbers a and b
+ */
+function max (a, b) {
+  a = BigInt(a)
+  b = BigInt(b)
+  return (a >= b) ? a : b
+}
+
+/**
+ * Minimum. min(a,b)==b if a>=b. min(a,b)==a if a<=b
+ *
+ * @param {number|bigint} a
+ * @param {number|bigint} b
+ *
+ * @returns {bigint} minimum of numbers a and b
+ */
+function min (a, b) {
+  a = BigInt(a)
+  b = BigInt(b)
+  return (a >= b) ? b : a
+}
+
+/**
+ * Modular inverse.
+ *
+ * @param {number|bigint} a The number to find an inverse for
+ * @param {number|bigint} n The modulo
+ *
+ * @returns {bigint|NaN} the inverse modulo n or NaN if it does not exist
+ */
+function modInv (a, n) {
+  try {
+    const egcd = eGcd(toZn(a, n), n)
+    if (egcd.g !== 1n) {
+      return NaN // modular inverse does not exist
+    } else {
+      return toZn(egcd.x, n)
+    }
+  } catch (error) {
+    return NaN
+  }
+}
+
+/**
+ * Modular exponentiation b**e mod n. Currently using the right-to-left binary method
+ *
+ * @param {number|bigint} b base
+ * @param {number|bigint} e exponent
+ * @param {number|bigint} n modulo
+ *
+ * @returns {bigint} b**e mod n
+ */
+function modPow (b, e, n) {
+  n = BigInt(n)
+  if (n === 0n) { return NaN } else if (n === 1n) { return BigInt(0) }
+
+  b = toZn(b, n)
+
+  e = BigInt(e)
+  if (e < 0n) {
+    return modInv(modPow(b, abs(e), n), n)
+  }
+
+  let r = 1n
+  while (e > 0) {
+    if ((e % 2n) === 1n) {
+      r = (r * b) % n
+    }
+    e = e / 2n
+    b = b ** 2n % n
+  }
+  return r
+}
+
+/**
+ * Finds the smallest positive element that is congruent to a in modulo n
+ * @param {number|bigint} a An integer
+ * @param {number|bigint} n The modulo
+ *
+ * @returns {bigint} The smallest positive representation of a in modulo n
+ */
+function toZn (a, n) {
+  n = BigInt(n)
+  if (n <= 0) { return NaN }
+
+  a = BigInt(a) % n
+  return (a < 0) ? a + n : a
+}
+
+/**
  * The test first tries if any of the first 250 small primes are a factor of the input number and then passes several
@@ -159,3 +372,3 @@ * iterations of Miller-Rabin Probabilistic Primality Test (FIPS 186-4 C.3.1)
   const interval = max - min
-  const bitLen = bigintModArith.bitLength(interval)
+  const bitLen = bitLength(interval)
   let rnd
@@ -591,7 +804,7 @@ do {
     const b = randBetween(d, 2n)
-    let z = bigintModArith.modPow(b, m, w)
+    let z = modPow(b, m, w)
     if (z === 1n || z === d) continue
     let j = 1
     while (j < a) {
-      z = bigintModArith.modPow(z, 2n, w)
+      z = modPow(z, 2n, w)
       if (z === d) break
@@ -641,13 +854,12 @@ if (z === 1n) return false
 
-exports.abs = bigintModArith.abs
-exports.bitLength = bigintModArith.bitLength
-exports.eGcd = bigintModArith.eGcd
-exports.gcd = bigintModArith.gcd
-exports.lcm = bigintModArith.lcm
-exports.max = bigintModArith.max
-exports.min = bigintModArith.min
-exports.modInv = bigintModArith.modInv
-exports.modPow = bigintModArith.modPow
-exports.toZn = bigintModArith.toZn
+exports.abs = abs
+exports.bitLength = bitLength
+exports.eGcd = eGcd
+exports.gcd = gcd
 exports.isProbablyPrime = isProbablyPrime
+exports.lcm = lcm
+exports.max = max
+exports.min = min
+exports.modInv = modInv
+exports.modPow = modPow
 exports.prime = prime
@@ -660,1 +872,2 @@ exports.primeSync = primeSync
 exports.randBytesSync = randBytesSync
+exports.toZn = toZn

package.json

 {
   "name": "bigint-crypto-utils",
-  "version": "3.0.5",
+  "version": "3.0.6",
   "description": "Arbitrary precision modular arithmetic, cryptographically secure random numbers and strong probable prime generation/testing. It works in modern browsers, Angular, React, Node.js, etc. since it uses the native JS implementation of BigInt",
@@ -68,3 +68,3 @@ "keywords": [
     "@rollup/plugin-commonjs": "^11.1.0",
-    "@rollup/plugin-multi-entry": "^3.0.0",
+    "@rollup/plugin-multi-entry": "^3.0.1",
     "@rollup/plugin-node-resolve": "^7.1.3",
@@ -74,14 +74,13 @@ "@rollup/plugin-replace": "^2.3.2",
     "jsdoc-to-markdown": "^5.0.3",
-    "mocha": "^7.1.1",
+    "mocha": "^7.1.2",
     "npm-run-all": "^4.1.5",
     "nyc": "^15.0.1",
-    "rollup": "^2.6.1",
+    "rollup": "^2.9.1",
     "rollup-plugin-terser": "^5.3.0",
-    "standard": "^14.3.3",
+    "standard": "^14.3.4",
     "typescript": "^3.8.3"
   },
   "dependencies": {
-    "@types/node": ">=10.4.0",
-    "bigint-mod-arith": "^2.0.7"
+    "@types/node": ">=10.4.0"
   }
 }

types/index.d.ts

 /**
+ * A triple (g, x, y), such that ax + by = g = gcd(a, b).
+ */
+export type egcdReturn = {
+    g: bigint;
+    x: bigint;
+    y: bigint;
+};
+/**
+ * Absolute value. abs(a)==a if a>=0. abs(a)==-a if a<0
+ *
+ * @param {number|bigint} a
+ *
+ * @returns {bigint} the absolute value of a
+ */
+export function abs(a: number | bigint): bigint;
+/**
+ * Returns the bitlength of a number
+ *
+ * @param {number|bigint} a
+ * @returns {number} - the bit length
+ */
+export function bitLength(a: number | bigint): number;
+/**
+ * @typedef {Object} egcdReturn A triple (g, x, y), such that ax + by = g = gcd(a, b).
+ * @property {bigint} g
+ * @property {bigint} x
+ * @property {bigint} y
+ */
+/**
+ * An iterative implementation of the extended euclidean algorithm or extended greatest common divisor algorithm.
+ * Take positive integers a, b as input, and return a triple (g, x, y), such that ax + by = g = gcd(a, b).
+ *
+ * @param {number|bigint} a
+ * @param {number|bigint} b
+ *
+ * @returns {egcdReturn} A triple (g, x, y), such that ax + by = g = gcd(a, b).
+ */
+export function eGcd(a: number | bigint, b: number | bigint): egcdReturn;
+/**
+ * Greatest-common divisor of two integers based on the iterative binary algorithm.
+ *
+ * @param {number|bigint} a
+ * @param {number|bigint} b
+ *
+ * @returns {bigint} The greatest common divisor of a and b
+ */
+export function gcd(a: number | bigint, b: number | bigint): bigint;
+/**
  * The test first tries if any of the first 250 small primes are a factor of the input number and then passes several
@@ -15,2 +63,47 @@ * iterations of Miller-Rabin Probabilistic Primality Test (FIPS 186-4 C.3.1)
 /**
+ * The least common multiple computed as abs(a*b)/gcd(a,b)
+ * @param {number|bigint} a
+ * @param {number|bigint} b
+ *
+ * @returns {bigint} The least common multiple of a and b
+ */
+export function lcm(a: number | bigint, b: number | bigint): bigint;
+/**
+ * Maximum. max(a,b)==a if a>=b. max(a,b)==b if a<=b
+ *
+ * @param {number|bigint} a
+ * @param {number|bigint} b
+ *
+ * @returns {bigint} maximum of numbers a and b
+ */
+export function max(a: number | bigint, b: number | bigint): bigint;
+/**
+ * Minimum. min(a,b)==b if a>=b. min(a,b)==a if a<=b
+ *
+ * @param {number|bigint} a
+ * @param {number|bigint} b
+ *
+ * @returns {bigint} minimum of numbers a and b
+ */
+export function min(a: number | bigint, b: number | bigint): bigint;
+/**
+ * Modular inverse.
+ *
+ * @param {number|bigint} a The number to find an inverse for
+ * @param {number|bigint} n The modulo
+ *
+ * @returns {bigint|NaN} the inverse modulo n or NaN if it does not exist
+ */
+export function modInv(a: number | bigint, n: number | bigint): number | bigint;
+/**
+ * Modular exponentiation b**e mod n. Currently using the right-to-left binary method
+ *
+ * @param {number|bigint} b base
+ * @param {number|bigint} e exponent
+ * @param {number|bigint} n modulo
+ *
+ * @returns {bigint} b**e mod n
+ */
+export function modPow(b: number | bigint, e: number | bigint, n: number | bigint): bigint;
+/**
  * A probably-prime (Miller-Rabin), cryptographically-secure, random-number generator.
@@ -95,2 +188,9 @@ * The browser version uses web workers to parallelise prime look up. Therefore, it does not lock the UI
 export function randBytesSync(byteLength: number, forceLength?: boolean): Uint8Array | Buffer;
-export { abs, bitLength, eGcd, gcd, lcm, max, min, modInv, modPow, toZn } from "bigint-mod-arith";
+/**
+ * Finds the smallest positive element that is congruent to a in modulo n
+ * @param {number|bigint} a An integer
+ * @param {number|bigint} n The modulo
+ *
+ * @returns {bigint} The smallest positive representation of a in modulo n
+ */
+export function toZn(a: number | bigint, n: number | bigint): bigint;

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

85213

increased by14.98%

Dependency count

1

decreased by-50%

Lines of code

1848

increased by36.18%

Dependency changes

• - Removedbigint-mod-arith@^2.0.7

• - Removedbigint-mod-arith@2.1.0(transitive)