//////////////////////////////////////////////////////////////////////////////////////// // Big Integer Library v. 5.5 // Created 2000, last modified 2013 // Leemon Baird // www.leemon.com // // Version history: // v 5.5 17 Mar 2013 // - two lines of a form like "if (x<0) x+=n" had the "if" changed to "while" to // handle the case when x<-n. (Thanks to James Ansell for finding that bug) // v 5.4 3 Oct 2009 // - added "var i" to greaterShift() so i is not global. (Thanks to PŽter Szab— for finding that bug) // // v 5.3 21 Sep 2009 // - added randProbPrime(k) for probable primes // - unrolled loop in mont_ (slightly faster) // - millerRabin now takes a bigInt parameter rather than an int // // v 5.2 15 Sep 2009 // - fixed capitalization in call to int2bigInt in randBigInt // (thanks to Emili Evripidou, Reinhold Behringer, and Samuel Macaleese for finding that bug) // // v 5.1 8 Oct 2007 // - renamed inverseModInt_ to inverseModInt since it doesn't change its parameters // - added functions GCD and randBigInt, which call GCD_ and randBigInt_ // - fixed a bug found by Rob Visser (see comment with his name below) // - improved comments // // This file is public domain. You can use it for any purpose without restriction. // I do not guarantee that it is correct, so use it at your own risk. If you use // it for something interesting, I'd appreciate hearing about it. If you find // any bugs or make any improvements, I'd appreciate hearing about those too. // It would also be nice if my name and URL were left in the comments. But none // of that is required. // // This code defines a bigInt library for arbitrary-precision integers. // 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; they always allocate new memory for the answer that is returned. // // These functions are designed to avoid frequent dynamic memory allocation in the inner loop. // For most functions, if it needs a BigInt as a local variable it will actually use // a global, and will only allocate to it only when it's not the right size. This ensures // that when a function is called repeatedly with same-sized parameters, it only allocates // memory on the first call. // // Note that for cryptographic purposes, the calls to Math.random() must // be replaced with calls to a better pseudorandom number generator. // // In the following, "bigInt" means a bigInt with at least one leading zero element, // and "integer" means a nonnegative integer less than radix. In some cases, integer // can be negative. Negative bigInts are 2s complement. // // The following functions do not modify their inputs. // Those returning a bigInt, string, or Array will dynamically allocate memory for that value. // Those returning a boolean will return the integer 0 (false) or 1 (true). // Those returning boolean or int will not allocate memory except possibly on the first // time they're called with a given parameter size. // // bigInt add(x,y) //return (x+y) for bigInts x and y. // bigInt addInt(x,n) //return (x+n) where x is a bigInt and n is an integer. // string bigInt2str(x,base) //return a string form of bigInt x in a given base, with 2 <= base <= 95 // int bitSize(x) //return how many bits long the bigInt x is, not counting leading zeros // bigInt dup(x) //return a copy of bigInt x // boolean equals(x,y) //is the bigInt x equal to the bigint y? // boolean equalsInt(x,y) //is bigint x equal to integer y? // bigInt expand(x,n) //return a copy of x with at least n elements, adding leading zeros if needed // Array findPrimes(n) //return array of all primes less than integer n // bigInt GCD(x,y) //return greatest common divisor of bigInts x and y (each with same number of elements). // boolean greater(x,y) //is x>y? (x and y are nonnegative bigInts) // boolean greaterShift(x,y,shift)//is (x <<(shift*bpe)) > y? // bigInt int2bigInt(t,n,m) //return a bigInt equal to integer t, with at least n bits and m array elements // bigInt inverseMod(x,n) //return (x**(-1) mod n) for bigInts x and n. If no inverse exists, it returns null // int inverseModInt(x,n) //return x**(-1) mod n, for integers x and n. Return 0 if there is no inverse // boolean isZero(x) //is the bigInt x equal to zero? // boolean millerRabin(x,b) //does one round of Miller-Rabin base integer b say that bigInt x is possibly prime? (b is bigInt, 1=1). If s=1, then the most significant of those n bits is set to 1. // bigInt randTruePrime(k) //return a new, random, k-bit, true prime bigInt using Maurer's algorithm. // bigInt randProbPrime(k) //return a new, random, k-bit, probable prime bigInt (probability it's composite less than 2^-80). // bigInt str2bigInt(s,b,n,m) //return a bigInt for number represented in string s in base b with at least n bits and m array elements // bigInt sub(x,y) //return (x-y) for bigInts x and y. Negative answers will be 2s complement // bigInt trim(x,k) //return a copy of x with exactly k leading zero elements // // // The following functions each have a non-underscored version, which most users should call instead. // These functions each write to a single parameter, and the caller is responsible for ensuring the array // passed in is large enough to hold the result. // // void addInt_(x,n) //do x=x+n where x is a bigInt and n is an integer // void add_(x,y) //do x=x+y for bigInts x and y // void copy_(x,y) //do x=y on bigInts x and y // void copyInt_(x,n) //do x=n on bigInt x and integer n // void GCD_(x,y) //set x to the greatest common divisor of bigInts x and y, (y is destroyed). (This never overflows its array). // boolean inverseMod_(x,n) //do x=x**(-1) mod n, for bigInts x and n. Returns 1 (0) if inverse does (doesn't) exist // void mod_(x,n) //do x=x mod n for bigInts x and n. (This never overflows its array). // void mult_(x,y) //do x=x*y for bigInts x and y. // void multMod_(x,y,n) //do x=x*y mod n for bigInts x,y,n. // void powMod_(x,y,n) //do x=x**y mod n, where x,y,n are bigInts (n is odd) and ** is exponentiation. 0**0=1. // void randBigInt_(b,n,s) //do b = an n-bit random BigInt. if s=1, then nth bit (most significant bit) is set to 1. n>=1. // void randTruePrime_(ans,k) //do ans = a random k-bit true random prime (not just probable prime) with 1 in the msb. // void sub_(x,y) //do x=x-y for bigInts x and y. Negative answers will be 2s complement. // // The following functions do NOT have a non-underscored version. // They each write a bigInt result to one or more parameters. The caller is responsible for // ensuring the arrays passed in are large enough to hold the results. // // void addShift_(x,y,ys) //do x=x+(y<<(ys*bpe)) // void carry_(x) //do carries and borrows so each element of the bigInt x fits in bpe bits. // void divide_(x,y,q,r) //divide x by y giving quotient q and remainder r // int divInt_(x,n) //do x=floor(x/n) for bigInt x and integer n, and return the remainder. (This never overflows its array). // int eGCD_(x,y,d,a,b) //sets a,b,d to positive bigInts such that d = GCD_(x,y) = a*x-b*y // void halve_(x) //do x=floor(|x|/2)*sgn(x) for bigInt x in 2's complement. (This never overflows its array). // void leftShift_(x,n) //left shift bigInt x by n bits. n64 multiplier, but not with JavaScript's 32*32->32) // - speeding up mont_(x,y,n,np) when x==y by doing a non-modular, non-Montgomery square // followed by a Montgomery reduction. The intermediate answer will be twice as long as x, so that // method would be slower. This is unfortunate because the code currently spends almost all of its time // doing mont_(x,x,...), both for randTruePrime_() and powMod_(). A faster method for Montgomery squaring // would have a large impact on the speed of randTruePrime_() and powMod_(). HAC has a couple of poorly-worded // sentences that seem to imply it's faster to do a non-modular square followed by a single // Montgomery reduction, but that's obviously wrong. ////////////////////////////////////////////////////////////////////////////////////////