Leemon
High perfomance big integer library for modern javascript application
npm install --save leemonyarn add leemon
This code is reincarnation of Big Integer Library created by Leemon Baird in 2000, supported up to 2013
Example
Fibonacci
{ let a = zero let b = one whiletrue const c = a = b b = c } const fib = for let i = 0;i<500;i++ fibnextvalue // => '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
- findPrimes
- millerRabinInt
- millerRabin
- bitSize
- expand
- randTruePrime
- randProbPrime
- randProbPrimeRounds
- mod
- addInt
- mult
- powMod
- sub
- add
- inverseMod
- multMod
- randTruePrime_
- randBigInt
- randBigInt_
- GCD
- GCD_
- inverseMod_
- inverseModInt
- eGCD_
- negative
- greaterShift
- greater
- divide_
- carry_
- modInt
- int2bigInt
- str2bigInt
- equalsInt
- equals
- isZero
- bigInt2str
- dup
- copy_
- copyInt_
- addInt_
- rightShift_
- halve_
- leftShift_
- multInt_
- divInt_
- linComb_
- linCombShift_
- addShift_
- subShift_
- sub_
- add_
- mult_
- mod_
- multMod_
- squareMod_
- trim
- powMod_
- mont_
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
nnumber
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
randTruePrime
return a k-bit true random prime using Maurer's algorithm.
Parameters
knumber
randProbPrime
return a k-bit random probable prime with probability of error < 2^-80
Parameters
knumber
randProbPrimeRounds
return a k-bit probable random prime using n rounds of Miller Rabin (after trial division with small primes)
Parameters
mod
return a new bigInt equal to (x mod n) for bigInts x and n.
Parameters
addInt
return (x+n) where x is a bigInt and n is an integer.
Parameters
mult
return x*y for bigInts x and y. This is faster when y<x.
Parameters
powMod
return (x**y mod n) where x,y,n are bigInts and ** is exponentiation.
0**0=1.
Faster for odd n.
Parameters
sub
return (x-y) for bigInts x and y
Negative answers will be 2s complement
Parameters
add
return (x+y) for bigInts x and y
Parameters
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
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
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
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
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
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
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
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