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