Skip to content

High perfomance big integer library for modern javascript application

License

Notifications You must be signed in to change notification settings

zerobias/leemon

Repository files navigation

Leemon

High perfomance big integer library for modern javascript application

npm install --save leemon
yarn add leemon

npm version Build Status

This code is reincarnation of Big Integer Library created by Leemon Baird in 2000, supported up to 2013

Example

Fibonacci

import { one, zero, add, bigInt2str } from 'leemon'

function* fibonacci() {
  let a = zero
  let b = one
  while(true){
    const c = add(a, b)
    a = b
    b = c
    yield bigInt2str(c, 10)
  }
}

const fib = fibonacci()



for (let i = 0;i<500;i++) fib.next().value

// => '225591516161936330872512695036072072046011324913758190588638866418474627738686883405015987052796968498626'

A bigInt is an array of integers storing the value in chunks of bpe bits, little endian (buff[0] is the least significant word). Negative bigInts are stored two's complement. Almost all the functions treat bigInts as nonnegative. The few that view them as two's complement say so in their comments. Some functions assume their parameters have at least one leading zero element. Functions with an underscore at the end of the name put their answer into one of the arrays passed in, and have unpredictable behavior in case of overflow, so the caller must make sure the arrays are big enough to hold the answer. But the average user should never have to call any of the underscored functions. Each important underscored function has a wrapper function of the same name without the underscore that takes care of the details for you. For each underscored function where a parameter is modified, that same variable must not be used as another argument too. So, you cannot square x by doing multMod_(x,x,n). You must use squareMod_(x,n) instead, or do y=dup(x); multMod_(x,y,n). Or simply use the multMod(x,x,n) function without the underscore, where such issues never arise, because non-underscored functions never change their parameters (immutable); they always allocate new memory for the answer that is returned.

API

Table of Contents

Bool


Big Integer Library _ Created 2000 _ Leemon Baird _ www.leemon.com _


Type: (1 | 0)

findPrimes

return array of all primes less than integer n

Parameters

Returns Array<number>

millerRabinInt

does a single round of Miller-Rabin base b consider x to be a possible prime?

x is a bigInt, and b is an integer, with b<x

Parameters

Returns (0 | 1)

millerRabin

does a single round of Miller-Rabin base b consider x to be a possible prime?

x and b are bigInts with b<x

Parameters

Returns (0 | 1)

bitSize

returns how many bits long the bigInt is, not counting leading zeros.

Parameters

Returns number

expand

return a copy of x with at least n elements, adding leading zeros if needed

Parameters

Returns Array<number>

randTruePrime

return a k-bit true random prime using Maurer's algorithm.

Parameters

Returns Array<number>

randProbPrime

return a k-bit random probable prime with probability of error < 2^-80

Parameters

Returns Array<number>

randProbPrimeRounds

return a k-bit probable random prime using n rounds of Miller Rabin (after trial division with small primes)

Parameters

Returns Array<number>

mod

return a new bigInt equal to (x mod n) for bigInts x and n.

Parameters

Returns Array<number>

addInt

return (x+n) where x is a bigInt and n is an integer.

Parameters

Returns Array<number>

mult

return x*y for bigInts x and y. This is faster when y<x.

Parameters

Returns Array<number>

powMod

return (x**y mod n) where x,y,n are bigInts and ** is exponentiation.

0**0=1.

Faster for odd n.

Parameters

Returns Array<number>

sub

return (x-y) for bigInts x and y

Negative answers will be 2s complement

Parameters

Returns Array<number>

add

return (x+y) for bigInts x and y

Parameters

Returns Array<number>

inverseMod

return (x**(-1) mod n) for bigInts x and n.

If no inverse exists, it returns null

Parameters

Returns (Array<number> | null)

multMod

return (x*y mod n) for bigInts x,y,n.

For greater speed, let y<x.

Parameters

Returns Array<number>

randTruePrime_

generate a k-bit true random prime using Maurer's algorithm, and put it into ans.

The bigInt ans must be large enough to hold it.

Parameters

Returns void

randBigInt

Return an n-bit random BigInt (n>=1). If s=1, then the most significant of those n bits is set to 1.

Parameters

Returns Array<number>

randBigInt_

Set b to an n-bit random BigInt. If s=1, then the most significant of those n bits is set to 1.

Array b must be big enough to hold the result. Must have n>=1

Parameters

Returns void

GCD

Return the greatest common divisor of bigInts x and y (each with same number of elements).

Parameters

Returns Array<number>

GCD_

set x to the greatest common divisor of bigInts x and y (each with same number of elements).

y is destroyed.

Parameters

Returns void

inverseMod_

do x=x**(-1) mod n, for bigInts x and n.

If no inverse exists, it sets x to zero and returns 0, else it returns 1. The x array must be at least as large as the n array.

Parameters

Returns (0 | 1)

inverseModInt

return x**(-1) mod n, for integers x and n.

Return 0 if there is no inverse

Parameters

Returns number

eGCD_

Given positive bigInts x and y, change the bigints v, a, and b to positive bigInts such that:

 v = GCD_(x,y) = a*x-b*y

