1563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark/* 2563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Copyright (c) 2003-2005 Tom Wu 3563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * All Rights Reserved. 4563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * 5563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * Permission is hereby granted, free of charge, to any person obtaining 6563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * a copy of this software and associated documentation files (the 7563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * "Software"), to deal in the Software without restriction, including 8563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * without limitation the rights to use, copy, modify, merge, publish, 9563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * distribute, sublicense, and/or sell copies of the Software, and to 10563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * permit persons to whom the Software is furnished to do so, subject to 11563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * the following conditions: 12563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * 13563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * The above copyright notice and this permission notice shall be 14563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * included in all copies or substantial portions of the Software. 15563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * 16563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 17563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 18563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 19563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * 20563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * IN NO EVENT SHALL TOM WU BE LIABLE FOR ANY SPECIAL, INCIDENTAL, 21563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, OR ANY DAMAGES WHATSOEVER 22563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER OR NOT ADVISED OF 23563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF LIABILITY, ARISING OUT 24563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 25563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * 26563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * In addition, the following condition applies: 27563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * 28563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * All redistributions must retain an intact copy of this copyright notice 29563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark * and disclaimer. 30563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark */ 31563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 32563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Basic JavaScript BN library - subset useful for RSA encryption. 33563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 34563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Bits per digit 35563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar dbits; 36563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar BI_DB; 37563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar BI_DM; 38563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar BI_DV; 39563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 40563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar BI_FP; 41563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar BI_FV; 42563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar BI_F1; 43563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar BI_F2; 44563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 45563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// JavaScript engine analysis 46563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar canary = 0xdeadbeefcafe; 47563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar j_lm = ((canary&0xffffff)==0xefcafe); 48563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 49563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) Constructor 50563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction BigInteger(a,b,c) { 51563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.array = new Array(); 52563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(a != null) 53563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if("number" == typeof a) this.fromNumber(a,b,c); 54563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(b == null && "string" != typeof a) this.fromString(a,256); 55563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else this.fromString(a,b); 56563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 57563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 58563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// return new, unset BigInteger 59563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction nbi() { return new BigInteger(null); } 60563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 61563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// am: Compute w_j += (x*this_i), propagate carries, 62563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// c is initial carry, returns final carry. 63563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// c < 3*dvalue, x < 2*dvalue, this_i < dvalue 64563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// We need to select the fastest one that works in this environment. 65563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 66563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// am1: use a single mult and divide to get the high bits, 67563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// max digit bits should be 26 because 68563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// max internal value = 2*dvalue^2-2*dvalue (< 2^53) 69563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction am1(i,x,w,j,c,n) { 70563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 71563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var w_array = w.array; 72563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(--n >= 0) { 73563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var v = x*this_array[i++]+w_array[j]+c; 74563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c = Math.floor(v/0x4000000); 75563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark w_array[j++] = v&0x3ffffff; 76563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 77563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return c; 78563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 79563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 80563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// am2 avoids a big mult-and-extract completely. 81563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Max digit bits should be <= 30 because we do bitwise ops 82563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// on values up to 2*hdvalue^2-hdvalue-1 (< 2^31) 83563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction am2(i,x,w,j,c,n) { 84563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 85563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var w_array = w.array; 86563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var xl = x&0x7fff, xh = x>>15; 87563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(--n >= 0) { 88563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var l = this_array[i]&0x7fff; 89563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var h = this_array[i++]>>15; 90563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var m = xh*l+h*xl; 91563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark l = xl*l+((m&0x7fff)<<15)+w_array[j]+(c&0x3fffffff); 92563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c = (l>>>30)+(m>>>15)+xh*h+(c>>>30); 93563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark w_array[j++] = l&0x3fffffff; 94563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 95563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return c; 96563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 97563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 98563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Alternately, set max digit bits to 28 since some 99563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// browsers slow down when dealing with 32-bit numbers. 100563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction am3(i,x,w,j,c,n) { 101563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 102563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var w_array = w.array; 103563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 104563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var xl = x&0x3fff, xh = x>>14; 105563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(--n >= 0) { 106563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var l = this_array[i]&0x3fff; 107563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var h = this_array[i++]>>14; 108563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var m = xh*l+h*xl; 109563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark l = xl*l+((m&0x3fff)<<14)+w_array[j]+c; 110563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c = (l>>28)+(m>>14)+xh*h; 111563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark w_array[j++] = l&0xfffffff; 112563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 113563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return c; 114563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 115563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 116563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// This is tailored to VMs with 2-bit tagging. It makes sure 117563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// that all the computations stay within the 29 bits available. 118563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction am4(i,x,w,j,c,n) { 119563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 120563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var w_array = w.array; 121563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 122563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var xl = x&0x1fff, xh = x>>13; 123563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(--n >= 0) { 124563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var l = this_array[i]&0x1fff; 125563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var h = this_array[i++]>>13; 126563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var m = xh*l+h*xl; 127563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark l = xl*l+((m&0x1fff)<<13)+w_array[j]+c; 128563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c = (l>>26)+(m>>13)+xh*h; 129563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark w_array[j++] = l&0x3ffffff; 130563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 131563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return c; 132563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 133563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 134563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// am3/28 is best for SM, Rhino, but am4/26 is best for v8. 135563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Kestrel (Opera 9.5) gets its best result with am4/26. 136563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// IE7 does 9% better with am3/28 than with am4/26. 137563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Firefox (SM) gets 10% faster with am3/28 than with am4/26. 138563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 139563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarksetupEngine = function(fn, bits) { 140563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark BigInteger.prototype.am = fn; 141563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark dbits = bits; 142563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 143563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark BI_DB = dbits; 144563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark BI_DM = ((1<<dbits)-1); 145563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark BI_DV = (1<<dbits); 146563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 147563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark BI_FP = 52; 148563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark BI_FV = Math.pow(2,BI_FP); 149563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark BI_F1 = BI_FP-dbits; 150563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark BI_F2 = 2*dbits-BI_FP; 151563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 152563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 153563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 154563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Digit conversions 155563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar BI_RM = "0123456789abcdefghijklmnopqrstuvwxyz"; 156563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar BI_RC = new Array(); 157563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar rr,vv; 158563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkrr = "0".charCodeAt(0); 159563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfor(vv = 0; vv <= 9; ++vv) BI_RC[rr++] = vv; 160563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkrr = "a".charCodeAt(0); 161563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfor(vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv; 162563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkrr = "A".charCodeAt(0); 163563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfor(vv = 10; vv < 36; ++vv) BI_RC[rr++] = vv; 164563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 165563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction int2char(n) { return BI_RM.charAt(n); } 166563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction intAt(s,i) { 167563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var c = BI_RC[s.charCodeAt(i)]; 168563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return (c==null)?-1:c; 169563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 170563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 171563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) copy this to r 172563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpCopyTo(r) { 173563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 174563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r_array = r.array; 175563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 176563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(var i = this.t-1; i >= 0; --i) r_array[i] = this_array[i]; 177563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.t = this.t; 178563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.s = this.s; 179563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 180563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 181563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) set from integer value x, -DV <= x < DV 182563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpFromInt(x) { 183563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 184563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.t = 1; 185563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.s = (x<0)?-1:0; 186563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(x > 0) this_array[0] = x; 187563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(x < -1) this_array[0] = x+DV; 188563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else this.t = 0; 189563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 190563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 191563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// return bigint initialized to value 192563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction nbv(i) { var r = nbi(); r.fromInt(i); return r; } 193563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 194563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) set from string and radix 195563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpFromString(s,b) { 196563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 197563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var k; 198563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(b == 16) k = 4; 199563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(b == 8) k = 3; 200563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(b == 256) k = 8; // byte array 201563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(b == 2) k = 1; 202563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(b == 32) k = 5; 203563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(b == 4) k = 2; 204563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else { this.fromRadix(s,b); return; } 205563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.t = 0; 206563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.s = 0; 207563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = s.length, mi = false, sh = 0; 208563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(--i >= 0) { 209563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var x = (k==8)?s[i]&0xff:intAt(s,i); 210563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(x < 0) { 211563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(s.charAt(i) == "-") mi = true; 212563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark continue; 213563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 214563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark mi = false; 215563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(sh == 0) 216563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this_array[this.t++] = x; 217563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(sh+k > BI_DB) { 218563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this_array[this.t-1] |= (x&((1<<(BI_DB-sh))-1))<<sh; 219563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this_array[this.t++] = (x>>(BI_DB-sh)); 220563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 221563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else 222563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this_array[this.t-1] |= x<<sh; 223563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark sh += k; 224563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(sh >= BI_DB) sh -= BI_DB; 225563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 226563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(k == 8 && (s[0]&0x80) != 0) { 227563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.s = -1; 228563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(sh > 0) this_array[this.t-1] |= ((1<<(BI_DB-sh))-1)<<sh; 229563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 230563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.clamp(); 231563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(mi) BigInteger.ZERO.subTo(this,this); 232563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 233563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 234563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) clamp off excess high words 235563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpClamp() { 236563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 237563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var c = this.s&BI_DM; 238563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(this.t > 0 && this_array[this.t-1] == c) --this.t; 239563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 240563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 241563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) return string representation in given radix 242563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnToString(b) { 243563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 244563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.s < 0) return "-"+this.negate().toString(b); 245563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var k; 246563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(b == 16) k = 4; 247563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(b == 8) k = 3; 248563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(b == 2) k = 1; 249563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(b == 32) k = 5; 250563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(b == 4) k = 2; 251563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else return this.toRadix(b); 252563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var km = (1<<k)-1, d, m = false, r = "", i = this.t; 253563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var p = BI_DB-(i*BI_DB)%k; 254563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(i-- > 0) { 255563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(p < BI_DB && (d = this_array[i]>>p) > 0) { m = true; r = int2char(d); } 256563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(i >= 0) { 257563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(p < k) { 258563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark d = (this_array[i]&((1<<p)-1))<<(k-p); 259563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark d |= this_array[--i]>>(p+=BI_DB-k); 260563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 261563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else { 262563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark d = (this_array[i]>>(p-=k))&km; 263563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(p <= 0) { p += BI_DB; --i; } 264563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 265563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(d > 0) m = true; 266563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(m) r += int2char(d); 267563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 268563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 269563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return m?r:"0"; 270563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 271563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 272563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) -this 273563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnNegate() { var r = nbi(); BigInteger.ZERO.subTo(this,r); return r; } 274563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 275563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) |this| 276563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnAbs() { return (this.s<0)?this.negate():this; } 277563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 278563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) return + if this > a, - if this < a, 0 if equal 279563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnCompareTo(a) { 280563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 281563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var a_array = a.array; 282563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 283563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r = this.s-a.s; 284563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(r != 0) return r; 285563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = this.t; 286563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r = i-a.t; 287563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(r != 0) return r; 288563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(--i >= 0) if((r=this_array[i]-a_array[i]) != 0) return r; 289563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return 0; 290563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 291563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 292563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// returns bit length of the integer x 293563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction nbits(x) { 294563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r = 1, t; 295563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((t=x>>>16) != 0) { x = t; r += 16; } 296563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((t=x>>8) != 0) { x = t; r += 8; } 297563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((t=x>>4) != 0) { x = t; r += 4; } 298563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((t=x>>2) != 0) { x = t; r += 2; } 299563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((t=x>>1) != 0) { x = t; r += 1; } 300563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return r; 301563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 302563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 303563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) return the number of bits in "this" 304563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnBitLength() { 305563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 306563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.t <= 0) return 0; 307563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return BI_DB*(this.t-1)+nbits(this_array[this.t-1]^(this.s&BI_DM)); 308563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 309563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 310563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) r = this << n*DB 311563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpDLShiftTo(n,r) { 312563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 313563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r_array = r.array; 314563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i; 315563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(i = this.t-1; i >= 0; --i) r_array[i+n] = this_array[i]; 316563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(i = n-1; i >= 0; --i) r_array[i] = 0; 317563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.t = this.t+n; 318563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.s = this.s; 319563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 320563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 321563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) r = this >> n*DB 322563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpDRShiftTo(n,r) { 323563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 324563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r_array = r.array; 325563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(var i = n; i < this.t; ++i) r_array[i-n] = this_array[i]; 326563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.t = Math.max(this.t-n,0); 327563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.s = this.s; 328563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 329563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 330563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) r = this << n 331563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpLShiftTo(n,r) { 332563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 333563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r_array = r.array; 334563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var bs = n%BI_DB; 335563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var cbs = BI_DB-bs; 336563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var bm = (1<<cbs)-1; 337563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var ds = Math.floor(n/BI_DB), c = (this.s<<bs)&BI_DM, i; 338563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(i = this.t-1; i >= 0; --i) { 339563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r_array[i+ds+1] = (this_array[i]>>cbs)|c; 340563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c = (this_array[i]&bm)<<bs; 341563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 342563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(i = ds-1; i >= 0; --i) r_array[i] = 0; 343563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r_array[ds] = c; 344563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.t = this.t+ds+1; 345563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.s = this.s; 346563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.clamp(); 347563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 348563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 349563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) r = this >> n 350563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpRShiftTo(n,r) { 351563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 352563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r_array = r.array; 353563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.s = this.s; 354563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var ds = Math.floor(n/BI_DB); 355563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(ds >= this.t) { r.t = 0; return; } 356563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var bs = n%BI_DB; 357563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var cbs = BI_DB-bs; 358563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var bm = (1<<bs)-1; 359563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r_array[0] = this_array[ds]>>bs; 360563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(var i = ds+1; i < this.t; ++i) { 361563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r_array[i-ds-1] |= (this_array[i]&bm)<<cbs; 362563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r_array[i-ds] = this_array[i]>>bs; 363563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 364563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(bs > 0) r_array[this.t-ds-1] |= (this.s&bm)<<cbs; 365563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.t = this.t-ds; 366563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.clamp(); 367563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 368563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 369563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) r = this - a 370563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpSubTo(a,r) { 371563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 372563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r_array = r.array; 373563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var a_array = a.array; 374563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = 0, c = 0, m = Math.min(a.t,this.t); 375563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(i < m) { 376563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c += this_array[i]-a_array[i]; 377563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r_array[i++] = c&BI_DM; 378563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c >>= BI_DB; 379563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 380563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(a.t < this.t) { 381563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c -= a.s; 382563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(i < this.t) { 383563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c += this_array[i]; 384563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r_array[i++] = c&BI_DM; 385563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c >>= BI_DB; 386563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 387563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c += this.s; 388563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 389563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else { 390563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c += this.s; 391563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(i < a.t) { 392563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c -= a_array[i]; 393563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r_array[i++] = c&BI_DM; 394563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c >>= BI_DB; 395563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 396563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c -= a.s; 397563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 398563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.s = (c<0)?-1:0; 399563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(c < -1) r_array[i++] = BI_DV+c; 400563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(c > 0) r_array[i++] = c; 401563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.t = i; 402563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.clamp(); 403563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 404563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 405563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) r = this * a, r != this,a (HAC 14.12) 406563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// "this" should be the larger one if appropriate. 407563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpMultiplyTo(a,r) { 408563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 409563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r_array = r.array; 410563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var x = this.abs(), y = a.abs(); 411563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var y_array = y.array; 412563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 413563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = x.t; 414563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.t = i+y.t; 415563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(--i >= 0) r_array[i] = 0; 416563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(i = 0; i < y.t; ++i) r_array[i+x.t] = x.am(0,y_array[i],r,i,0,x.t); 417563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.s = 0; 418563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.clamp(); 419563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.s != a.s) BigInteger.ZERO.subTo(r,r); 420563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 421563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 422563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) r = this^2, r != this (HAC 14.16) 423563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpSquareTo(r) { 424563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var x = this.abs(); 425563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var x_array = x.array; 426563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r_array = r.array; 427563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 428563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = r.t = 2*x.t; 429563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(--i >= 0) r_array[i] = 0; 430563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(i = 0; i < x.t-1; ++i) { 431563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var c = x.am(i,x_array[i],r,2*i,0,1); 432563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((r_array[i+x.t]+=x.am(i+1,2*x_array[i],r,2*i+1,c,x.t-i-1)) >= BI_DV) { 433563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r_array[i+x.t] -= BI_DV; 434563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r_array[i+x.t+1] = 1; 435563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 436563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 437563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(r.t > 0) r_array[r.t-1] += x.am(i,x_array[i],r,2*i,0,1); 438563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.s = 0; 439563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.clamp(); 440563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 441563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 442563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) divide this by m, quotient and remainder to q, r (HAC 14.20) 443563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// r != q, this != m. q or r may be null. 444563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpDivRemTo(m,q,r) { 445563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var pm = m.abs(); 446563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(pm.t <= 0) return; 447563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var pt = this.abs(); 448563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(pt.t < pm.t) { 449563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(q != null) q.fromInt(0); 450563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(r != null) this.copyTo(r); 451563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return; 452563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 453563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(r == null) r = nbi(); 454563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var y = nbi(), ts = this.s, ms = m.s; 455563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var pm_array = pm.array; 456563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var nsh = BI_DB-nbits(pm_array[pm.t-1]); // normalize modulus 457563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(nsh > 0) { pm.lShiftTo(nsh,y); pt.lShiftTo(nsh,r); } 458563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else { pm.copyTo(y); pt.copyTo(r); } 459563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var ys = y.t; 460563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 461563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var y_array = y.array; 462563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var y0 = y_array[ys-1]; 463563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(y0 == 0) return; 464563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var yt = y0*(1<<BI_F1)+((ys>1)?y_array[ys-2]>>BI_F2:0); 465563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var d1 = BI_FV/yt, d2 = (1<<BI_F1)/yt, e = 1<<BI_F2; 466563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = r.t, j = i-ys, t = (q==null)?nbi():q; 467563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark y.dlShiftTo(j,t); 468563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 469563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r_array = r.array; 470563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(r.compareTo(t) >= 0) { 471563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r_array[r.t++] = 1; 472563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.subTo(t,r); 473563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 474563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark BigInteger.ONE.dlShiftTo(ys,t); 475563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark t.subTo(y,y); // "negative" y so we can replace sub with am later 476563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(y.t < ys) y_array[y.t++] = 0; 477563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(--j >= 0) { 478563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // Estimate quotient digit 479563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var qd = (r_array[--i]==y0)?BI_DM:Math.floor(r_array[i]*d1+(r_array[i-1]+e)*d2); 480563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((r_array[i]+=y.am(0,qd,r,j,0,ys)) < qd) { // Try it out 481563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark y.dlShiftTo(j,t); 482563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.subTo(t,r); 483563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(r_array[i] < --qd) r.subTo(t,r); 484563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 485563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 486563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(q != null) { 487563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.drShiftTo(ys,q); 488563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(ts != ms) BigInteger.ZERO.subTo(q,q); 489563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 490563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.t = ys; 491563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.clamp(); 492563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(nsh > 0) r.rShiftTo(nsh,r); // Denormalize remainder 493563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(ts < 0) BigInteger.ZERO.subTo(r,r); 494563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 495563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 496563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this mod a 497563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnMod(a) { 498563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r = nbi(); 499563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.abs().divRemTo(a,null,r); 500563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.s < 0 && r.compareTo(BigInteger.ZERO) > 0) a.subTo(r,r); 501563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return r; 502563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 503563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 504563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Modular reduction using "classic" algorithm 505563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction Classic(m) { this.m = m; } 506563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction cConvert(x) { 507563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(x.s < 0 || x.compareTo(this.m) >= 0) return x.mod(this.m); 508563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else return x; 509563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 510563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction cRevert(x) { return x; } 511563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction cReduce(x) { x.divRemTo(this.m,null,x); } 512563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction cMulTo(x,y,r) { x.multiplyTo(y,r); this.reduce(r); } 513563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction cSqrTo(x,r) { x.squareTo(r); this.reduce(r); } 514563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 515563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkClassic.prototype.convert = cConvert; 516563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkClassic.prototype.revert = cRevert; 517563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkClassic.prototype.reduce = cReduce; 518563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkClassic.prototype.mulTo = cMulTo; 519563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkClassic.prototype.sqrTo = cSqrTo; 520563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 521563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) return "-1/this % 2^DB"; useful for Mont. reduction 522563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// justification: 523563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// xy == 1 (mod m) 524563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// xy = 1+km 525563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// xy(2-xy) = (1+km)(1-km) 526563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// x[y(2-xy)] = 1-k^2m^2 527563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// x[y(2-xy)] == 1 (mod m^2) 528563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// if y is 1/x mod m, then y(2-xy) is 1/x mod m^2 529563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// should reduce x and y(2-xy) by m^2 at each step to keep size bounded. 530563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// JS multiply "overflows" differently from C/C++, so care is needed here. 531563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpInvDigit() { 532563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 533563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.t < 1) return 0; 534563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var x = this_array[0]; 535563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((x&1) == 0) return 0; 536563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var y = x&3; // y == 1/x mod 2^2 537563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark y = (y*(2-(x&0xf)*y))&0xf; // y == 1/x mod 2^4 538563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark y = (y*(2-(x&0xff)*y))&0xff; // y == 1/x mod 2^8 539563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark y = (y*(2-(((x&0xffff)*y)&0xffff)))&0xffff; // y == 1/x mod 2^16 540563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // last step - calculate inverse mod DV directly; 541563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // assumes 16 < DB <= 32 and assumes ability to handle 48-bit ints 542563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark y = (y*(2-x*y%BI_DV))%BI_DV; // y == 1/x mod 2^dbits 543563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // we really want the negative inverse, and -DV < y < DV 544563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return (y>0)?BI_DV-y:-y; 545563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 546563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 547563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Montgomery reduction 548563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction Montgomery(m) { 549563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.m = m; 550563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.mp = m.invDigit(); 551563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.mpl = this.mp&0x7fff; 552563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.mph = this.mp>>15; 553563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.um = (1<<(BI_DB-15))-1; 554563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.mt2 = 2*m.t; 555563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 556563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 557563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// xR mod m 558563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction montConvert(x) { 559563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r = nbi(); 560563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark x.abs().dlShiftTo(this.m.t,r); 561563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.divRemTo(this.m,null,r); 562563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(x.s < 0 && r.compareTo(BigInteger.ZERO) > 0) this.m.subTo(r,r); 563563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return r; 564563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 565563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 566563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// x/R mod m 567563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction montRevert(x) { 568563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r = nbi(); 569563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark x.copyTo(r); 570563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.reduce(r); 571563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return r; 572563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 573563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 574563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// x = x/R mod m (HAC 14.32) 575563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction montReduce(x) { 576563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var x_array = x.array; 577563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(x.t <= this.mt2) // pad x so am has enough room later 578563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark x_array[x.t++] = 0; 579563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(var i = 0; i < this.m.t; ++i) { 580563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // faster way of calculating u0 = x[i]*mp mod DV 581563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var j = x_array[i]&0x7fff; 582563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var u0 = (j*this.mpl+(((j*this.mph+(x_array[i]>>15)*this.mpl)&this.um)<<15))&BI_DM; 583563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // use am to combine the multiply-shift-add into one call 584563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark j = i+this.m.t; 585563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark x_array[j] += this.m.am(0,u0,x,i,0,this.m.t); 586563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // propagate carry 587563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(x_array[j] >= BI_DV) { x_array[j] -= BI_DV; x_array[++j]++; } 588563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 589563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark x.clamp(); 590563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark x.drShiftTo(this.m.t,x); 591563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(x.compareTo(this.m) >= 0) x.subTo(this.m,x); 592563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 593563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 594563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// r = "x^2/R mod m"; x != r 595563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction montSqrTo(x,r) { x.squareTo(r); this.reduce(r); } 596563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 597563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// r = "xy/R mod m"; x,y != r 598563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction montMulTo(x,y,r) { x.multiplyTo(y,r); this.reduce(r); } 599563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 600563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkMontgomery.prototype.convert = montConvert; 601563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkMontgomery.prototype.revert = montRevert; 602563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkMontgomery.prototype.reduce = montReduce; 603563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkMontgomery.prototype.mulTo = montMulTo; 604563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkMontgomery.prototype.sqrTo = montSqrTo; 605563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 606563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) true iff this is even 607563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpIsEven() { 608563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 609563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return ((this.t>0)?(this_array[0]&1):this.s) == 0; 610563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 611563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 612563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) this^e, e < 2^32, doing sqr and mul with "r" (HAC 14.79) 613563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpExp(e,z) { 614563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(e > 0xffffffff || e < 1) return BigInteger.ONE; 615563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r = nbi(), r2 = nbi(), g = z.convert(this), i = nbits(e)-1; 616563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark g.copyTo(r); 617563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(--i >= 0) { 618563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark z.sqrTo(r,r2); 619563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((e&(1<<i)) > 0) z.mulTo(r2,g,r); 620563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else { var t = r; r = r2; r2 = t; } 621563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 622563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return z.revert(r); 623563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 624563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 625563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this^e % m, 0 <= e < 2^32 626563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnModPowInt(e,m) { 627563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var z; 628563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(e < 256 || m.isEven()) z = new Classic(m); else z = new Montgomery(m); 629563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return this.exp(e,z); 630563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 631563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 632563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// protected 633563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.copyTo = bnpCopyTo; 634563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.fromInt = bnpFromInt; 635563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.fromString = bnpFromString; 636563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.clamp = bnpClamp; 637563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.dlShiftTo = bnpDLShiftTo; 638563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.drShiftTo = bnpDRShiftTo; 639563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.lShiftTo = bnpLShiftTo; 640563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.rShiftTo = bnpRShiftTo; 641563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.subTo = bnpSubTo; 642563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.multiplyTo = bnpMultiplyTo; 643563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.squareTo = bnpSquareTo; 644563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.divRemTo = bnpDivRemTo; 645563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.invDigit = bnpInvDigit; 646563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.isEven = bnpIsEven; 647563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.exp = bnpExp; 648563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 649563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// public 650563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.toString = bnToString; 651563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.negate = bnNegate; 652563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.abs = bnAbs; 653563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.compareTo = bnCompareTo; 654563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.bitLength = bnBitLength; 655563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.mod = bnMod; 656563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.modPowInt = bnModPowInt; 657563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 658563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// "constants" 659563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.ZERO = nbv(0); 660563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.ONE = nbv(1); 661563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Copyright (c) 2005 Tom Wu 662563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// All Rights Reserved. 663563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// See "LICENSE" for details. 664563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 665563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Extended JavaScript BN functions, required for RSA private ops. 666563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 667563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) 668563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnClone() { var r = nbi(); this.copyTo(r); return r; } 669563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 670563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) return value as integer 671563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnIntValue() { 672563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 673563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.s < 0) { 674563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.t == 1) return this_array[0]-BI_DV; 675563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(this.t == 0) return -1; 676563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 677563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(this.t == 1) return this_array[0]; 678563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(this.t == 0) return 0; 679563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // assumes 16 < DB < 32 680563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return ((this_array[1]&((1<<(32-BI_DB))-1))<<BI_DB)|this_array[0]; 681563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 682563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 683563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) return value as byte 684563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnByteValue() { 685563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 686563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return (this.t==0)?this.s:(this_array[0]<<24)>>24; 687563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 688563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 689563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) return value as short (assumes DB>=16) 690563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnShortValue() { 691563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 692563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return (this.t==0)?this.s:(this_array[0]<<16)>>16; 693563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 694563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 695563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) return x s.t. r^x < DV 696563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpChunkSize(r) { return Math.floor(Math.LN2*BI_DB/Math.log(r)); } 697563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 698563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) 0 if this == 0, 1 if this > 0 699563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnSigNum() { 700563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 701563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.s < 0) return -1; 702563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(this.t <= 0 || (this.t == 1 && this_array[0] <= 0)) return 0; 703563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else return 1; 704563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 705563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 706563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) convert to radix string 707563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpToRadix(b) { 708563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(b == null) b = 10; 709563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.signum() == 0 || b < 2 || b > 36) return "0"; 710563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var cs = this.chunkSize(b); 711563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var a = Math.pow(b,cs); 712563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var d = nbv(a), y = nbi(), z = nbi(), r = ""; 713563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.divRemTo(d,y,z); 714563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(y.signum() > 0) { 715563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r = (a+z.intValue()).toString(b).substr(1) + r; 716563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark y.divRemTo(d,y,z); 717563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 718563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return z.intValue().toString(b) + r; 719563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 720563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 721563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) convert from radix string 722563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpFromRadix(s,b) { 723563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.fromInt(0); 724563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(b == null) b = 10; 725563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var cs = this.chunkSize(b); 726563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var d = Math.pow(b,cs), mi = false, j = 0, w = 0; 727563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(var i = 0; i < s.length; ++i) { 728563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var x = intAt(s,i); 729563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(x < 0) { 730563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(s.charAt(i) == "-" && this.signum() == 0) mi = true; 731563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark continue; 732563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 733563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark w = b*w+x; 734563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(++j >= cs) { 735563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.dMultiply(d); 736563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.dAddOffset(w,0); 737563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark j = 0; 738563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark w = 0; 739563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 740563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 741563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(j > 0) { 742563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.dMultiply(Math.pow(b,j)); 743563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.dAddOffset(w,0); 744563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 745563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(mi) BigInteger.ZERO.subTo(this,this); 746563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 747563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 748563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) alternate constructor 749563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpFromNumber(a,b,c) { 750563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if("number" == typeof b) { 751563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // new BigInteger(int,int,RNG) 752563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(a < 2) this.fromInt(1); 753563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else { 754563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.fromNumber(a,c); 755563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(!this.testBit(a-1)) // force MSB set 756563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.bitwiseTo(BigInteger.ONE.shiftLeft(a-1),op_or,this); 757563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.isEven()) this.dAddOffset(1,0); // force odd 758563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(!this.isProbablePrime(b)) { 759563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.dAddOffset(2,0); 760563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.bitLength() > a) this.subTo(BigInteger.ONE.shiftLeft(a-1),this); 761563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 762563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 763563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 764563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else { 765563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // new BigInteger(int,RNG) 766563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var x = new Array(), t = a&7; 767563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark x.length = (a>>3)+1; 768563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark b.nextBytes(x); 769563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(t > 0) x[0] &= ((1<<t)-1); else x[0] = 0; 770563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.fromString(x,256); 771563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 772563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 773563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 774563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) convert to bigendian byte array 775563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnToByteArray() { 776563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 777563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = this.t, r = new Array(); 778563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r[0] = this.s; 779563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var p = BI_DB-(i*BI_DB)%8, d, k = 0; 780563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(i-- > 0) { 781563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(p < BI_DB && (d = this_array[i]>>p) != (this.s&BI_DM)>>p) 782563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r[k++] = d|(this.s<<(BI_DB-p)); 783563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(i >= 0) { 784563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(p < 8) { 785563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark d = (this_array[i]&((1<<p)-1))<<(8-p); 786563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark d |= this_array[--i]>>(p+=BI_DB-8); 787563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 788563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else { 789563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark d = (this_array[i]>>(p-=8))&0xff; 790563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(p <= 0) { p += BI_DB; --i; } 791563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 792563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((d&0x80) != 0) d |= -256; 793563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(k == 0 && (this.s&0x80) != (d&0x80)) ++k; 794563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(k > 0 || d != this.s) r[k++] = d; 795563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 796563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 797563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return r; 798563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 799563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 800563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnEquals(a) { return(this.compareTo(a)==0); } 801563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnMin(a) { return(this.compareTo(a)<0)?this:a; } 802563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnMax(a) { return(this.compareTo(a)>0)?this:a; } 803563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 804563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) r = this op a (bitwise) 805563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpBitwiseTo(a,op,r) { 806563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 807563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var a_array = a.array; 808563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r_array = r.array; 809563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i, f, m = Math.min(a.t,this.t); 810563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(i = 0; i < m; ++i) r_array[i] = op(this_array[i],a_array[i]); 811563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(a.t < this.t) { 812563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark f = a.s&BI_DM; 813563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(i = m; i < this.t; ++i) r_array[i] = op(this_array[i],f); 814563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.t = this.t; 815563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 816563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else { 817563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark f = this.s&BI_DM; 818563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(i = m; i < a.t; ++i) r_array[i] = op(f,a_array[i]); 819563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.t = a.t; 820563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 821563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.s = op(this.s,a.s); 822563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.clamp(); 823563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 824563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 825563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this & a 826563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction op_and(x,y) { return x&y; } 827563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnAnd(a) { var r = nbi(); this.bitwiseTo(a,op_and,r); return r; } 828563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 829563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this | a 830563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction op_or(x,y) { return x|y; } 831563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnOr(a) { var r = nbi(); this.bitwiseTo(a,op_or,r); return r; } 832563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 833563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this ^ a 834563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction op_xor(x,y) { return x^y; } 835563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnXor(a) { var r = nbi(); this.bitwiseTo(a,op_xor,r); return r; } 836563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 837563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this & ~a 838563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction op_andnot(x,y) { return x&~y; } 839563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnAndNot(a) { var r = nbi(); this.bitwiseTo(a,op_andnot,r); return r; } 840563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 841563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) ~this 842563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnNot() { 843563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 844563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r = nbi(); 845563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r_array = r.array; 846563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 847563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(var i = 0; i < this.t; ++i) r_array[i] = BI_DM&~this_array[i]; 848563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.t = this.t; 849563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.s = ~this.s; 850563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return r; 851563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 852563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 853563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this << n 854563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnShiftLeft(n) { 855563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r = nbi(); 856563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(n < 0) this.rShiftTo(-n,r); else this.lShiftTo(n,r); 857563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return r; 858563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 859563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 860563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this >> n 861563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnShiftRight(n) { 862563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r = nbi(); 863563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(n < 0) this.lShiftTo(-n,r); else this.rShiftTo(n,r); 864563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return r; 865563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 866563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 867563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// return index of lowest 1-bit in x, x < 2^31 868563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction lbit(x) { 869563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(x == 0) return -1; 870563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r = 0; 871563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((x&0xffff) == 0) { x >>= 16; r += 16; } 872563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((x&0xff) == 0) { x >>= 8; r += 8; } 873563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((x&0xf) == 0) { x >>= 4; r += 4; } 874563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((x&3) == 0) { x >>= 2; r += 2; } 875563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((x&1) == 0) ++r; 876563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return r; 877563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 878563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 879563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) returns index of lowest 1-bit (or -1 if none) 880563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnGetLowestSetBit() { 881563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 882563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(var i = 0; i < this.t; ++i) 883563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this_array[i] != 0) return i*BI_DB+lbit(this_array[i]); 884563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.s < 0) return this.t*BI_DB; 885563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return -1; 886563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 887563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 888563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// return number of 1 bits in x 889563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction cbit(x) { 890563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r = 0; 891563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(x != 0) { x &= x-1; ++r; } 892563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return r; 893563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 894563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 895563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) return number of set bits 896563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnBitCount() { 897563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r = 0, x = this.s&BI_DM; 898563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(var i = 0; i < this.t; ++i) r += cbit(this_array[i]^x); 899563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return r; 900563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 901563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 902563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) true iff nth bit is set 903563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnTestBit(n) { 904563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 905563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var j = Math.floor(n/BI_DB); 906563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(j >= this.t) return(this.s!=0); 907563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return((this_array[j]&(1<<(n%BI_DB)))!=0); 908563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 909563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 910563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) this op (1<<n) 911563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpChangeBit(n,op) { 912563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r = BigInteger.ONE.shiftLeft(n); 913563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.bitwiseTo(r,op,r); 914563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return r; 915563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 916563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 917563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this | (1<<n) 918563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnSetBit(n) { return this.changeBit(n,op_or); } 919563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 920563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this & ~(1<<n) 921563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnClearBit(n) { return this.changeBit(n,op_andnot); } 922563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 923563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this ^ (1<<n) 924563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnFlipBit(n) { return this.changeBit(n,op_xor); } 925563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 926563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) r = this + a 927563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpAddTo(a,r) { 928563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 929563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var a_array = a.array; 930563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r_array = r.array; 931563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = 0, c = 0, m = Math.min(a.t,this.t); 932563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(i < m) { 933563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c += this_array[i]+a_array[i]; 934563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r_array[i++] = c&BI_DM; 935563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c >>= BI_DB; 936563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 937563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(a.t < this.t) { 938563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c += a.s; 939563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(i < this.t) { 940563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c += this_array[i]; 941563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r_array[i++] = c&BI_DM; 942563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c >>= BI_DB; 943563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 944563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c += this.s; 945563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 946563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else { 947563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c += this.s; 948563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(i < a.t) { 949563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c += a_array[i]; 950563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r_array[i++] = c&BI_DM; 951563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c >>= BI_DB; 952563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 953563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c += a.s; 954563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 955563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.s = (c<0)?-1:0; 956563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(c > 0) r_array[i++] = c; 957563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(c < -1) r_array[i++] = BI_DV+c; 958563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.t = i; 959563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.clamp(); 960563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 961563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 962563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this + a 963563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnAdd(a) { var r = nbi(); this.addTo(a,r); return r; } 964563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 965563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this - a 966563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnSubtract(a) { var r = nbi(); this.subTo(a,r); return r; } 967563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 968563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this * a 969563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnMultiply(a) { var r = nbi(); this.multiplyTo(a,r); return r; } 970563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 971563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this / a 972563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnDivide(a) { var r = nbi(); this.divRemTo(a,r,null); return r; } 973563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 974563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this % a 975563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnRemainder(a) { var r = nbi(); this.divRemTo(a,null,r); return r; } 976563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 977563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) [this/a,this%a] 978563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnDivideAndRemainder(a) { 979563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var q = nbi(), r = nbi(); 980563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.divRemTo(a,q,r); 981563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return new Array(q,r); 982563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 983563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 984563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) this *= n, this >= 0, 1 < n < DV 985563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpDMultiply(n) { 986563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 987563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this_array[this.t] = this.am(0,n-1,this,0,0,this.t); 988563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ++this.t; 989563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.clamp(); 990563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 991563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 992563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) this += n << w words, this >= 0 993563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpDAddOffset(n,w) { 994563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 995563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(this.t <= w) this_array[this.t++] = 0; 996563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this_array[w] += n; 997563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(this_array[w] >= BI_DV) { 998563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this_array[w] -= BI_DV; 999563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(++w >= this.t) this_array[this.t++] = 0; 1000563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ++this_array[w]; 1001563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1002563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1003563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1004563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// A "null" reducer 1005563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction NullExp() {} 1006563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction nNop(x) { return x; } 1007563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction nMulTo(x,y,r) { x.multiplyTo(y,r); } 1008563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction nSqrTo(x,r) { x.squareTo(r); } 1009563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1010563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkNullExp.prototype.convert = nNop; 1011563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkNullExp.prototype.revert = nNop; 1012563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkNullExp.prototype.mulTo = nMulTo; 1013563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkNullExp.prototype.sqrTo = nSqrTo; 1014563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1015563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this^e 1016563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnPow(e) { return this.exp(e,new NullExp()); } 1017563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1018563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) r = lower n words of "this * a", a.t <= n 1019563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// "this" should be the larger one if appropriate. 1020563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpMultiplyLowerTo(a,n,r) { 1021563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r_array = r.array; 1022563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var a_array = a.array; 1023563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = Math.min(this.t+a.t,n); 1024563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.s = 0; // assumes a,this >= 0 1025563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.t = i; 1026563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(i > 0) r_array[--i] = 0; 1027563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var j; 1028563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(j = r.t-this.t; i < j; ++i) r_array[i+this.t] = this.am(0,a_array[i],r,i,0,this.t); 1029563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(j = Math.min(a.t,n); i < j; ++i) this.am(0,a_array[i],r,i,0,n-i); 1030563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.clamp(); 1031563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1032563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1033563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) r = "this * a" without lower n words, n > 0 1034563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// "this" should be the larger one if appropriate. 1035563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpMultiplyUpperTo(a,n,r) { 1036563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r_array = r.array; 1037563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var a_array = a.array; 1038563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark --n; 1039563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = r.t = this.t+a.t-n; 1040563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.s = 0; // assumes a,this >= 0 1041563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(--i >= 0) r_array[i] = 0; 1042563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(i = Math.max(n-this.t,0); i < a.t; ++i) 1043563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r_array[this.t+i-n] = this.am(n-i,a_array[i],r,0,0,this.t+i-n); 1044563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.clamp(); 1045563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark r.drShiftTo(1,r); 1046563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1047563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1048563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Barrett modular reduction 1049563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction Barrett(m) { 1050563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // setup Barrett 1051563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.r2 = nbi(); 1052563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.q3 = nbi(); 1053563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark BigInteger.ONE.dlShiftTo(2*m.t,this.r2); 1054563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.mu = this.r2.divide(m); 1055563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.m = m; 1056563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1057563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1058563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction barrettConvert(x) { 1059563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(x.s < 0 || x.t > 2*this.m.t) return x.mod(this.m); 1060563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(x.compareTo(this.m) < 0) return x; 1061563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else { var r = nbi(); x.copyTo(r); this.reduce(r); return r; } 1062563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1063563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1064563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction barrettRevert(x) { return x; } 1065563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1066563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// x = x mod m (HAC 14.42) 1067563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction barrettReduce(x) { 1068563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark x.drShiftTo(this.m.t-1,this.r2); 1069563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(x.t > this.m.t+1) { x.t = this.m.t+1; x.clamp(); } 1070563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.mu.multiplyUpperTo(this.r2,this.m.t+1,this.q3); 1071563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.m.multiplyLowerTo(this.q3,this.m.t+1,this.r2); 1072563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(x.compareTo(this.r2) < 0) x.dAddOffset(1,this.m.t+1); 1073563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark x.subTo(this.r2,x); 1074563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(x.compareTo(this.m) >= 0) x.subTo(this.m,x); 1075563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1076563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1077563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// r = x^2 mod m; x != r 1078563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction barrettSqrTo(x,r) { x.squareTo(r); this.reduce(r); } 1079563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1080563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// r = x*y mod m; x,y != r 1081563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction barrettMulTo(x,y,r) { x.multiplyTo(y,r); this.reduce(r); } 1082563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1083563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBarrett.prototype.convert = barrettConvert; 1084563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBarrett.prototype.revert = barrettRevert; 1085563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBarrett.prototype.reduce = barrettReduce; 1086563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBarrett.prototype.mulTo = barrettMulTo; 1087563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBarrett.prototype.sqrTo = barrettSqrTo; 1088563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1089563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) this^e % m (HAC 14.85) 1090563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnModPow(e,m) { 1091563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var e_array = e.array; 1092563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = e.bitLength(), k, r = nbv(1), z; 1093563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(i <= 0) return r; 1094563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(i < 18) k = 1; 1095563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(i < 48) k = 3; 1096563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(i < 144) k = 4; 1097563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(i < 768) k = 5; 1098563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else k = 6; 1099563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(i < 8) 1100563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark z = new Classic(m); 1101563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(m.isEven()) 1102563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark z = new Barrett(m); 1103563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else 1104563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark z = new Montgomery(m); 1105563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1106563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // precomputation 1107563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var g = new Array(), n = 3, k1 = k-1, km = (1<<k)-1; 1108563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark g[1] = z.convert(this); 1109563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(k > 1) { 1110563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var g2 = nbi(); 1111563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark z.sqrTo(g[1],g2); 1112563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(n <= km) { 1113563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark g[n] = nbi(); 1114563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark z.mulTo(g2,g[n-2],g[n]); 1115563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark n += 2; 1116563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1117563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1118563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1119563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var j = e.t-1, w, is1 = true, r2 = nbi(), t; 1120563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark i = nbits(e_array[j])-1; 1121563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(j >= 0) { 1122563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(i >= k1) w = (e_array[j]>>(i-k1))&km; 1123563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else { 1124563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark w = (e_array[j]&((1<<(i+1))-1))<<(k1-i); 1125563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(j > 0) w |= e_array[j-1]>>(BI_DB+i-k1); 1126563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1127563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1128563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark n = k; 1129563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while((w&1) == 0) { w >>= 1; --n; } 1130563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((i -= n) < 0) { i += BI_DB; --j; } 1131563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(is1) { // ret == 1, don't bother squaring or multiplying it 1132563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark g[w].copyTo(r); 1133563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark is1 = false; 1134563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1135563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else { 1136563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(n > 1) { z.sqrTo(r,r2); z.sqrTo(r2,r); n -= 2; } 1137563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(n > 0) z.sqrTo(r,r2); else { t = r; r = r2; r2 = t; } 1138563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark z.mulTo(r2,g[w],r); 1139563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1140563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1141563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(j >= 0 && (e_array[j]&(1<<i)) == 0) { 1142563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark z.sqrTo(r,r2); t = r; r = r2; r2 = t; 1143563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(--i < 0) { i = BI_DB-1; --j; } 1144563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1145563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1146563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return z.revert(r); 1147563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1148563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1149563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) gcd(this,a) (HAC 14.54) 1150563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnGCD(a) { 1151563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var x = (this.s<0)?this.negate():this.clone(); 1152563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var y = (a.s<0)?a.negate():a.clone(); 1153563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(x.compareTo(y) < 0) { var t = x; x = y; y = t; } 1154563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = x.getLowestSetBit(), g = y.getLowestSetBit(); 1155563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(g < 0) return x; 1156563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(i < g) g = i; 1157563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(g > 0) { 1158563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark x.rShiftTo(g,x); 1159563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark y.rShiftTo(g,y); 1160563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1161563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(x.signum() > 0) { 1162563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((i = x.getLowestSetBit()) > 0) x.rShiftTo(i,x); 1163563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((i = y.getLowestSetBit()) > 0) y.rShiftTo(i,y); 1164563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(x.compareTo(y) >= 0) { 1165563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark x.subTo(y,x); 1166563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark x.rShiftTo(1,x); 1167563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1168563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else { 1169563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark y.subTo(x,y); 1170563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark y.rShiftTo(1,y); 1171563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1172563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1173563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(g > 0) y.lShiftTo(g,y); 1174563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return y; 1175563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1176563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1177563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) this % n, n < 2^26 1178563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpModInt(n) { 1179563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var this_array = this.array; 1180563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(n <= 0) return 0; 1181563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var d = BI_DV%n, r = (this.s<0)?n-1:0; 1182563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.t > 0) 1183563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(d == 0) r = this_array[0]%n; 1184563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else for(var i = this.t-1; i >= 0; --i) r = (d*r+this_array[i])%n; 1185563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return r; 1186563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1187563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1188563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) 1/this % m (HAC 14.61) 1189563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnModInverse(m) { 1190563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var ac = m.isEven(); 1191563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((this.isEven() && ac) || m.signum() == 0) return BigInteger.ZERO; 1192563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var u = m.clone(), v = this.clone(); 1193563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var a = nbv(1), b = nbv(0), c = nbv(0), d = nbv(1); 1194563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(u.signum() != 0) { 1195563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(u.isEven()) { 1196563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark u.rShiftTo(1,u); 1197563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(ac) { 1198563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(!a.isEven() || !b.isEven()) { a.addTo(this,a); b.subTo(m,b); } 1199563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark a.rShiftTo(1,a); 1200563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1201563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(!b.isEven()) b.subTo(m,b); 1202563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark b.rShiftTo(1,b); 1203563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1204563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(v.isEven()) { 1205563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark v.rShiftTo(1,v); 1206563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(ac) { 1207563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(!c.isEven() || !d.isEven()) { c.addTo(this,c); d.subTo(m,d); } 1208563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark c.rShiftTo(1,c); 1209563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1210563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else if(!d.isEven()) d.subTo(m,d); 1211563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark d.rShiftTo(1,d); 1212563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1213563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(u.compareTo(v) >= 0) { 1214563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark u.subTo(v,u); 1215563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(ac) a.subTo(c,a); 1216563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark b.subTo(d,b); 1217563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1218563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else { 1219563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark v.subTo(u,v); 1220563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(ac) c.subTo(a,c); 1221563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark d.subTo(b,d); 1222563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1223563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1224563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(v.compareTo(BigInteger.ONE) != 0) return BigInteger.ZERO; 1225563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(d.compareTo(m) >= 0) return d.subtract(m); 1226563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(d.signum() < 0) d.addTo(m,d); else return d; 1227563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(d.signum() < 0) return d.add(m); else return d; 1228563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1229563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1230563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar lowprimes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509]; 1231563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar lplim = (1<<26)/lowprimes[lowprimes.length-1]; 1232563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1233563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (public) test primality with certainty >= 1-.5^t 1234563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnIsProbablePrime(t) { 1235563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i, x = this.abs(); 1236563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var x_array = x.array; 1237563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(x.t == 1 && x_array[0] <= lowprimes[lowprimes.length-1]) { 1238563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(i = 0; i < lowprimes.length; ++i) 1239563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(x_array[0] == lowprimes[i]) return true; 1240563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return false; 1241563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1242563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(x.isEven()) return false; 1243563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark i = 1; 1244563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(i < lowprimes.length) { 1245563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var m = lowprimes[i], j = i+1; 1246563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(j < lowprimes.length && m < lplim) m *= lowprimes[j++]; 1247563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark m = x.modInt(m); 1248563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(i < j) if(m%lowprimes[i++] == 0) return false; 1249563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1250563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return x.millerRabin(t); 1251563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1252563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1253563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// (protected) true if probably prime (HAC 4.24, Miller-Rabin) 1254563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction bnpMillerRabin(t) { 1255563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var n1 = this.subtract(BigInteger.ONE); 1256563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var k = n1.getLowestSetBit(); 1257563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(k <= 0) return false; 1258563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var r = n1.shiftRight(k); 1259563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark t = (t+1)>>1; 1260563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(t > lowprimes.length) t = lowprimes.length; 1261563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var a = nbi(); 1262563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(var i = 0; i < t; ++i) { 1263563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark a.fromInt(lowprimes[i]); 1264563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var y = a.modPow(r,this); 1265563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(y.compareTo(BigInteger.ONE) != 0 && y.compareTo(n1) != 0) { 1266563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var j = 1; 1267563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(j++ < k && y.compareTo(n1) != 0) { 1268563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark y = y.modPowInt(2,this); 1269563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(y.compareTo(BigInteger.ONE) == 0) return false; 1270563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1271563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(y.compareTo(n1) != 0) return false; 1272563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1273563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1274563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return true; 1275563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1276563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1277563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// protected 1278563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.chunkSize = bnpChunkSize; 1279563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.toRadix = bnpToRadix; 1280563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.fromRadix = bnpFromRadix; 1281563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.fromNumber = bnpFromNumber; 1282563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.bitwiseTo = bnpBitwiseTo; 1283563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.changeBit = bnpChangeBit; 1284563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.addTo = bnpAddTo; 1285563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.dMultiply = bnpDMultiply; 1286563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.dAddOffset = bnpDAddOffset; 1287563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.multiplyLowerTo = bnpMultiplyLowerTo; 1288563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.multiplyUpperTo = bnpMultiplyUpperTo; 1289563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.modInt = bnpModInt; 1290563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.millerRabin = bnpMillerRabin; 1291563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1292563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// public 1293563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.clone = bnClone; 1294563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.intValue = bnIntValue; 1295563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.byteValue = bnByteValue; 1296563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.shortValue = bnShortValue; 1297563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.signum = bnSigNum; 1298563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.toByteArray = bnToByteArray; 1299563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.equals = bnEquals; 1300563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.min = bnMin; 1301563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.max = bnMax; 1302563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.and = bnAnd; 1303563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.or = bnOr; 1304563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.xor = bnXor; 1305563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.andNot = bnAndNot; 1306563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.not = bnNot; 1307563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.shiftLeft = bnShiftLeft; 1308563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.shiftRight = bnShiftRight; 1309563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.getLowestSetBit = bnGetLowestSetBit; 1310563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.bitCount = bnBitCount; 1311563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.testBit = bnTestBit; 1312563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.setBit = bnSetBit; 1313563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.clearBit = bnClearBit; 1314563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.flipBit = bnFlipBit; 1315563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.add = bnAdd; 1316563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.subtract = bnSubtract; 1317563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.multiply = bnMultiply; 1318563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.divide = bnDivide; 1319563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.remainder = bnRemainder; 1320563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.divideAndRemainder = bnDivideAndRemainder; 1321563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.modPow = bnModPow; 1322563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.modInverse = bnModInverse; 1323563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.pow = bnPow; 1324563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.gcd = bnGCD; 1325563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkBigInteger.prototype.isProbablePrime = bnIsProbablePrime; 1326563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1327563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// BigInteger interfaces not implemented in jsbn: 1328563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1329563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// BigInteger(int signum, byte[] magnitude) 1330563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// double doubleValue() 1331563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// float floatValue() 1332563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// int hashCode() 1333563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// long longValue() 1334563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// static BigInteger valueOf(long val) 1335563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// prng4.js - uses Arcfour as a PRNG 1336563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1337563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction Arcfour() { 1338563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.i = 0; 1339563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.j = 0; 1340563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.S = new Array(); 1341563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1342563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1343563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Initialize arcfour context from key, an array of ints, each from [0..255] 1344563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction ARC4init(key) { 1345563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i, j, t; 1346563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(i = 0; i < 256; ++i) 1347563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.S[i] = i; 1348563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark j = 0; 1349563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(i = 0; i < 256; ++i) { 1350563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark j = (j + this.S[i] + key[i % key.length]) & 255; 1351563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark t = this.S[i]; 1352563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.S[i] = this.S[j]; 1353563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.S[j] = t; 1354563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1355563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.i = 0; 1356563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.j = 0; 1357563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1358563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1359563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction ARC4next() { 1360563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var t; 1361563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.i = (this.i + 1) & 255; 1362563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.j = (this.j + this.S[this.i]) & 255; 1363563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark t = this.S[this.i]; 1364563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.S[this.i] = this.S[this.j]; 1365563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.S[this.j] = t; 1366563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return this.S[(t + this.S[this.i]) & 255]; 1367563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1368563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1369563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkArcfour.prototype.init = ARC4init; 1370563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkArcfour.prototype.next = ARC4next; 1371563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1372563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Plug in your RNG constructor here 1373563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction prng_newstate() { 1374563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return new Arcfour(); 1375563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1376563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1377563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Pool size must be a multiple of 4 and greater than 32. 1378563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// An array of bytes the size of the pool will be passed to init() 1379563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar rng_psize = 256; 1380563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Random number generator - requires a PRNG backend, e.g. prng4.js 1381563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1382563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// For best results, put code like 1383563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// <body onClick='rng_seed_time();' onKeyPress='rng_seed_time();'> 1384563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// in your main HTML document. 1385563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1386563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar rng_state; 1387563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar rng_pool; 1388563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkvar rng_pptr; 1389563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1390563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Mix in a 32-bit integer into the pool 1391563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction rng_seed_int(x) { 1392563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark rng_pool[rng_pptr++] ^= x & 255; 1393563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark rng_pool[rng_pptr++] ^= (x >> 8) & 255; 1394563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark rng_pool[rng_pptr++] ^= (x >> 16) & 255; 1395563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark rng_pool[rng_pptr++] ^= (x >> 24) & 255; 1396563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(rng_pptr >= rng_psize) rng_pptr -= rng_psize; 1397563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1398563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1399563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Mix in the current time (w/milliseconds) into the pool 1400563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction rng_seed_time() { 14010bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch // Use pre-computed date to avoid making the benchmark 14020bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch // results dependent on the current date. 14030bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch rng_seed_int(1122926989487); 1404563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1405563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1406563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Initialize the pool with junk if needed. 1407563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkif(rng_pool == null) { 1408563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark rng_pool = new Array(); 1409563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark rng_pptr = 0; 1410563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var t; 1411563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(rng_pptr < rng_psize) { // extract some randomness from Math.random() 1412563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark t = Math.floor(65536 * Math.random()); 1413563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark rng_pool[rng_pptr++] = t >>> 8; 1414563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark rng_pool[rng_pptr++] = t & 255; 1415563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1416563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark rng_pptr = 0; 1417563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark rng_seed_time(); 1418563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark //rng_seed_int(window.screenX); 1419563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark //rng_seed_int(window.screenY); 1420563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1421563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1422563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction rng_get_byte() { 1423563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(rng_state == null) { 1424563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark rng_seed_time(); 1425563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark rng_state = prng_newstate(); 1426563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark rng_state.init(rng_pool); 1427563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(rng_pptr = 0; rng_pptr < rng_pool.length; ++rng_pptr) 1428563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark rng_pool[rng_pptr] = 0; 1429563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark rng_pptr = 0; 1430563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark //rng_pool = null; 1431563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1432563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // TODO: allow reseeding after first request 1433563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return rng_state.next(); 1434563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1435563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1436563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction rng_get_bytes(ba) { 1437563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i; 1438563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(i = 0; i < ba.length; ++i) ba[i] = rng_get_byte(); 1439563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1440563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1441563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction SecureRandom() {} 1442563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1443563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkSecureRandom.prototype.nextBytes = rng_get_bytes; 1444563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Depends on jsbn.js and rng.js 1445563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1446563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// convert a (hex) string to a bignum object 1447563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction parseBigInt(str,r) { 1448563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return new BigInteger(str,r); 1449563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1450563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1451563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction linebrk(s,n) { 1452563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var ret = ""; 1453563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = 0; 1454563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(i + n < s.length) { 1455563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ret += s.substring(i,i+n) + "\n"; 1456563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark i += n; 1457563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1458563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return ret + s.substring(i,s.length); 1459563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1460563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1461563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction byte2Hex(b) { 1462563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(b < 0x10) 1463563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return "0" + b.toString(16); 1464563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else 1465563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return b.toString(16); 1466563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1467563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1468563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// PKCS#1 (type 2, random) pad input string s to n bytes, and return a bigint 1469563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction pkcs1pad2(s,n) { 1470563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(n < s.length + 11) { 1471563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark alert("Message too long for RSA"); 1472563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return null; 1473563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1474563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var ba = new Array(); 1475563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = s.length - 1; 1476563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(i >= 0 && n > 0) ba[--n] = s.charCodeAt(i--); 1477563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ba[--n] = 0; 1478563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var rng = new SecureRandom(); 1479563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var x = new Array(); 1480563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(n > 2) { // random non-zero pad 1481563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark x[0] = 0; 1482563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(x[0] == 0) rng.nextBytes(x); 1483563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ba[--n] = x[0]; 1484563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1485563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ba[--n] = 2; 1486563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ba[--n] = 0; 1487563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return new BigInteger(ba); 1488563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1489563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1490563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// "empty" RSA key constructor 1491563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction RSAKey() { 1492563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.n = null; 1493563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.e = 0; 1494563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.d = null; 1495563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.p = null; 1496563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.q = null; 1497563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.dmp1 = null; 1498563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.dmq1 = null; 1499563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.coeff = null; 1500563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1501563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1502563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Set the public key fields N and e from hex strings 1503563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction RSASetPublic(N,E) { 1504563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(N != null && E != null && N.length > 0 && E.length > 0) { 1505563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.n = parseBigInt(N,16); 1506563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.e = parseInt(E,16); 1507563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1508563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else 1509563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark alert("Invalid RSA public key"); 1510563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1511563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1512563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Perform raw public operation on "x": return x^e (mod n) 1513563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction RSADoPublic(x) { 1514563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return x.modPowInt(this.e, this.n); 1515563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1516563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1517563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Return the PKCS#1 RSA encryption of "text" as an even-length hex string 1518563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction RSAEncrypt(text) { 1519563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var m = pkcs1pad2(text,(this.n.bitLength()+7)>>3); 1520563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(m == null) return null; 1521563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var c = this.doPublic(m); 1522563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(c == null) return null; 1523563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var h = c.toString(16); 1524563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if((h.length & 1) == 0) return h; else return "0" + h; 1525563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1526563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1527563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Return the PKCS#1 RSA encryption of "text" as a Base64-encoded string 1528563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark//function RSAEncryptB64(text) { 1529563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// var h = this.encrypt(text); 1530563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// if(h) return hex2b64(h); else return null; 1531563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark//} 1532563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1533563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// protected 1534563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkRSAKey.prototype.doPublic = RSADoPublic; 1535563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1536563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// public 1537563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkRSAKey.prototype.setPublic = RSASetPublic; 1538563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkRSAKey.prototype.encrypt = RSAEncrypt; 1539563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark//RSAKey.prototype.encrypt_b64 = RSAEncryptB64; 1540563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Depends on rsa.js and jsbn2.js 1541563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1542563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Undo PKCS#1 (type 2, random) padding and, if valid, return the plaintext 1543563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction pkcs1unpad2(d,n) { 1544563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var b = d.toByteArray(); 1545563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var i = 0; 1546563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(i < b.length && b[i] == 0) ++i; 1547563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(b.length-i != n-1 || b[i] != 2) 1548563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return null; 1549563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ++i; 1550563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(b[i] != 0) 1551563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(++i >= b.length) return null; 1552563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var ret = ""; 1553563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(++i < b.length) 1554563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark ret += String.fromCharCode(b[i]); 1555563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return ret; 1556563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1557563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1558563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Set the private key fields N, e, and d from hex strings 1559563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction RSASetPrivate(N,E,D) { 1560563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(N != null && E != null && N.length > 0 && E.length > 0) { 1561563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.n = parseBigInt(N,16); 1562563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.e = parseInt(E,16); 1563563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.d = parseBigInt(D,16); 1564563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1565563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else 1566563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark alert("Invalid RSA private key"); 1567563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1568563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1569563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Set the private key fields N, e, d and CRT params from hex strings 1570563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction RSASetPrivateEx(N,E,D,P,Q,DP,DQ,C) { 1571563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(N != null && E != null && N.length > 0 && E.length > 0) { 1572563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.n = parseBigInt(N,16); 1573563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.e = parseInt(E,16); 1574563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.d = parseBigInt(D,16); 1575563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.p = parseBigInt(P,16); 1576563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.q = parseBigInt(Q,16); 1577563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.dmp1 = parseBigInt(DP,16); 1578563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.dmq1 = parseBigInt(DQ,16); 1579563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.coeff = parseBigInt(C,16); 1580563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1581563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark else 1582563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark alert("Invalid RSA private key"); 1583563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1584563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1585563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Generate a new random private key B bits long, using public expt E 1586563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction RSAGenerate(B,E) { 1587563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var rng = new SecureRandom(); 1588563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var qs = B>>1; 1589563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.e = parseInt(E,16); 1590563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var ee = new BigInteger(E,16); 1591563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(;;) { 1592563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(;;) { 1593563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.p = new BigInteger(B-qs,1,rng); 1594563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.p.subtract(BigInteger.ONE).gcd(ee).compareTo(BigInteger.ONE) == 0 && this.p.isProbablePrime(10)) break; 1595563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1596563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark for(;;) { 1597563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.q = new BigInteger(qs,1,rng); 1598563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.q.subtract(BigInteger.ONE).gcd(ee).compareTo(BigInteger.ONE) == 0 && this.q.isProbablePrime(10)) break; 1599563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1600563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.p.compareTo(this.q) <= 0) { 1601563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var t = this.p; 1602563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.p = this.q; 1603563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.q = t; 1604563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1605563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var p1 = this.p.subtract(BigInteger.ONE); 1606563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var q1 = this.q.subtract(BigInteger.ONE); 1607563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var phi = p1.multiply(q1); 1608563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(phi.gcd(ee).compareTo(BigInteger.ONE) == 0) { 1609563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.n = this.p.multiply(this.q); 1610563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.d = ee.modInverse(phi); 1611563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.dmp1 = this.d.mod(p1); 1612563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.dmq1 = this.d.mod(q1); 1613563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark this.coeff = this.q.modInverse(this.p); 1614563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark break; 1615563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1616563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark } 1617563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1618563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1619563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Perform raw private operation on "x": return x^d (mod n) 1620563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction RSADoPrivate(x) { 1621563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(this.p == null || this.q == null) 1622563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return x.modPow(this.d, this.n); 1623563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1624563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark // TODO: re-calculate any missing CRT params 1625563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var xp = x.mod(this.p).modPow(this.dmp1, this.p); 1626563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var xq = x.mod(this.q).modPow(this.dmq1, this.q); 1627563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1628563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark while(xp.compareTo(xq) < 0) 1629563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark xp = xp.add(this.p); 1630563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return xp.subtract(xq).multiply(this.coeff).mod(this.p).multiply(this.q).add(xq); 1631563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1632563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1633563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Return the PKCS#1 RSA decryption of "ctext". 1634563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// "ctext" is an even-length hex string and the output is a plain string. 1635563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction RSADecrypt(ctext) { 1636563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var c = parseBigInt(ctext, 16); 1637563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark var m = this.doPrivate(c); 1638563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark if(m == null) return null; 1639563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark return pkcs1unpad2(m, (this.n.bitLength()+7)>>3); 1640563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1641563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1642563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// Return the PKCS#1 RSA decryption of "ctext". 1643563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// "ctext" is a Base64-encoded string and the output is a plain string. 1644563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark//function RSAB64Decrypt(ctext) { 1645563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// var h = b64tohex(ctext); 1646563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// if(h) return this.decrypt(h); else return null; 1647563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark//} 1648563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1649563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// protected 1650563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkRSAKey.prototype.doPrivate = RSADoPrivate; 1651563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1652563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark// public 1653563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkRSAKey.prototype.setPrivate = RSASetPrivate; 1654563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkRSAKey.prototype.setPrivateEx = RSASetPrivateEx; 1655563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkRSAKey.prototype.generate = RSAGenerate; 1656563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkRSAKey.prototype.decrypt = RSADecrypt; 1657563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark//RSAKey.prototype.b64_decrypt = RSAB64Decrypt; 1658563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1659563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1660563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarknValue="a5261939975948bb7a58dffe5ff54e65f0498f9175f5a09288810b8975871e99af3b5dd94057b0fc07535f5f97444504fa35169d461d0d30cf0192e307727c065168c788771c561a9400fb49175e9e6aa4e23fe11af69e9412dd23b0cb6684c4c2429bce139e848ab26d0829073351f4acd36074eafd036a5eb83359d2a698d3"; 1661563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkeValue="10001"; 1662563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkdValue="8e9912f6d3645894e8d38cb58c0db81ff516cf4c7e5a14c7f1eddb1459d2cded4d8d293fc97aee6aefb861859c8b6a3d1dfe710463e1f9ddc72048c09751971c4a580aa51eb523357a3cc48d31cfad1d4a165066ed92d4748fb6571211da5cb14bc11b6e2df7c1a559e6d5ac1cd5c94703a22891464fba23d0d965086277a161"; 1663563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkpValue="d090ce58a92c75233a6486cb0a9209bf3583b64f540c76f5294bb97d285eed33aec220bde14b2417951178ac152ceab6da7090905b478195498b352048f15e7d"; 1664563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkqValue="cab575dc652bb66df15a0359609d51d1db184750c00c6698b90ef3465c99655103edbf0d54c56aec0ce3c4d22592338092a126a0cc49f65a4a30d222b411e58f"; 1665563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkdmp1Value="1a24bca8e273df2f0e47c199bbf678604e7df7215480c77c8db39f49b000ce2cf7500038acfff5433b7d582a01f1826e6f4d42e1c57f5e1fef7b12aabc59fd25"; 1666563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkdmq1Value="3d06982efbbe47339e1f6d36b1216b8a741d410b0c662f54f7118b27b9a4ec9d914337eb39841d8666f3034408cf94f5b62f11c402fc994fe15a05493150d9fd"; 1667563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarkcoeffValue="3a3e731acd8960b7ff9eb81a7ff93bd1cfa74cbd56987db58b4594fb09c09084db1734c8143f98b602b981aaa9243ca28deb69b5b280ee8dcee0fd2625e53250"; 1668563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1669563af33bc48281d19dce701398dbb88cb54fd7ecCary ClarksetupEngine(am3, 28); 1670563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 16710bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdochvar TEXT = "The quick brown fox jumped over the extremely lazy frog! " + 16720bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch "Now is the time for all good men to come to the party."; 16730bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdochvar encrypted; 1674563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1675563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction encrypt() { 16760bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch var RSA = new RSAKey(); 16770bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch RSA.setPublic(nValue, eValue); 16780bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch RSA.setPrivateEx(nValue, eValue, dValue, pValue, qValue, dmp1Value, dmq1Value, coeffValue); 16790bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch encrypted = RSA.encrypt(TEXT); 1680563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1681563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1682563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfunction decrypt() { 16830bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch var RSA = new RSAKey(); 16840bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch RSA.setPublic(nValue, eValue); 16850bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch RSA.setPrivateEx(nValue, eValue, dValue, pValue, qValue, dmp1Value, dmq1Value, coeffValue); 16860bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch var decrypted = RSA.decrypt(encrypted); 16870bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch if (decrypted != TEXT) { 16880bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch throw new Error("Crypto operation failed"); 16890bf48ef3be53ddaa52bbead65dfd75bf90e7a2b5Ben Murdoch } 1690563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1691563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark 1692563af33bc48281d19dce701398dbb88cb54fd7ecCary Clarkfor (var i = 0; i < 8; ++i) { 1693563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark encrypt(); 1694563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark decrypt(); 1695563af33bc48281d19dce701398dbb88cb54fd7ecCary Clark} 1696