- 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_
Big Integer Library _ Created 2000 _ Leemon Baird _ www.leemon.com _
Type: (1 | 0)
return array of all primes less than integer n
nnumber
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
Returns (0 | 1)
does a single round of Miller-Rabin base b consider x to be a possible prime?
x and b are bigInts with b<x
Returns (0 | 1)
returns how many bits long the bigInt is, not counting leading zeros.
Returns number
return a copy of x with at least n elements, adding leading zeros if needed
return a k-bit true random prime using Maurer's algorithm.
knumber
return a k-bit random probable prime with probability of error < 2^-80
knumber
return a k-bit probable random prime using n rounds of Miller Rabin (after trial division with small primes)
return a new bigInt equal to (x mod n) for bigInts x and n.
return (x+n) where x is a bigInt and n is an integer.
return x*y for bigInts x and y. This is faster when y<x.
return (x**y mod n) where x,y,n are bigInts and ** is exponentiation.
0**0=1.
Faster for odd n.
return (x-y) for bigInts x and y
Negative answers will be 2s complement
return (x+y) for bigInts x and y
return (x**(-1) mod n) for bigInts x and n.
If no inverse exists, it returns null
Returns (Array<number> | null)
return (x*y mod n) for bigInts x,y,n.
For greater speed, let y<x.
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.
Returns void
Return an n-bit random BigInt (n>=1). If s=1, then the most significant of those n bits is set to 1.
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
Returns void
Return the greatest common divisor of bigInts x and y (each with same number of elements).
set x to the greatest common divisor of bigInts x and y (each with same number of elements).
y is destroyed.
Returns void
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.
Returns (0 | 1)
return x**(-1) mod n, for integers x and n.
Return 0 if there is no inverse
Returns number
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.
Returns void
is bigInt x negative?
Returns (1 | 0)
is (x << (shift*bpe)) > y?
x and y are nonnegative bigInts shift is a nonnegative integer
Returns (1 | 0)
is x > y?
x and y both nonnegative
Returns (1 | 0)
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.
Returns void
do carries and borrows so each element of the bigInt x fits in bpe bits.
Returns void
return x mod n for bigInt x and integer n.
Returns number
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.
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.
is bigint x equal to integer y?
y must have less than bpe bits
Returns (1 | 0)
are bigints x and y equal?
this works even if x and y are different lengths and have arbitrarily many leading zeros
Returns (1 | 0)
is the bigInt x equal to zero?
Returns (1 | 0)
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.
Returns string
Returns a duplicate of bigInt x
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).
Returns void
do x=y on bigInt x and integer y.
Returns void
do x=x+n where x is a bigInt and n is an integer.
x must be large enough to hold the result.
Returns void
right shift bigInt x by n bits.
0 <= n < bpe.
Returns void
do x=floor(|x|/2)*sgn(x) for bigInt x in 2's complement
Returns void
left shift bigInt x by n bits
Returns void
do x=x*n where x is a bigInt and n is an integer.
x must be large enough to hold the result.
Returns void
do x=floor(x/n) for bigInt x and integer n, and return the remainder
Returns number remainder
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.
Returns void
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.
Returns void
do x=x+(y<<(ys*bpe)) for bigInts x and y, and integer ys.
x must be large enough to hold the answer.
Returns void
do x=x-(y<<(ys*bpe)) for bigInts x and y, and integer ys
x must be large enough to hold the answer
Returns void
do x=x-y for bigInts x and y
x must be large enough to hold the answer
negative answers will be 2s complement
Returns void
do x=x+y for bigInts x and y
x must be large enough to hold the answer
Returns void
do x=x*y for bigInts x and y.
This is faster when y<x.
Returns void
do x=x mod n for bigInts x and n
Returns void
do x=x*y mod n for bigInts x,y,n.
for greater speed, let y<x.
Returns void
do x=x*x mod n for bigInts x,n.
Returns void
return x with exactly k leading zero elements
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.
Returns void
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
Returns void