The bigInts v, a, b, must have exactly as many elements as the larger of x and y.

Parameters

Returns void

negative

is bigInt x negative?

Parameters

Returns (1 | 0)

greaterShift

is (x << (shift*bpe)) > y?

x and y are nonnegative bigInts shift is a nonnegative integer

Parameters

Returns (1 | 0)

greater

is x > y?

x and y both nonnegative

Parameters

Returns (1 | 0)

divide_

divide x by y giving quotient q and remainder r.

q = floor(x/y)
r = x mod y

All 4 are bigints.

  • x must have at least one leading zero element.
  • y must be nonzero.
  • q and r must be arrays that are exactly the same length as x. (Or q can have more).
  • Must have x.length >= y.length >= 2.

Parameters

Returns void

carry_

do carries and borrows so each element of the bigInt x fits in bpe bits.

Parameters

Returns void

modInt

return x mod n for bigInt x and integer n.

Parameters

Returns number

int2bigInt

convert the integer t into a bigInt with at least the given number of bits. the returned array stores the bigInt in bpe-bit chunks, little endian (buff[0] is least significant word) Pad the array with leading zeros so that it has at least minSize elements.

There will always be at least one leading 0 element.

Parameters

Returns Array<number>

str2bigInt

return the bigInt given a string representation in a given base. Pad the array with leading zeros so that it has at least minSize elements. If base=-1, then it reads in a space-separated list of array elements in decimal.

The array will always have at least one leading zero, unless base=-1.

Parameters

Returns Array<number>

equalsInt

is bigint x equal to integer y?

y must have less than bpe bits

Parameters

Returns (1 | 0)

equals

are bigints x and y equal?

this works even if x and y are different lengths and have arbitrarily many leading zeros

Parameters

Returns (1 | 0)

isZero

is the bigInt x equal to zero?

Parameters

Returns (1 | 0)

bigInt2str

Convert a bigInt into a string in a given base, from base 2 up to base 95.

Base -1 prints the contents of the array representing the number.

Parameters

Returns string

dup

Returns a duplicate of bigInt x

Parameters

Returns Array<number>

copy_

do x=y on bigInts x and y.

x must be an array at least as big as y (not counting the leading zeros in y).

Parameters

Returns void

copyInt_

do x=y on bigInt x and integer y.

Parameters

Returns void

addInt_

do x=x+n where x is a bigInt and n is an integer.

x must be large enough to hold the result.

Parameters

Returns void

rightShift_

right shift bigInt x by n bits.

0 <= n < bpe.

Parameters

Returns void

halve_

do x=floor(|x|/2)*sgn(x) for bigInt x in 2's complement

Parameters

Returns void

leftShift_

left shift bigInt x by n bits

Parameters

Returns void

multInt_

do x=x*n where x is a bigInt and n is an integer.

x must be large enough to hold the result.

Parameters

Returns void

divInt_

do x=floor(x/n) for bigInt x and integer n, and return the remainder

Parameters

Returns number remainder

linComb_

do the linear combination x=a_x+b_y for bigInts x and y, and integers a and b.

x must be large enough to hold the answer.

Parameters

Returns void

linCombShift_

do the linear combination x=a_x+b_(y<<(ys*bpe)) for bigInts x and y, and integers a, b and ys.

x must be large enough to hold the answer.

Parameters

Returns void

addShift_

do x=x+(y<<(ys*bpe)) for bigInts x and y, and integer ys.

x must be large enough to hold the answer.

Parameters

Returns void

subShift_

do x=x-(y<<(ys*bpe)) for bigInts x and y, and integer ys

x must be large enough to hold the answer

Parameters

Returns void

sub_

do x=x-y for bigInts x and y

x must be large enough to hold the answer

negative answers will be 2s complement

Parameters

Returns void

add_

do x=x+y for bigInts x and y

x must be large enough to hold the answer

Parameters

Returns void

mult_

do x=x*y for bigInts x and y.

This is faster when y<x.

Parameters

Returns void

mod_

do x=x mod n for bigInts x and n

Parameters

Returns void

multMod_

do x=x*y mod n for bigInts x,y,n.

for greater speed, let y<x.

Parameters

Returns void

squareMod_

do x=x*x mod n for bigInts x,n.

Parameters

Returns void

trim

return x with exactly k leading zero elements

Parameters

Returns Array<number>

powMod_

do x=x**y mod n, where x,y,n are bigInts and ** is exponentiation. 0**0=1.

this is faster when n is odd.

x usually needs to have as many elements as n.

Parameters

Returns void

mont_

do x=x_y_Ri mod n for bigInts x,y,n, where Ri = 2*_(-kn_bpe) mod n, and kn is the number of elements in the n array, not counting leading zeros.

x array must have at least as many elemnts as the n array It's OK if x and y are the same variable.

must have:

  • x,y < n
  • n is odd
  • np = -(n^(-1)) mod radix

Parameters

Returns void

About

High perfomance big integer library for modern javascript application

Resources

License

Stars

Watchers

Forks

Packages

No packages published