sat_docs: scripts/minifier/otr/dep/bigint.js annotate

annotate scripts/minifier/otr/dep/bigint.js @ 103:e69883c1ec30

docker (libervia_cont): added a "status" command: - if libervia container is not running, it exits with error code 1 - if libervia container is running but no server is launched, it exits with error code 2 - if libervia container is running and server is launcher, it exits with error code 0 (success) server detection is done by doing a simple grep on logs, that's not perfectly reliable (ports can be changed in configuration, even if that doesn't really make sense in Docker context) but should be good enough for this purpose.

author	Goffi <goffi@goffi.org>
date	Sat, 27 Feb 2016 00:45:40 +0100
parents	1596660ddf72
children

rev	line source
12 1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1 ;(function (root, factory) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	2
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	3 if (typeof define === 'function' && define.amd) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	4 define(factory.bind(root, root.crypto \|\| root.msCrypto))
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	5 } else if (typeof module !== 'undefined' && module.exports) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	6 module.exports = factory(require('crypto'))
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	7 } else {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	8 root.BigInt = factory(root.crypto \|\| root.msCrypto)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	9 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	10
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	11 }(this, function (crypto) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	12
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	13 ////////////////////////////////////////////////////////////////////////////////////////
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	14 // Big Integer Library v. 5.5
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	15 // Created 2000, last modified 2013
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	16 // Leemon Baird
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	17 // www.leemon.com
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	18 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	19 // Version history:
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	20 // v 5.5 17 Mar 2013
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	21 // - two lines of a form like "if (x<0) x+=n" had the "if" changed to "while" to
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	22 // handle the case when x<-n. (Thanks to James Ansell for finding that bug)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	23 // v 5.4 3 Oct 2009
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	24 // - added "var i" to greaterShift() so i is not global. (Thanks to Péter Szabó for finding that bug)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	25 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	26 // v 5.3 21 Sep 2009
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	27 // - added randProbPrime(k) for probable primes
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	28 // - unrolled loop in mont_ (slightly faster)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	29 // - millerRabin now takes a bigInt parameter rather than an int
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	30 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	31 // v 5.2 15 Sep 2009
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	32 // - fixed capitalization in call to int2bigInt in randBigInt
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	33 // (thanks to Emili Evripidou, Reinhold Behringer, and Samuel Macaleese for finding that bug)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	34 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	35 // v 5.1 8 Oct 2007
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	36 // - renamed inverseModInt_ to inverseModInt since it doesn't change its parameters
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	37 // - added functions GCD and randBigInt, which call GCD_ and randBigInt_
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	38 // - fixed a bug found by Rob Visser (see comment with his name below)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	39 // - improved comments
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	40 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	41 // This file is public domain. You can use it for any purpose without restriction.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	42 // I do not guarantee that it is correct, so use it at your own risk. If you use
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	43 // it for something interesting, I'd appreciate hearing about it. If you find
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	44 // any bugs or make any improvements, I'd appreciate hearing about those too.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	45 // It would also be nice if my name and URL were left in the comments. But none
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	46 // of that is required.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	47 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	48 // This code defines a bigInt library for arbitrary-precision integers.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	49 // A bigInt is an array of integers storing the value in chunks of bpe bits,
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	50 // little endian (buff[0] is the least significant word).
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	51 // Negative bigInts are stored two's complement. Almost all the functions treat
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	52 // bigInts as nonnegative. The few that view them as two's complement say so
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	53 // in their comments. Some functions assume their parameters have at least one
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	54 // leading zero element. Functions with an underscore at the end of the name put
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	55 // their answer into one of the arrays passed in, and have unpredictable behavior
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	56 // in case of overflow, so the caller must make sure the arrays are big enough to
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	57 // hold the answer. But the average user should never have to call any of the
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	58 // underscored functions. Each important underscored function has a wrapper function
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	59 // of the same name without the underscore that takes care of the details for you.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	60 // For each underscored function where a parameter is modified, that same variable
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	61 // must not be used as another argument too. So, you cannot square x by doing
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	62 // multMod_(x,x,n). You must use squareMod_(x,n) instead, or do y=dup(x); multMod_(x,y,n).
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	63 // Or simply use the multMod(x,x,n) function without the underscore, where
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	64 // such issues never arise, because non-underscored functions never change
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	65 // their parameters; they always allocate new memory for the answer that is returned.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	66 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	67 // These functions are designed to avoid frequent dynamic memory allocation in the inner loop.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	68 // For most functions, if it needs a BigInt as a local variable it will actually use
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	69 // a global, and will only allocate to it only when it's not the right size. This ensures
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	70 // that when a function is called repeatedly with same-sized parameters, it only allocates
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	71 // memory on the first call.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	72 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	73 // Note that for cryptographic purposes, the calls to Math.random() must
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	74 // be replaced with calls to a better pseudorandom number generator.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	75 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	76 // In the following, "bigInt" means a bigInt with at least one leading zero element,
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	77 // and "integer" means a nonnegative integer less than radix. In some cases, integer
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	78 // can be negative. Negative bigInts are 2s complement.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	79 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	80 // The following functions do not modify their inputs.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	81 // Those returning a bigInt, string, or Array will dynamically allocate memory for that value.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	82 // Those returning a boolean will return the integer 0 (false) or 1 (true).
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	83 // Those returning boolean or int will not allocate memory except possibly on the first
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	84 // time they're called with a given parameter size.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	85 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	86 // bigInt add(x,y) //return (x+y) for bigInts x and y.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	87 // bigInt addInt(x,n) //return (x+n) where x is a bigInt and n is an integer.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	88 // string bigInt2str(x,base) //return a string form of bigInt x in a given base, with 2 <= base <= 95
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	89 // int bitSize(x) //return how many bits long the bigInt x is, not counting leading zeros
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	90 // bigInt dup(x) //return a copy of bigInt x
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	91 // boolean equals(x,y) //is the bigInt x equal to the bigint y?
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	92 // boolean equalsInt(x,y) //is bigint x equal to integer y?
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	93 // bigInt expand(x,n) //return a copy of x with at least n elements, adding leading zeros if needed
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	94 // Array findPrimes(n) //return array of all primes less than integer n
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	95 // bigInt GCD(x,y) //return greatest common divisor of bigInts x and y (each with same number of elements).
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	96 // boolean greater(x,y) //is x>y? (x and y are nonnegative bigInts)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	97 // boolean greaterShift(x,y,shift)//is (x <<(shift*bpe)) > y?
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	98 // bigInt int2bigInt(t,n,m) //return a bigInt equal to integer t, with at least n bits and m array elements
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	99 // bigInt inverseMod(x,n) //return (x**(-1) mod n) for bigInts x and n. If no inverse exists, it returns null
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	100 // int inverseModInt(x,n) //return x**(-1) mod n, for integers x and n. Return 0 if there is no inverse
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	101 // boolean isZero(x) //is the bigInt x equal to zero?
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	102 // boolean millerRabin(x,b) //does one round of Miller-Rabin base integer b say that bigInt x is possibly prime? (b is bigInt, 1<b<x)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	103 // boolean millerRabinInt(x,b) //does one round of Miller-Rabin base integer b say that bigInt x is possibly prime? (b is int, 1<b<x)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	104 // bigInt mod(x,n) //return a new bigInt equal to (x mod n) for bigInts x and n.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	105 // int modInt(x,n) //return x mod n for bigInt x and integer n.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	106 // bigInt mult(x,y) //return x*y for bigInts x and y. This is faster when y<x.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	107 // bigInt multMod(x,y,n) //return (x*y mod n) for bigInts x,y,n. For greater speed, let y<x.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	108 // boolean negative(x) //is bigInt x negative?
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	109 // bigInt powMod(x,y,n) //return (xy mod n) where x,y,n are bigInts and is exponentiation. 0**0=1. Faster for odd n.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	110 // bigInt randBigInt(n,s) //return an n-bit random BigInt (n>=1). If s=1, then the most significant of those n bits is set to 1.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	111 // bigInt randTruePrime(k) //return a new, random, k-bit, true prime bigInt using Maurer's algorithm.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	112 // bigInt randProbPrime(k) //return a new, random, k-bit, probable prime bigInt (probability it's composite less than 2^-80).
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	113 // 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
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	114 // bigInt sub(x,y) //return (x-y) for bigInts x and y. Negative answers will be 2s complement
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	115 // bigInt trim(x,k) //return a copy of x with exactly k leading zero elements
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	116 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	117 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	118 // The following functions each have a non-underscored version, which most users should call instead.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	119 // These functions each write to a single parameter, and the caller is responsible for ensuring the array
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	120 // passed in is large enough to hold the result.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	121 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	122 // void addInt_(x,n) //do x=x+n where x is a bigInt and n is an integer
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	123 // void add_(x,y) //do x=x+y for bigInts x and y
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	124 // void copy_(x,y) //do x=y on bigInts x and y
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	125 // void copyInt_(x,n) //do x=n on bigInt x and integer n
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	126 // void GCD_(x,y) //set x to the greatest common divisor of bigInts x and y, (y is destroyed). (This never overflows its array).
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	127 // boolean inverseMod_(x,n) //do x=x**(-1) mod n, for bigInts x and n. Returns 1 (0) if inverse does (doesn't) exist
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	128 // void mod_(x,n) //do x=x mod n for bigInts x and n. (This never overflows its array).
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	129 // void mult_(x,y) //do x=x*y for bigInts x and y.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	130 // void multMod_(x,y,n) //do x=x*y mod n for bigInts x,y,n.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	131 // void powMod_(x,y,n) //do x=xy mod n, where x,y,n are bigInts (n is odd) and is exponentiation. 0**0=1.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	132 // 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.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	133 // void randTruePrime_(ans,k) //do ans = a random k-bit true random prime (not just probable prime) with 1 in the msb.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	134 // void sub_(x,y) //do x=x-y for bigInts x and y. Negative answers will be 2s complement.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	135 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	136 // The following functions do NOT have a non-underscored version.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	137 // They each write a bigInt result to one or more parameters. The caller is responsible for
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	138 // ensuring the arrays passed in are large enough to hold the results.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	139 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	140 // void addShift_(x,y,ys) //do x=x+(y<<(ys*bpe))
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	141 // void carry_(x) //do carries and borrows so each element of the bigInt x fits in bpe bits.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	142 // void divide_(x,y,q,r) //divide x by y giving quotient q and remainder r
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	143 // int divInt_(x,n) //do x=floor(x/n) for bigInt x and integer n, and return the remainder. (This never overflows its array).
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	144 // int eGCD_(x,y,d,a,b) //sets a,b,d to positive bigInts such that d = GCD_(x,y) = ax-by
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	145 // void halve_(x) //do x=floor(\|x\|/2)*sgn(x) for bigInt x in 2's complement. (This never overflows its array).
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	146 // void leftShift_(x,n) //left shift bigInt x by n bits. n<bpe.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	147 // void linComb_(x,y,a,b) //do x=ax+by for bigInts x and y and integers a and b
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	148 // void linCombShift_(x,y,b,ys) //do x=x+b(y<<(ysbpe)) for bigInts x and y, and integers b and ys
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	149 // void mont_(x,y,n,np) //Montgomery multiplication (see comments where the function is defined)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	150 // void multInt_(x,n) //do x=x*n where x is a bigInt and n is an integer.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	151 // void rightShift_(x,n) //right shift bigInt x by n bits. (This never overflows its array).
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	152 // void squareMod_(x,n) //do x=x*x mod n for bigInts x,n
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	153 // void subShift_(x,y,ys) //do x=x-(y<<(ys*bpe)). Negative answers will be 2s complement.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	154 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	155 // The following functions are based on algorithms from the _Handbook of Applied Cryptography_
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	156 // powMod_() = algorithm 14.94, Montgomery exponentiation
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	157 // eGCD_,inverseMod_() = algorithm 14.61, Binary extended GCD_
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	158 // GCD_() = algorothm 14.57, Lehmer's algorithm
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	159 // mont_() = algorithm 14.36, Montgomery multiplication
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	160 // divide_() = algorithm 14.20 Multiple-precision division
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	161 // squareMod_() = algorithm 14.16 Multiple-precision squaring
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	162 // randTruePrime_() = algorithm 4.62, Maurer's algorithm
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	163 // millerRabin() = algorithm 4.24, Miller-Rabin algorithm
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	164 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	165 // Profiling shows:
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	166 // randTruePrime_() spends:
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	167 // 10% of its time in calls to powMod_()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	168 // 85% of its time in calls to millerRabin()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	169 // millerRabin() spends:
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	170 // 99% of its time in calls to powMod_() (always with a base of 2)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	171 // powMod_() spends:
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	172 // 94% of its time in calls to mont_() (almost always with x==y)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	173 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	174 // This suggests there are several ways to speed up this library slightly:
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	175 // - convert powMod_ to use a Montgomery form of k-ary window (or maybe a Montgomery form of sliding window)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	176 // -- this should especially focus on being fast when raising 2 to a power mod n
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	177 // - convert randTruePrime_() to use a minimum r of 1/3 instead of 1/2 with the appropriate change to the test
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	178 // - tune the parameters in randTruePrime_(), including c, m, and recLimit
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	179 // - speed up the single loop in mont_() that takes 95% of the runtime, perhaps by reducing checking
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	180 // within the loop when all the parameters are the same length.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	181 //
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	182 // There are several ideas that look like they wouldn't help much at all:
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	183 // - replacing trial division in randTruePrime_() with a sieve (that speeds up something taking almost no time anyway)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	184 // - increase bpe from 15 to 30 (that would help if we had a 3232->64 multiplier, but not with JavaScript's 3232->32)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	185 // - speeding up mont_(x,y,n,np) when x==y by doing a non-modular, non-Montgomery square
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	186 // followed by a Montgomery reduction. The intermediate answer will be twice as long as x, so that
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	187 // method would be slower. This is unfortunate because the code currently spends almost all of its time
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	188 // doing mont_(x,x,...), both for randTruePrime_() and powMod_(). A faster method for Montgomery squaring
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	189 // would have a large impact on the speed of randTruePrime_() and powMod_(). HAC has a couple of poorly-worded
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	190 // sentences that seem to imply it's faster to do a non-modular square followed by a single
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	191 // Montgomery reduction, but that's obviously wrong.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	192 ////////////////////////////////////////////////////////////////////////////////////////
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	193
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	194 //globals
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	195
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	196 // The number of significant bits in the fraction of a JavaScript
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	197 // floating-point number is 52, independent of platform.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	198 // See: https://github.com/arlolra/otr/issues/41
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	199
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	200 var bpe = 26; // bits stored per array element
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	201 var radix = 1 << bpe; // equals 2^bpe
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	202 var mask = radix - 1; // AND this with an array element to chop it down to bpe bits
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	203
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	204 //the digits for converting to different bases
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	205 var digitsStr='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_=!@#$%^&*()[]{}\|;:,.<>/?`~ \\\'\"+-';
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	206
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	207 var one=int2bigInt(1,1,1); //constant used in powMod_()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	208
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	209 //the following global variables are scratchpad memory to
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	210 //reduce dynamic memory allocation in the inner loop
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	211 var t=new Array(0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	212 var ss=t; //used in mult_()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	213 var s0=t; //used in multMod_(), squareMod_()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	214 var s1=t; //used in powMod_(), multMod_(), squareMod_()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	215 var s2=t; //used in powMod_(), multMod_()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	216 var s3=t; //used in powMod_()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	217 var s4=t, s5=t; //used in mod_()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	218 var s6=t; //used in bigInt2str()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	219 var s7=t; //used in powMod_()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	220 var T=t; //used in GCD_()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	221 var sa=t; //used in mont_()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	222 var mr_x1=t, mr_r=t, mr_a=t; //used in millerRabin()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	223 var eg_v=t, eg_u=t, eg_A=t, eg_B=t, eg_C=t, eg_D=t; //used in eGCD_(), inverseMod_()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	224 var md_q1=t, md_q2=t, md_q3=t, md_r=t, md_r1=t, md_r2=t, md_tt=t; //used in mod_()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	225
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	226 var primes=t, pows=t, s_i=t, s_i2=t, s_R=t, s_rm=t, s_q=t, s_n1=t;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	227 var s_a=t, s_r2=t, s_n=t, s_b=t, s_d=t, s_x1=t, s_x2=t, s_aa=t; //used in randTruePrime_()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	228
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	229 var rpprb=t; //used in randProbPrimeRounds() (which also uses "primes")
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	230
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	231 ////////////////////////////////////////////////////////////////////////////////////////
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	232
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	233
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	234 //return array of all primes less than integer n
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	235 function findPrimes(n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	236 var i,s,p,ans;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	237 s=new Array(n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	238 for (i=0;i<n;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	239 s[i]=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	240 s[0]=2;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	241 p=0; //first p elements of s are primes, the rest are a sieve
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	242 for(;s[p]<n;) { //s[p] is the pth prime
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	243 for(i=s[p]*s[p]; i<n; i+=s[p]) //mark multiples of s[p]
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	244 s[i]=1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	245 p++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	246 s[p]=s[p-1]+1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	247 for(; s[p]<n && s[s[p]]; s[p]++); //find next prime (where s[p]==0)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	248 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	249 ans=new Array(p);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	250 for(i=0;i<p;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	251 ans[i]=s[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	252 return ans;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	253 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	254
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	255
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	256 //does a single round of Miller-Rabin base b consider x to be a possible prime?
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	257 //x is a bigInt, and b is an integer, with b<x
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	258 function millerRabinInt(x,b) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	259 if (mr_x1.length!=x.length) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	260 mr_x1=dup(x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	261 mr_r=dup(x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	262 mr_a=dup(x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	263 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	264
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	265 copyInt_(mr_a,b);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	266 return millerRabin(x,mr_a);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	267 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	268
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	269 //does a single round of Miller-Rabin base b consider x to be a possible prime?
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	270 //x and b are bigInts with b<x
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	271 function millerRabin(x,b) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	272 var i,j,k,s;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	273
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	274 if (mr_x1.length!=x.length) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	275 mr_x1=dup(x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	276 mr_r=dup(x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	277 mr_a=dup(x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	278 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	279
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	280 copy_(mr_a,b);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	281 copy_(mr_r,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	282 copy_(mr_x1,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	283
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	284 addInt_(mr_r,-1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	285 addInt_(mr_x1,-1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	286
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	287 //s=the highest power of two that divides mr_r
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	288
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	289 /*
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	290 k=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	291 for (i=0;i<mr_r.length;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	292 for (j=1;j<mask;j<<=1)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	293 if (x[i] & j) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	294 s=(k<mr_r.length+bpe ? k : 0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	295 i=mr_r.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	296 j=mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	297 } else
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	298 k++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	299 */
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	300
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	301 /* http://www.javascripter.net/math/primes/millerrabinbug-bigint54.htm */
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	302 if (isZero(mr_r)) return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	303 for (k=0; mr_r[k]==0; k++);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	304 for (i=1,j=2; mr_r[k]%j==0; j*=2,i++ );
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	305 s = k*bpe + i - 1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	306 /* end */
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	307
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	308 if (s)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	309 rightShift_(mr_r,s);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	310
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	311 powMod_(mr_a,mr_r,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	312
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	313 if (!equalsInt(mr_a,1) && !equals(mr_a,mr_x1)) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	314 j=1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	315 while (j<=s-1 && !equals(mr_a,mr_x1)) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	316 squareMod_(mr_a,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	317 if (equalsInt(mr_a,1)) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	318 return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	319 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	320 j++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	321 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	322 if (!equals(mr_a,mr_x1)) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	323 return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	324 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	325 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	326 return 1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	327 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	328
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	329 //returns how many bits long the bigInt is, not counting leading zeros.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	330 function bitSize(x) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	331 var j,z,w;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	332 for (j=x.length-1; (x[j]==0) && (j>0); j--);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	333 for (z=0,w=x[j]; w; (w>>=1),z++);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	334 z+=bpe*j;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	335 return z;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	336 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	337
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	338 //return a copy of x with at least n elements, adding leading zeros if needed
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	339 function expand(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	340 var ans=int2bigInt(0,(x.length>n ? x.length : n)*bpe,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	341 copy_(ans,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	342 return ans;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	343 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	344
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	345 //return a k-bit true random prime using Maurer's algorithm.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	346 function randTruePrime(k) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	347 var ans=int2bigInt(0,k,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	348 randTruePrime_(ans,k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	349 return trim(ans,1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	350 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	351
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	352 //return a k-bit random probable prime with probability of error < 2^-80
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	353 function randProbPrime(k) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	354 if (k>=600) return randProbPrimeRounds(k,2); //numbers from HAC table 4.3
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	355 if (k>=550) return randProbPrimeRounds(k,4);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	356 if (k>=500) return randProbPrimeRounds(k,5);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	357 if (k>=400) return randProbPrimeRounds(k,6);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	358 if (k>=350) return randProbPrimeRounds(k,7);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	359 if (k>=300) return randProbPrimeRounds(k,9);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	360 if (k>=250) return randProbPrimeRounds(k,12); //numbers from HAC table 4.4
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	361 if (k>=200) return randProbPrimeRounds(k,15);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	362 if (k>=150) return randProbPrimeRounds(k,18);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	363 if (k>=100) return randProbPrimeRounds(k,27);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	364 return randProbPrimeRounds(k,40); //number from HAC remark 4.26 (only an estimate)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	365 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	366
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	367 //return a k-bit probable random prime using n rounds of Miller Rabin (after trial division with small primes)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	368 function randProbPrimeRounds(k,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	369 var ans, i, divisible, B;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	370 B=30000; //B is largest prime to use in trial division
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	371 ans=int2bigInt(0,k,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	372
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	373 //optimization: try larger and smaller B to find the best limit.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	374
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	375 if (primes.length==0)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	376 primes=findPrimes(30000); //check for divisibility by primes <=30000
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	377
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	378 if (rpprb.length!=ans.length)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	379 rpprb=dup(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	380
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	381 for (;;) { //keep trying random values for ans until one appears to be prime
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	382 //optimization: pick a random number times L=235...p, plus a
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	383 // random element of the list of all numbers in [0,L) not divisible by any prime up to p.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	384 // This can reduce the amount of random number generation.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	385
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	386 randBigInt_(ans,k,0); //ans = a random odd number to check
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	387 ans[0] \|= 1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	388 divisible=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	389
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	390 //check ans for divisibility by small primes up to B
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	391 for (i=0; (i<primes.length) && (primes[i]<=B); i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	392 if (modInt(ans,primes[i])==0 && !equalsInt(ans,primes[i])) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	393 divisible=1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	394 break;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	395 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	396
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	397 //optimization: change millerRabin so the base can be bigger than the number being checked, then eliminate the while here.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	398
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	399 //do n rounds of Miller Rabin, with random bases less than ans
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	400 for (i=0; i<n && !divisible; i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	401 randBigInt_(rpprb,k,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	402 while(!greater(ans,rpprb)) //pick a random rpprb that's < ans
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	403 randBigInt_(rpprb,k,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	404 if (!millerRabin(ans,rpprb))
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	405 divisible=1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	406 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	407
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	408 if(!divisible)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	409 return ans;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	410 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	411 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	412
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	413 //return a new bigInt equal to (x mod n) for bigInts x and n.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	414 function mod(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	415 var ans=dup(x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	416 mod_(ans,n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	417 return trim(ans,1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	418 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	419
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	420 //return (x+n) where x is a bigInt and n is an integer.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	421 function addInt(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	422 var ans=expand(x,x.length+1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	423 addInt_(ans,n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	424 return trim(ans,1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	425 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	426
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	427 //return x*y for bigInts x and y. This is faster when y<x.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	428 function mult(x,y) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	429 var ans=expand(x,x.length+y.length);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	430 mult_(ans,y);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	431 return trim(ans,1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	432 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	433
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	434 //return (xy mod n) where x,y,n are bigInts and is exponentiation. 0**0=1. Faster for odd n.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	435 function powMod(x,y,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	436 var ans=expand(x,n.length);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	437 powMod_(ans,trim(y,2),trim(n,2),0); //this should work without the trim, but doesn't
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	438 return trim(ans,1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	439 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	440
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	441 //return (x-y) for bigInts x and y. Negative answers will be 2s complement
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	442 function sub(x,y) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	443 var ans=expand(x,(x.length>y.length ? x.length+1 : y.length+1));
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	444 sub_(ans,y);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	445 return trim(ans,1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	446 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	447
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	448 //return (x+y) for bigInts x and y.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	449 function add(x,y) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	450 var ans=expand(x,(x.length>y.length ? x.length+1 : y.length+1));
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	451 add_(ans,y);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	452 return trim(ans,1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	453 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	454
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	455 //return (x**(-1) mod n) for bigInts x and n. If no inverse exists, it returns null
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	456 function inverseMod(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	457 var ans=expand(x,n.length);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	458 var s;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	459 s=inverseMod_(ans,n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	460 return s ? trim(ans,1) : null;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	461 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	462
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	463 //return (x*y mod n) for bigInts x,y,n. For greater speed, let y<x.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	464 function multMod(x,y,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	465 var ans=expand(x,n.length);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	466 multMod_(ans,y,n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	467 return trim(ans,1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	468 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	469
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	470 //generate a k-bit true random prime using Maurer's algorithm,
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	471 //and put it into ans. The bigInt ans must be large enough to hold it.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	472 function randTruePrime_(ans,k) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	473 var c,w,m,pm,dd,j,r,B,divisible,z,zz,recSize,recLimit;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	474
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	475 if (primes.length==0)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	476 primes=findPrimes(30000); //check for divisibility by primes <=30000
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	477
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	478 if (pows.length==0) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	479 pows=new Array(512);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	480 for (j=0;j<512;j++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	481 pows[j]=Math.pow(2,j/511.0-1.0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	482 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	483 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	484
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	485 //c and m should be tuned for a particular machine and value of k, to maximize speed
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	486 c=0.1; //c=0.1 in HAC
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	487 m=20; //generate this k-bit number by first recursively generating a number that has between k/2 and k-m bits
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	488 recLimit=20; //stop recursion when k <=recLimit. Must have recLimit >= 2
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	489
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	490 if (s_i2.length!=ans.length) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	491 s_i2=dup(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	492 s_R =dup(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	493 s_n1=dup(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	494 s_r2=dup(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	495 s_d =dup(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	496 s_x1=dup(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	497 s_x2=dup(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	498 s_b =dup(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	499 s_n =dup(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	500 s_i =dup(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	501 s_rm=dup(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	502 s_q =dup(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	503 s_a =dup(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	504 s_aa=dup(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	505 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	506
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	507 if (k <= recLimit) { //generate small random primes by trial division up to its square root
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	508 pm=(1<<((k+2)>>1))-1; //pm is binary number with all ones, just over sqrt(2^k)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	509 copyInt_(ans,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	510 for (dd=1;dd;) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	511 dd=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	512 ans[0]= 1 \| (1<<(k-1)) \| randomBitInt(k); //random, k-bit, odd integer, with msb 1
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	513 for (j=1;(j<primes.length) && ((primes[j]&pm)==primes[j]);j++) { //trial division by all primes 3...sqrt(2^k)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	514 if (0==(ans[0]%primes[j])) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	515 dd=1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	516 break;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	517 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	518 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	519 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	520 carry_(ans);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	521 return;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	522 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	523
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	524 B=ckk; //try small primes up to B (or all the primes[] array if the largest is less than B).
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	525 if (k>2*m) //generate this k-bit number by first recursively generating a number that has between k/2 and k-m bits
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	526 for (r=1; k-k*r<=m; )
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	527 r=pows[randomBitInt(9)]; //r=Math.pow(2,Math.random()-1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	528 else
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	529 r=0.5;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	530
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	531 //simulation suggests the more complex algorithm using r=.333 is only slightly faster.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	532
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	533 recSize=Math.floor(r*k)+1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	534
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	535 randTruePrime_(s_q,recSize);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	536 copyInt_(s_i2,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	537 s_i2[Math.floor((k-2)/bpe)] \|= (1<<((k-2)%bpe)); //s_i2=2^(k-2)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	538 divide_(s_i2,s_q,s_i,s_rm); //s_i=floor((2^(k-1))/(2q))
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	539
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	540 z=bitSize(s_i);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	541
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	542 for (;;) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	543 for (;;) { //generate z-bit numbers until one falls in the range [0,s_i-1]
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	544 randBigInt_(s_R,z,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	545 if (greater(s_i,s_R))
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	546 break;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	547 } //now s_R is in the range [0,s_i-1]
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	548 addInt_(s_R,1); //now s_R is in the range [1,s_i]
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	549 add_(s_R,s_i); //now s_R is in the range [s_i+1,2*s_i]
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	550
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	551 copy_(s_n,s_q);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	552 mult_(s_n,s_R);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	553 multInt_(s_n,2);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	554 addInt_(s_n,1); //s_n=2s_Rs_q+1
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	555
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	556 copy_(s_r2,s_R);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	557 multInt_(s_r2,2); //s_r2=2*s_R
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	558
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	559 //check s_n for divisibility by small primes up to B
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	560 for (divisible=0,j=0; (j<primes.length) && (primes[j]<B); j++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	561 if (modInt(s_n,primes[j])==0 && !equalsInt(s_n,primes[j])) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	562 divisible=1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	563 break;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	564 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	565
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	566 if (!divisible) //if it passes small primes check, then try a single Miller-Rabin base 2
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	567 if (!millerRabinInt(s_n,2)) //this line represents 75% of the total runtime for randTruePrime_
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	568 divisible=1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	569
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	570 if (!divisible) { //if it passes that test, continue checking s_n
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	571 addInt_(s_n,-3);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	572 for (j=s_n.length-1;(s_n[j]==0) && (j>0); j--); //strip leading zeros
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	573 for (zz=0,w=s_n[j]; w; (w>>=1),zz++);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	574 zz+=bpe*j; //zz=number of bits in s_n, ignoring leading zeros
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	575 for (;;) { //generate z-bit numbers until one falls in the range [0,s_n-1]
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	576 randBigInt_(s_a,zz,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	577 if (greater(s_n,s_a))
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	578 break;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	579 } //now s_a is in the range [0,s_n-1]
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	580 addInt_(s_n,3); //now s_a is in the range [0,s_n-4]
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	581 addInt_(s_a,2); //now s_a is in the range [2,s_n-2]
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	582 copy_(s_b,s_a);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	583 copy_(s_n1,s_n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	584 addInt_(s_n1,-1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	585 powMod_(s_b,s_n1,s_n); //s_b=s_a^(s_n-1) modulo s_n
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	586 addInt_(s_b,-1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	587 if (isZero(s_b)) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	588 copy_(s_b,s_a);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	589 powMod_(s_b,s_r2,s_n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	590 addInt_(s_b,-1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	591 copy_(s_aa,s_n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	592 copy_(s_d,s_b);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	593 GCD_(s_d,s_n); //if s_b and s_n are relatively prime, then s_n is a prime
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	594 if (equalsInt(s_d,1)) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	595 copy_(ans,s_aa);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	596 return; //if we've made it this far, then s_n is absolutely guaranteed to be prime
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	597 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	598 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	599 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	600 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	601 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	602
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	603 //Return an n-bit random BigInt (n>=1). If s=1, then the most significant of those n bits is set to 1.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	604 function randBigInt(n,s) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	605 var a,b;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	606 a=Math.floor((n-1)/bpe)+2; //# array elements to hold the BigInt with a leading 0 element
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	607 b=int2bigInt(0,0,a);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	608 randBigInt_(b,n,s);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	609 return b;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	610 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	611
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	612 //Set b to an n-bit random BigInt. If s=1, then the most significant of those n bits is set to 1.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	613 //Array b must be big enough to hold the result. Must have n>=1
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	614 function randBigInt_(b,n,s) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	615 var i,a;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	616 for (i=0;i<b.length;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	617 b[i]=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	618 a=Math.floor((n-1)/bpe)+1; //# array elements to hold the BigInt
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	619 for (i=0;i<a;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	620 b[i]=randomBitInt(bpe);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	621 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	622 b[a-1] &= (2<<((n-1)%bpe))-1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	623 if (s==1)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	624 b[a-1] \|= (1<<((n-1)%bpe));
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	625 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	626
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	627 //Return the greatest common divisor of bigInts x and y (each with same number of elements).
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	628 function GCD(x,y) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	629 var xc,yc;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	630 xc=dup(x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	631 yc=dup(y);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	632 GCD_(xc,yc);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	633 return xc;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	634 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	635
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	636 //set x to the greatest common divisor of bigInts x and y (each with same number of elements).
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	637 //y is destroyed.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	638 function GCD_(x,y) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	639 var i,xp,yp,A,B,C,D,q,sing,qp;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	640 if (T.length!=x.length)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	641 T=dup(x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	642
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	643 sing=1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	644 while (sing) { //while y has nonzero elements other than y[0]
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	645 sing=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	646 for (i=1;i<y.length;i++) //check if y has nonzero elements other than 0
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	647 if (y[i]) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	648 sing=1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	649 break;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	650 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	651 if (!sing) break; //quit when y all zero elements except possibly y[0]
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	652
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	653 for (i=x.length;!x[i] && i>=0;i--); //find most significant element of x
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	654 xp=x[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	655 yp=y[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	656 A=1; B=0; C=0; D=1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	657 while ((yp+C) && (yp+D)) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	658 q =Math.floor((xp+A)/(yp+C));
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	659 qp=Math.floor((xp+B)/(yp+D));
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	660 if (q!=qp)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	661 break;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	662 t= A-qC; A=C; C=t; // do (A,B,xp, C,D,yp) = (C,D,yp, A,B,xp) - q(0,0,0, C,D,yp)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	663 t= B-q*D; B=D; D=t;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	664 t=xp-q*yp; xp=yp; yp=t;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	665 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	666 if (B) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	667 copy_(T,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	668 linComb_(x,y,A,B); //x=Ax+By
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	669 linComb_(y,T,D,C); //y=Dy+CT
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	670 } else {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	671 mod_(x,y);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	672 copy_(T,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	673 copy_(x,y);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	674 copy_(y,T);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	675 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	676 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	677 if (y[0]==0)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	678 return;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	679 t=modInt(x,y[0]);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	680 copyInt_(x,y[0]);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	681 y[0]=t;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	682 while (y[0]) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	683 x[0]%=y[0];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	684 t=x[0]; x[0]=y[0]; y[0]=t;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	685 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	686 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	687
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	688 //do x=x**(-1) mod n, for bigInts x and n.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	689 //If no inverse exists, it sets x to zero and returns 0, else it returns 1.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	690 //The x array must be at least as large as the n array.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	691 function inverseMod_(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	692 var k=1+2*Math.max(x.length,n.length);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	693
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	694 if(!(x[0]&1) && !(n[0]&1)) { //if both inputs are even, then inverse doesn't exist
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	695 copyInt_(x,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	696 return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	697 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	698
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	699 if (eg_u.length!=k) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	700 eg_u=new Array(k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	701 eg_v=new Array(k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	702 eg_A=new Array(k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	703 eg_B=new Array(k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	704 eg_C=new Array(k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	705 eg_D=new Array(k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	706 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	707
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	708 copy_(eg_u,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	709 copy_(eg_v,n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	710 copyInt_(eg_A,1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	711 copyInt_(eg_B,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	712 copyInt_(eg_C,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	713 copyInt_(eg_D,1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	714 for (;;) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	715 while(!(eg_u[0]&1)) { //while eg_u is even
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	716 halve_(eg_u);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	717 if (!(eg_A[0]&1) && !(eg_B[0]&1)) { //if eg_A==eg_B==0 mod 2
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	718 halve_(eg_A);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	719 halve_(eg_B);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	720 } else {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	721 add_(eg_A,n); halve_(eg_A);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	722 sub_(eg_B,x); halve_(eg_B);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	723 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	724 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	725
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	726 while (!(eg_v[0]&1)) { //while eg_v is even
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	727 halve_(eg_v);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	728 if (!(eg_C[0]&1) && !(eg_D[0]&1)) { //if eg_C==eg_D==0 mod 2
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	729 halve_(eg_C);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	730 halve_(eg_D);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	731 } else {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	732 add_(eg_C,n); halve_(eg_C);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	733 sub_(eg_D,x); halve_(eg_D);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	734 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	735 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	736
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	737 if (!greater(eg_v,eg_u)) { //eg_v <= eg_u
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	738 sub_(eg_u,eg_v);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	739 sub_(eg_A,eg_C);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	740 sub_(eg_B,eg_D);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	741 } else { //eg_v > eg_u
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	742 sub_(eg_v,eg_u);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	743 sub_(eg_C,eg_A);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	744 sub_(eg_D,eg_B);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	745 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	746
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	747 if (equalsInt(eg_u,0)) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	748 while (negative(eg_C)) //make sure answer is nonnegative
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	749 add_(eg_C,n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	750 copy_(x,eg_C);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	751
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	752 if (!equalsInt(eg_v,1)) { //if GCD_(x,n)!=1, then there is no inverse
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	753 copyInt_(x,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	754 return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	755 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	756 return 1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	757 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	758 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	759 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	760
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	761 //return x**(-1) mod n, for integers x and n. Return 0 if there is no inverse
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	762 function inverseModInt(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	763 var a=1,b=0,t;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	764 for (;;) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	765 if (x==1) return a;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	766 if (x==0) return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	767 b-=a*Math.floor(n/x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	768 n%=x;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	769
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	770 if (n==1) return b; //to avoid negatives, change this b to n-b, and each -= to +=
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	771 if (n==0) return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	772 a-=b*Math.floor(x/n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	773 x%=n;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	774 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	775 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	776
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	777 //this deprecated function is for backward compatibility only.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	778 function inverseModInt_(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	779 return inverseModInt(x,n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	780 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	781
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	782
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	783 //Given positive bigInts x and y, change the bigints v, a, and b to positive bigInts such that:
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	784 // v = GCD_(x,y) = ax-by
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	785 //The bigInts v, a, b, must have exactly as many elements as the larger of x and y.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	786 function eGCD_(x,y,v,a,b) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	787 var g=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	788 var k=Math.max(x.length,y.length);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	789 if (eg_u.length!=k) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	790 eg_u=new Array(k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	791 eg_A=new Array(k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	792 eg_B=new Array(k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	793 eg_C=new Array(k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	794 eg_D=new Array(k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	795 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	796 while(!(x[0]&1) && !(y[0]&1)) { //while x and y both even
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	797 halve_(x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	798 halve_(y);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	799 g++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	800 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	801 copy_(eg_u,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	802 copy_(v,y);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	803 copyInt_(eg_A,1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	804 copyInt_(eg_B,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	805 copyInt_(eg_C,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	806 copyInt_(eg_D,1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	807 for (;;) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	808 while(!(eg_u[0]&1)) { //while u is even
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	809 halve_(eg_u);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	810 if (!(eg_A[0]&1) && !(eg_B[0]&1)) { //if A==B==0 mod 2
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	811 halve_(eg_A);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	812 halve_(eg_B);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	813 } else {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	814 add_(eg_A,y); halve_(eg_A);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	815 sub_(eg_B,x); halve_(eg_B);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	816 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	817 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	818
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	819 while (!(v[0]&1)) { //while v is even
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	820 halve_(v);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	821 if (!(eg_C[0]&1) && !(eg_D[0]&1)) { //if C==D==0 mod 2
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	822 halve_(eg_C);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	823 halve_(eg_D);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	824 } else {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	825 add_(eg_C,y); halve_(eg_C);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	826 sub_(eg_D,x); halve_(eg_D);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	827 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	828 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	829
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	830 if (!greater(v,eg_u)) { //v<=u
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	831 sub_(eg_u,v);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	832 sub_(eg_A,eg_C);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	833 sub_(eg_B,eg_D);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	834 } else { //v>u
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	835 sub_(v,eg_u);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	836 sub_(eg_C,eg_A);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	837 sub_(eg_D,eg_B);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	838 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	839 if (equalsInt(eg_u,0)) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	840 while (negative(eg_C)) { //make sure a (C) is nonnegative
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	841 add_(eg_C,y);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	842 sub_(eg_D,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	843 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	844 multInt_(eg_D,-1); ///make sure b (D) is nonnegative
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	845 copy_(a,eg_C);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	846 copy_(b,eg_D);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	847 leftShift_(v,g);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	848 return;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	849 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	850 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	851 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	852
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	853
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	854 //is bigInt x negative?
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	855 function negative(x) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	856 return ((x[x.length-1]>>(bpe-1))&1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	857 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	858
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	859
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	860 //is (x << (shift*bpe)) > y?
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	861 //x and y are nonnegative bigInts
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	862 //shift is a nonnegative integer
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	863 function greaterShift(x,y,shift) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	864 var i, kx=x.length, ky=y.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	865 var k=((kx+shift)<ky) ? (kx+shift) : ky;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	866 for (i=ky-1-shift; i<kx && i>=0; i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	867 if (x[i]>0)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	868 return 1; //if there are nonzeros in x to the left of the first column of y, then x is bigger
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	869 for (i=kx-1+shift; i<ky; i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	870 if (y[i]>0)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	871 return 0; //if there are nonzeros in y to the left of the first column of x, then x is not bigger
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	872 for (i=k-1; i>=shift; i--)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	873 if (x[i-shift]>y[i]) return 1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	874 else if (x[i-shift]<y[i]) return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	875 return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	876 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	877
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	878 //is x > y? (x and y both nonnegative)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	879 function greater(x,y) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	880 var i;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	881 var k=(x.length<y.length) ? x.length : y.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	882
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	883 for (i=x.length;i<y.length;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	884 if (y[i])
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	885 return 0; //y has more digits
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	886
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	887 for (i=y.length;i<x.length;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	888 if (x[i])
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	889 return 1; //x has more digits
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	890
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	891 for (i=k-1;i>=0;i--)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	892 if (x[i]>y[i])
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	893 return 1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	894 else if (x[i]<y[i])
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	895 return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	896 return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	897 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	898
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	899 //divide x by y giving quotient q and remainder r. (q=floor(x/y), r=x mod y). All 4 are bigints.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	900 //x must have at least one leading zero element.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	901 //y must be nonzero.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	902 //q and r must be arrays that are exactly the same length as x. (Or q can have more).
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	903 //Must have x.length >= y.length >= 2.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	904 function divide_(x,y,q,r) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	905 var kx, ky;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	906 var i,j,y1,y2,c,a,b;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	907 copy_(r,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	908 for (ky=y.length;y[ky-1]==0;ky--); //ky is number of elements in y, not including leading zeros
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	909
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	910 //normalize: ensure the most significant element of y has its highest bit set
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	911 b=y[ky-1];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	912 for (a=0; b; a++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	913 b>>=1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	914 a=bpe-a; //a is how many bits to shift so that the high order bit of y is leftmost in its array element
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	915 leftShift_(y,a); //multiply both by 1<<a now, then divide both by that at the end
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	916 leftShift_(r,a);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	917
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	918 //Rob Visser discovered a bug: the following line was originally just before the normalization.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	919 for (kx=r.length;r[kx-1]==0 && kx>ky;kx--); //kx is number of elements in normalized x, not including leading zeros
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	920
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	921 copyInt_(q,0); // q=0
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	922 while (!greaterShift(y,r,kx-ky)) { // while (leftShift_(y,kx-ky) <= r) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	923 subShift_(r,y,kx-ky); // r=r-leftShift_(y,kx-ky)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	924 q[kx-ky]++; // q[kx-ky]++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	925 } // }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	926
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	927 for (i=kx-1; i>=ky; i--) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	928 if (r[i]==y[ky-1])
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	929 q[i-ky]=mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	930 else
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	931 q[i-ky]=Math.floor((r[i]*radix+r[i-1])/y[ky-1]);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	932
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	933 //The following for(;;) loop is equivalent to the commented while loop,
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	934 //except that the uncommented version avoids overflow.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	935 //The commented loop comes from HAC, which assumes r[-1]==y[-1]==0
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	936 // while (q[i-ky](y[ky-1]radix+y[ky-2]) > r[i]radixradix+r[i-1]*radix+r[i-2])
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	937 // q[i-ky]--;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	938 for (;;) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	939 y2=(ky>1 ? y[ky-2] : 0)*q[i-ky];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	940 c=y2;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	941 y2=y2 & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	942 c = (c - y2) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	943 y1=c+q[i-ky]*y[ky-1];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	944 c=y1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	945 y1=y1 & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	946 c = (c - y1) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	947
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	948 if (c==r[i] ? y1==r[i-1] ? y2>(i>1 ? r[i-2] : 0) : y1>r[i-1] : c>r[i])
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	949 q[i-ky]--;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	950 else
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	951 break;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	952 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	953
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	954 linCombShift_(r,y,-q[i-ky],i-ky); //r=r-q[i-ky]*leftShift_(y,i-ky)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	955 if (negative(r)) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	956 addShift_(r,y,i-ky); //r=r+leftShift_(y,i-ky)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	957 q[i-ky]--;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	958 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	959 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	960
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	961 rightShift_(y,a); //undo the normalization step
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	962 rightShift_(r,a); //undo the normalization step
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	963 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	964
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	965 //do carries and borrows so each element of the bigInt x fits in bpe bits.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	966 function carry_(x) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	967 var i,k,c,b;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	968 k=x.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	969 c=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	970 for (i=0;i<k;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	971 c+=x[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	972 b=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	973 if (c<0) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	974 b = c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	975 b = -((c - b) / radix);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	976 c+=b*radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	977 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	978 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	979 c = ((c - x[i]) / radix) - b;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	980 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	981 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	982
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	983 //return x mod n for bigInt x and integer n.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	984 function modInt(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	985 var i,c=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	986 for (i=x.length-1; i>=0; i--)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	987 c=(c*radix+x[i])%n;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	988 return c;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	989 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	990
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	991 //convert the integer t into a bigInt with at least the given number of bits.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	992 //the returned array stores the bigInt in bpe-bit chunks, little endian (buff[0] is least significant word)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	993 //Pad the array with leading zeros so that it has at least minSize elements.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	994 //There will always be at least one leading 0 element.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	995 function int2bigInt(t,bits,minSize) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	996 var i,k, buff;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	997 k=Math.ceil(bits/bpe)+1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	998 k=minSize>k ? minSize : k;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	999 buff=new Array(k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1000 copyInt_(buff,t);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1001 return buff;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1002 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1003
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1004 //return the bigInt given a string representation in a given base.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1005 //Pad the array with leading zeros so that it has at least minSize elements.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1006 //If base=-1, then it reads in a space-separated list of array elements in decimal.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1007 //The array will always have at least one leading zero, unless base=-1.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1008 function str2bigInt(s,base,minSize) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1009 var d, i, j, x, y, kk;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1010 var k=s.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1011 if (base==-1) { //comma-separated list of array elements in decimal
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1012 x=new Array(0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1013 for (;;) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1014 y=new Array(x.length+1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1015 for (i=0;i<x.length;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1016 y[i+1]=x[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1017 y[0]=parseInt(s,10);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1018 x=y;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1019 d=s.indexOf(',',0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1020 if (d<1)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1021 break;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1022 s=s.substring(d+1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1023 if (s.length==0)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1024 break;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1025 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1026 if (x.length<minSize) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1027 y=new Array(minSize);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1028 copy_(y,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1029 return y;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1030 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1031 return x;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1032 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1033
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1034 // log2(base)*k
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1035 var bb = base, p = 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1036 var b = base == 1 ? k : 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1037 while (bb > 1) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1038 if (bb & 1) p = 1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1039 b += k;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1040 bb >>= 1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1041 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1042 b += p*k;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1043
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1044 x=int2bigInt(0,b,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1045 for (i=0;i<k;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1046 d=digitsStr.indexOf(s.substring(i,i+1),0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1047 if (base<=36 && d>=36) //convert lowercase to uppercase if base<=36
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1048 d-=26;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1049 if (d>=base \|\| d<0) { //stop at first illegal character
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1050 break;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1051 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1052 multInt_(x,base);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1053 addInt_(x,d);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1054 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1055
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1056 for (k=x.length;k>0 && !x[k-1];k--); //strip off leading zeros
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1057 k=minSize>k+1 ? minSize : k+1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1058 y=new Array(k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1059 kk=k<x.length ? k : x.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1060 for (i=0;i<kk;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1061 y[i]=x[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1062 for (;i<k;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1063 y[i]=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1064 return y;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1065 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1066
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1067 //is bigint x equal to integer y?
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1068 //y must have less than bpe bits
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1069 function equalsInt(x,y) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1070 var i;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1071 if (x[0]!=y)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1072 return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1073 for (i=1;i<x.length;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1074 if (x[i])
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1075 return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1076 return 1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1077 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1078
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1079 //are bigints x and y equal?
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1080 //this works even if x and y are different lengths and have arbitrarily many leading zeros
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1081 function equals(x,y) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1082 var i;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1083 var k=x.length<y.length ? x.length : y.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1084 for (i=0;i<k;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1085 if (x[i]!=y[i])
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1086 return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1087 if (x.length>y.length) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1088 for (;i<x.length;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1089 if (x[i])
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1090 return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1091 } else {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1092 for (;i<y.length;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1093 if (y[i])
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1094 return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1095 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1096 return 1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1097 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1098
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1099 //is the bigInt x equal to zero?
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1100 function isZero(x) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1101 var i;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1102 for (i=0;i<x.length;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1103 if (x[i])
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1104 return 0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1105 return 1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1106 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1107
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1108 //convert a bigInt into a string in a given base, from base 2 up to base 95.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1109 //Base -1 prints the contents of the array representing the number.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1110 function bigInt2str(x,base) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1111 var i,t,s="";
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1112
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1113 if (s6.length!=x.length)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1114 s6=dup(x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1115 else
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1116 copy_(s6,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1117
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1118 if (base==-1) { //return the list of array contents
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1119 for (i=x.length-1;i>0;i--)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1120 s+=x[i]+',';
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1121 s+=x[0];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1122 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1123 else { //return it in the given base
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1124 while (!isZero(s6)) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1125 t=divInt_(s6,base); //t=s6 % base; s6=floor(s6/base);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1126 s=digitsStr.substring(t,t+1)+s;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1127 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1128 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1129 if (s.length==0)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1130 s="0";
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1131 return s;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1132 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1133
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1134 //returns a duplicate of bigInt x
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1135 function dup(x) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1136 var i, buff;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1137 buff=new Array(x.length);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1138 copy_(buff,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1139 return buff;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1140 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1141
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1142 //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).
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1143 function copy_(x,y) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1144 var i;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1145 var k=x.length<y.length ? x.length : y.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1146 for (i=0;i<k;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1147 x[i]=y[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1148 for (i=k;i<x.length;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1149 x[i]=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1150 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1151
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1152 //do x=y on bigInt x and integer y.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1153 function copyInt_(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1154 var i,c;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1155 for (c=n,i=0;i<x.length;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1156 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1157 c>>=bpe;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1158 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1159 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1160
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1161 //do x=x+n where x is a bigInt and n is an integer.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1162 //x must be large enough to hold the result.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1163 function addInt_(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1164 var i,k,c,b;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1165 x[0]+=n;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1166 k=x.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1167 c=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1168 for (i=0;i<k;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1169 c+=x[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1170 b=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1171 if (c<0) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1172 b = c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1173 b = -((c - b) / radix);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1174 c+=b*radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1175 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1176 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1177 c = ((c - x[i]) / radix) - b;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1178 if (!c) return; //stop carrying as soon as the carry is zero
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1179 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1180 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1181
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1182 //right shift bigInt x by n bits.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1183 function rightShift_(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1184 var i;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1185 var k=Math.floor(n/bpe);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1186 if (k) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1187 for (i=0;i<x.length-k;i++) //right shift x by k elements
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1188 x[i]=x[i+k];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1189 for (;i<x.length;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1190 x[i]=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1191 n%=bpe;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1192 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1193 for (i=0;i<x.length-1;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1194 x[i]=mask & ((x[i+1]<<(bpe-n)) \| (x[i]>>n));
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1195 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1196 x[i]>>=n;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1197 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1198
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1199 //do x=floor(\|x\|/2)*sgn(x) for bigInt x in 2's complement
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1200 function halve_(x) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1201 var i;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1202 for (i=0;i<x.length-1;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1203 x[i]=mask & ((x[i+1]<<(bpe-1)) \| (x[i]>>1));
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1204 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1205 x[i]=(x[i]>>1) \| (x[i] & (radix>>1)); //most significant bit stays the same
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1206 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1207
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1208 //left shift bigInt x by n bits.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1209 function leftShift_(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1210 var i;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1211 var k=Math.floor(n/bpe);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1212 if (k) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1213 for (i=x.length; i>=k; i--) //left shift x by k elements
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1214 x[i]=x[i-k];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1215 for (;i>=0;i--)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1216 x[i]=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1217 n%=bpe;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1218 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1219 if (!n)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1220 return;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1221 for (i=x.length-1;i>0;i--) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1222 x[i]=mask & ((x[i]<<n) \| (x[i-1]>>(bpe-n)));
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1223 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1224 x[i]=mask & (x[i]<<n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1225 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1226
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1227 //do x=x*n where x is a bigInt and n is an integer.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1228 //x must be large enough to hold the result.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1229 function multInt_(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1230 var i,k,c,b;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1231 if (!n)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1232 return;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1233 k=x.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1234 c=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1235 for (i=0;i<k;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1236 c+=x[i]*n;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1237 b=0;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1238 if (c<0) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1239 b = c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1240 b = -((c - b) / radix);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1241 c+=b*radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1242 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1243 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1244 c = ((c - x[i]) / radix) - b;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1245 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1246 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1247
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1248 //do x=floor(x/n) for bigInt x and integer n, and return the remainder
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1249 function divInt_(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1250 var i,r=0,s;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1251 for (i=x.length-1;i>=0;i--) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1252 s=r*radix+x[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1253 x[i]=Math.floor(s/n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1254 r=s%n;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1255 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1256 return r;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1257 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1258
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1259 //do the linear combination x=ax+by for bigInts x and y, and integers a and b.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1260 //x must be large enough to hold the answer.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1261 function linComb_(x,y,a,b) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1262 var i,c,k,kk;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1263 k=x.length<y.length ? x.length : y.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1264 kk=x.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1265 for (c=0,i=0;i<k;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1266 c+=ax[i]+by[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1267 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1268 c = (c - x[i]) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1269 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1270 for (i=k;i<kk;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1271 c+=a*x[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1272 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1273 c = (c - x[i]) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1274 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1275 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1276
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1277 //do the linear combination x=ax+b(y<<(ys*bpe)) for bigInts x and y, and integers a, b and ys.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1278 //x must be large enough to hold the answer.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1279 function linCombShift_(x,y,b,ys) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1280 var i,c,k,kk;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1281 k=x.length<ys+y.length ? x.length : ys+y.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1282 kk=x.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1283 for (c=0,i=ys;i<k;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1284 c+=x[i]+b*y[i-ys];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1285 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1286 c = (c - x[i]) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1287 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1288 for (i=k;c && i<kk;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1289 c+=x[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1290 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1291 c = (c - x[i]) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1292 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1293 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1294
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1295 //do x=x+(y<<(ys*bpe)) for bigInts x and y, and integers a,b and ys.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1296 //x must be large enough to hold the answer.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1297 function addShift_(x,y,ys) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1298 var i,c,k,kk;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1299 k=x.length<ys+y.length ? x.length : ys+y.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1300 kk=x.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1301 for (c=0,i=ys;i<k;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1302 c+=x[i]+y[i-ys];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1303 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1304 c = (c - x[i]) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1305 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1306 for (i=k;c && i<kk;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1307 c+=x[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1308 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1309 c = (c - x[i]) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1310 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1311 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1312
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1313 //do x=x-(y<<(ys*bpe)) for bigInts x and y, and integers a,b and ys.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1314 //x must be large enough to hold the answer.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1315 function subShift_(x,y,ys) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1316 var i,c,k,kk;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1317 k=x.length<ys+y.length ? x.length : ys+y.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1318 kk=x.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1319 for (c=0,i=ys;i<k;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1320 c+=x[i]-y[i-ys];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1321 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1322 c = (c - x[i]) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1323 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1324 for (i=k;c && i<kk;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1325 c+=x[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1326 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1327 c = (c - x[i]) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1328 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1329 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1330
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1331 //do x=x-y for bigInts x and y.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1332 //x must be large enough to hold the answer.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1333 //negative answers will be 2s complement
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1334 function sub_(x,y) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1335 var i,c,k,kk;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1336 k=x.length<y.length ? x.length : y.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1337 for (c=0,i=0;i<k;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1338 c+=x[i]-y[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1339 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1340 c = (c - x[i]) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1341 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1342 for (i=k;c && i<x.length;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1343 c+=x[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1344 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1345 c = (c - x[i]) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1346 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1347 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1348
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1349 //do x=x+y for bigInts x and y.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1350 //x must be large enough to hold the answer.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1351 function add_(x,y) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1352 var i,c,k,kk;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1353 k=x.length<y.length ? x.length : y.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1354 for (c=0,i=0;i<k;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1355 c+=x[i]+y[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1356 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1357 c = (c - x[i]) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1358 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1359 for (i=k;c && i<x.length;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1360 c+=x[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1361 x[i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1362 c = (c - x[i]) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1363 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1364 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1365
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1366 //do x=x*y for bigInts x and y. This is faster when y<x.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1367 function mult_(x,y) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1368 var i;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1369 if (ss.length!=2*x.length)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1370 ss=new Array(2*x.length);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1371 copyInt_(ss,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1372 for (i=0;i<y.length;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1373 if (y[i])
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1374 linCombShift_(ss,x,y[i],i); //ss=1ss+y[i](x<<(i*bpe))
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1375 copy_(x,ss);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1376 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1377
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1378 //do x=x mod n for bigInts x and n.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1379 function mod_(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1380 if (s4.length!=x.length)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1381 s4=dup(x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1382 else
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1383 copy_(s4,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1384 if (s5.length!=x.length)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1385 s5=dup(x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1386 divide_(s4,n,s5,x); //x = remainder of s4 / n
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1387 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1388
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1389 //do x=x*y mod n for bigInts x,y,n.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1390 //for greater speed, let y<x.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1391 function multMod_(x,y,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1392 var i;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1393 if (s0.length!=2*x.length)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1394 s0=new Array(2*x.length);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1395 copyInt_(s0,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1396 for (i=0;i<y.length;i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1397 if (y[i])
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1398 linCombShift_(s0,x,y[i],i); //s0=1s0+y[i](x<<(i*bpe))
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1399 mod_(s0,n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1400 copy_(x,s0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1401 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1402
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1403 //do x=x*x mod n for bigInts x,n.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1404 function squareMod_(x,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1405 var i,j,d,c,kx,kn,k;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1406 for (kx=x.length; kx>0 && !x[kx-1]; kx--); //ignore leading zeros in x
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1407 k=kx>n.length ? 2kx : 2n.length; //k=# elements in the product, which is twice the elements in the larger of x and n
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1408 if (s0.length!=k)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1409 s0=new Array(k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1410 copyInt_(s0,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1411 for (i=0;i<kx;i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1412 c=s0[2i]+x[i]x[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1413 s0[2*i]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1414 c = (c - s0[2*i]) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1415 for (j=i+1;j<kx;j++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1416 c=s0[i+j]+2x[i]x[j]+c;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1417 s0[i+j]=(c & mask);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1418 c = (c - s0[i+j]) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1419 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1420 s0[i+kx]=c;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1421 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1422 mod_(s0,n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1423 copy_(x,s0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1424 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1425
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1426 //return x with exactly k leading zero elements
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1427 function trim(x,k) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1428 var i,y;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1429 for (i=x.length; i>0 && !x[i-1]; i--);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1430 y=new Array(i+k);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1431 copy_(y,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1432 return y;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1433 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1434
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1435 //do x=xy mod n, where x,y,n are bigInts and is exponentiation. 0**0=1.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1436 //this is faster when n is odd. x usually needs to have as many elements as n.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1437 function powMod_(x,y,n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1438 var k1,k2,kn,np;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1439 if(s7.length!=n.length)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1440 s7=dup(n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1441
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1442 //for even modulus, use a simple square-and-multiply algorithm,
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1443 //rather than using the more complex Montgomery algorithm.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1444 if ((n[0]&1)==0) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1445 copy_(s7,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1446 copyInt_(x,1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1447 while(!equalsInt(y,0)) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1448 if (y[0]&1)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1449 multMod_(x,s7,n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1450 divInt_(y,2);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1451 squareMod_(s7,n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1452 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1453 return;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1454 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1455
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1456 //calculate np from n for the Montgomery multiplications
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1457 copyInt_(s7,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1458 for (kn=n.length;kn>0 && !n[kn-1];kn--);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1459 np=radix-inverseModInt(modInt(n,radix),radix);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1460 s7[kn]=1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1461 multMod_(x ,s7,n); // x = x * 2*(knbp) mod n
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1462
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1463 if (s3.length!=x.length)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1464 s3=dup(x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1465 else
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1466 copy_(s3,x);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1467
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1468 for (k1=y.length-1;k1>0 & !y[k1]; k1--); //k1=first nonzero element of y
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1469 if (y[k1]==0) { //anything to the 0th power is 1
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1470 copyInt_(x,1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1471 return;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1472 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1473 for (k2=1<<(bpe-1);k2 && !(y[k1] & k2); k2>>=1); //k2=position of first 1 bit in y[k1]
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1474 for (;;) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1475 if (!(k2>>=1)) { //look at next bit of y
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1476 k1--;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1477 if (k1<0) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1478 mont_(x,one,n,np);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1479 return;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1480 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1481 k2=1<<(bpe-1);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1482 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1483 mont_(x,x,n,np);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1484
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1485 if (k2 & y[k1]) //if next bit is a 1
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1486 mont_(x,s3,n,np);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1487 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1488 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1489
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1490
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1491 //do x=xyRi mod n for bigInts x,y,n,
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1492 // where Ri = 2*(-knbpe) mod n, and kn is the
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1493 // number of elements in the n array, not
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1494 // counting leading zeros.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1495 //x array must have at least as many elemnts as the n array
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1496 //It's OK if x and y are the same variable.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1497 //must have:
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1498 // x,y < n
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1499 // n is odd
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1500 // np = -(n^(-1)) mod radix
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1501 function mont_(x,y,n,np) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1502 var i,j,c,ui,t,t2,ks;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1503 var kn=n.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1504 var ky=y.length;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1505
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1506 if (sa.length!=kn)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1507 sa=new Array(kn);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1508
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1509 copyInt_(sa,0);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1510
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1511 for (;kn>0 && n[kn-1]==0;kn--); //ignore leading zeros of n
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1512 for (;ky>0 && y[ky-1]==0;ky--); //ignore leading zeros of y
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1513 ks=sa.length-1; //sa will never have more than this many nonzero elements.
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1514
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1515 //the following loop consumes 95% of the runtime for randTruePrime_() and powMod_() for large numbers
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1516 for (i=0; i<kn; i++) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1517 t=sa[0]+x[i]*y[0];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1518 ui=((t & mask) * np) & mask; //the inner "& mask" was needed on Safari (but not MSIE) at one time
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1519 c=(t+ui*n[0]);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1520 c = (c - (c & mask)) / radix;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1521 t=x[i];
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1522
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1523 //do sa=(sa+x[i]y+uin)/b where b=2**bpe. Loop is unrolled 5-fold for speed
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1524 j=1;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1525 for (;j<ky-4;) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1526 c+=sa[j]+uin[j]+ty[j]; t2=sa[j-1]=c & mask; c=(c-t2)/radix; j++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1527 c+=sa[j]+uin[j]+ty[j]; t2=sa[j-1]=c & mask; c=(c-t2)/radix; j++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1528 c+=sa[j]+uin[j]+ty[j]; t2=sa[j-1]=c & mask; c=(c-t2)/radix; j++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1529 c+=sa[j]+uin[j]+ty[j]; t2=sa[j-1]=c & mask; c=(c-t2)/radix; j++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1530 c+=sa[j]+uin[j]+ty[j]; t2=sa[j-1]=c & mask; c=(c-t2)/radix; j++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1531 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1532 for (;j<ky;) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1533 c+=sa[j]+uin[j]+ty[j]; t2=sa[j-1]=c & mask; c=(c-t2)/radix; j++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1534 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1535 for (;j<kn-4;) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1536 c+=sa[j]+ui*n[j]; t2=sa[j-1]=c & mask; c=(c-t2)/radix; j++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1537 c+=sa[j]+ui*n[j]; t2=sa[j-1]=c & mask; c=(c-t2)/radix; j++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1538 c+=sa[j]+ui*n[j]; t2=sa[j-1]=c & mask; c=(c-t2)/radix; j++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1539 c+=sa[j]+ui*n[j]; t2=sa[j-1]=c & mask; c=(c-t2)/radix; j++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1540 c+=sa[j]+ui*n[j]; t2=sa[j-1]=c & mask; c=(c-t2)/radix; j++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1541 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1542 for (;j<kn;) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1543 c+=sa[j]+ui*n[j]; t2=sa[j-1]=c & mask; c=(c-t2)/radix; j++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1544 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1545 for (;j<ks;) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1546 c+=sa[j]; t2=sa[j-1]=c & mask; c=(c-t2)/radix; j++;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1547 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1548 sa[j-1]=c & mask;
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1549 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1550
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1551 if (!greater(n,sa))
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1552 sub_(sa,n);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1553 copy_(x,sa);
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1554 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1555
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1556
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1557 // otr.js additions
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1558
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1559
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1560 // computes num / den mod n
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1561 function divMod(num, den, n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1562 return multMod(num, inverseMod(den, n), n)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1563 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1564
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1565 // computes one - two mod n
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1566 function subMod(one, two, n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1567 one = mod(one, n)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1568 two = mod(two, n)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1569 if (greater(two, one)) one = add(one, n)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1570 return sub(one, two)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1571 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1572
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1573 // computes 2^m as a bigInt
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1574 function twoToThe(m) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1575 var b = Math.floor(m / bpe) + 2
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1576 var t = new Array(b)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1577 for (var i = 0; i < b; i++) t[i] = 0
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1578 t[b - 2] = 1 << (m % bpe)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1579 return t
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1580 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1581
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1582 // cache these results for faster lookup
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1583 var _num2bin = (function () {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1584 var i = 0, _num2bin= {}
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1585 for (; i < 0x100; ++i) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1586 _num2bin[i] = String.fromCharCode(i) // 0 -> "\00"
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1587 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1588 return _num2bin
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1589 }())
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1590
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1591 // serialize a bigInt to an ascii string
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1592 // padded up to pad length
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1593 function bigInt2bits(bi, pad) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1594 pad \|\| (pad = 0)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1595 bi = dup(bi)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1596 var ba = ''
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1597 while (!isZero(bi)) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1598 ba = _num2bin[bi[0] & 0xff] + ba
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1599 rightShift_(bi, 8)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1600 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1601 while (ba.length < pad) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1602 ba = '\x00' + ba
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1603 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1604 return ba
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1605 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1606
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1607 // converts a byte array to a bigInt
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1608 function ba2bigInt(data) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1609 var mpi = str2bigInt('0', 10, data.length)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1610 data.forEach(function (d, i) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1611 if (i) leftShift_(mpi, 8)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1612 mpi[0] \|= d
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1613 })
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1614 return mpi
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1615 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1616
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1617 // returns a function that returns an array of n bytes
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1618 var randomBytes = (function () {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1619
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1620 // in node
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1621 if ( typeof crypto !== 'undefined' &&
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1622 typeof crypto.randomBytes === 'function' ) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1623 return function (n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1624 try {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1625 var buf = crypto.randomBytes(n)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1626 } catch (e) { throw e }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1627 return Array.prototype.slice.call(buf, 0)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1628 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1629 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1630
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1631 // in browser
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1632 else if ( typeof crypto !== 'undefined' &&
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1633 typeof crypto.getRandomValues === 'function' ) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1634 return function (n) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1635 var buf = new Uint8Array(n)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1636 crypto.getRandomValues(buf)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1637 return Array.prototype.slice.call(buf, 0)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1638 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1639 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1640
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1641 // err
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1642 else {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1643 throw new Error('Keys should not be generated without CSPRNG.')
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1644 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1645
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1646 }())
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1647
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1648 // Salsa 20 in webworker needs a 40 byte seed
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1649 function getSeed() {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1650 return randomBytes(40)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1651 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1652
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1653 // returns a single random byte
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1654 function randomByte() {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1655 return randomBytes(1)[0]
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1656 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1657
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1658 // returns a k-bit random integer
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1659 function randomBitInt(k) {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1660 if (k > 31) throw new Error("Too many bits.")
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1661 var i = 0, r = 0
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1662 var b = Math.floor(k / 8)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1663 var mask = (1 << (k % 8)) - 1
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1664 if (mask) r = randomByte() & mask
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1665 for (; i < b; i++)
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1666 r = (256 * r) + randomByte()
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1667 return r
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1668 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1669
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1670 return {
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1671 str2bigInt : str2bigInt
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1672 , bigInt2str : bigInt2str
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1673 , int2bigInt : int2bigInt
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1674 , multMod : multMod
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1675 , powMod : powMod
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1676 , inverseMod : inverseMod
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1677 , randBigInt : randBigInt
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1678 , randBigInt_ : randBigInt_
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1679 , equals : equals
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1680 , equalsInt : equalsInt
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1681 , sub : sub
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1682 , mod : mod
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1683 , modInt : modInt
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1684 , mult : mult
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1685 , divInt_ : divInt_
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1686 , rightShift_ : rightShift_
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1687 , dup : dup
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1688 , greater : greater
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1689 , add : add
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1690 , isZero : isZero
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1691 , bitSize : bitSize
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1692 , millerRabin : millerRabin
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1693 , divide_ : divide_
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1694 , trim : trim
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1695 , primes : primes
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1696 , findPrimes : findPrimes
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1697 , getSeed : getSeed
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1698 , divMod : divMod
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1699 , subMod : subMod
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1700 , twoToThe : twoToThe
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1701 , bigInt2bits : bigInt2bits
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1702 , ba2bigInt : ba2bigInt
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1703 }
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1704
1596660ddf72 Add minifier script for otr.js and its dependencies souliane <souliane@mailoo.org> parents: diff changeset	1705 }))