colonymech / docs / www / colonyscout / internal / js / jquery.jcryption-1.1.js @ f59acf11
History | View | Annotate | Download (16.9 KB)
1 |
/*
|
---|---|
2 |
* jCryption JavaScript data encryption v1.1
|
3 |
* http://www.jcryption.org/
|
4 |
*
|
5 |
* Copyright (c) 2010 Daniel Griesser
|
6 |
* Dual licensed under the MIT and GPL licenses.
|
7 |
* http://www.opensource.org/licenses/mit-license.php
|
8 |
* http://www.opensource.org/licenses/gpl-2.0.php
|
9 |
*
|
10 |
* If you need any further information about this plugin please
|
11 |
* visit my homepage or contact me under daniel.griesser@jcryption.org
|
12 |
*/
|
13 |
(function($) { |
14 |
$.jCryption = function(el, options) { |
15 |
var base = this; |
16 |
|
17 |
base.$el = $(el); |
18 |
base.el = el; |
19 |
|
20 |
base.$el.data("jCryption", base); |
21 |
base.init = function() { |
22 |
|
23 |
base.options = $.extend({},$.jCryption.defaultOptions, options); |
24 |
|
25 |
$encryptedElement = $("<input />",{ |
26 |
type:'hidden', |
27 |
name:base.options.postVariable
|
28 |
}); |
29 |
|
30 |
if (base.options.submitElement !== false) { |
31 |
var $submitElement = base.options.submitElement; |
32 |
} else {
|
33 |
var $submitElement = base.$el.find(":input:submit"); |
34 |
} |
35 |
|
36 |
$submitElement.bind(base.options.submitEvent,function() { |
37 |
$(this).attr("disabled",true); |
38 |
if(base.options.beforeEncryption()) {
|
39 |
$.jCryption.getKeys(base.options.getKeysURL,function(keys) { |
40 |
$.jCryption.encrypt(base.$el.serialize(),keys,function(encrypted) { |
41 |
$encryptedElement.val(encrypted);
|
42 |
$(base.$el).find(":input").attr("disabled",true).end().append($encryptedElement).submit(); |
43 |
}); |
44 |
}); |
45 |
} |
46 |
return false; |
47 |
}); |
48 |
|
49 |
}; |
50 |
|
51 |
base.init(); |
52 |
}; |
53 |
|
54 |
$.jCryption.getKeys = function(url,callback) { |
55 |
var base = this; |
56 |
base.getKeys = function() { |
57 |
$.getJSON(url,function(data){ |
58 |
keys = new base.jCryptionKeyPair(data.e,data.n,data.maxdigits);
|
59 |
if($.isFunction(callback)) { |
60 |
callback.call(this, keys);
|
61 |
} |
62 |
}); |
63 |
}; |
64 |
|
65 |
base.jCryptionKeyPair = function(encryptionExponent, modulus, maxdigits) { |
66 |
setMaxDigits(parseInt(maxdigits,10));
|
67 |
this.e = biFromHex(encryptionExponent);
|
68 |
this.m = biFromHex(modulus);
|
69 |
this.chunkSize = 2 * biHighIndex(this.m); |
70 |
this.radix = 16; |
71 |
this.barrett = new BarrettMu(this.m); |
72 |
}; |
73 |
|
74 |
base.getKeys(); |
75 |
}; |
76 |
|
77 |
$.jCryption.encrypt = function(string,keyPair,callback) { |
78 |
var charSum = 0; |
79 |
for(var i = 0; i < string.length; i++){ |
80 |
charSum += string.charCodeAt(i); |
81 |
} |
82 |
var tag = '0123456789abcdef'; |
83 |
var hex = ''; |
84 |
hex += tag.charAt((charSum & 0xF0) >> 4) + tag.charAt(charSum & 0x0F); |
85 |
|
86 |
var taggedString = hex + string;
|
87 |
|
88 |
var encrypt = [];
|
89 |
var j = 0; |
90 |
|
91 |
while (j < taggedString.length) {
|
92 |
encrypt[j] = taggedString.charCodeAt(j); |
93 |
j++; |
94 |
} |
95 |
|
96 |
while (encrypt.length % keyPair.chunkSize !== 0) { |
97 |
encrypt[j++] = 0;
|
98 |
} |
99 |
|
100 |
function encryption(encryptObject) { |
101 |
var charCounter = 0; |
102 |
var j, block;
|
103 |
var encrypted = ""; |
104 |
function encryptChar() { |
105 |
block = new BigInt();
|
106 |
j = 0;
|
107 |
for (var k = charCounter; k < charCounter+keyPair.chunkSize; ++j) { |
108 |
block.digits[j] = encryptObject[k++]; |
109 |
block.digits[j] += encryptObject[k++] << 8;
|
110 |
} |
111 |
var crypt = keyPair.barrett.powMod(block, keyPair.e);
|
112 |
var text = keyPair.radix == 16 ? biToHex(crypt) : biToString(crypt, keyPair.radix); |
113 |
encrypted += text + " ";
|
114 |
charCounter += keyPair.chunkSize; |
115 |
if (charCounter < encryptObject.length) {
|
116 |
setTimeout(encryptChar, 1)
|
117 |
} else {
|
118 |
var encryptedString = encrypted.substring(0, encrypted.length - 1); |
119 |
if($.isFunction(callback)) { |
120 |
callback(encryptedString); |
121 |
} else {
|
122 |
return encryptedString;
|
123 |
} |
124 |
|
125 |
} |
126 |
} |
127 |
setTimeout(encryptChar, 1);
|
128 |
} |
129 |
|
130 |
encryption(encrypt); |
131 |
}; |
132 |
|
133 |
$.jCryption.defaultOptions = {
|
134 |
submitElement:false, |
135 |
submitEvent:"click", |
136 |
getKeysURL:"main.php?generateKeypair=true", |
137 |
beforeEncryption:function(){return true}, |
138 |
postVariable:"jCryption" |
139 |
}; |
140 |
|
141 |
$.fn.jCryption = function(options) { |
142 |
return this.each(function(){ |
143 |
(new $.jCryption(this, options)); |
144 |
}); |
145 |
}; |
146 |
|
147 |
})(jQuery); |
148 |
|
149 |
/*
|
150 |
* BigInt, a suite of routines for performing multiple-precision arithmetic in
|
151 |
* JavaScript.
|
152 |
* BarrettMu, a class for performing Barrett modular reduction computations in
|
153 |
* JavaScript.
|
154 |
*
|
155 |
*
|
156 |
* Copyright 1998-2005 David Shapiro.
|
157 |
* dave@ohdave.com
|
158 |
*
|
159 |
* changed and improved by Daniel Griesser
|
160 |
* http://www.jcryption.org/
|
161 |
* Daniel Griesser <daniel.griesser@jcryption.org>
|
162 |
*/
|
163 |
var biRadixBase = 2; |
164 |
var biRadixBits = 16; |
165 |
var bitsPerDigit = biRadixBits;
|
166 |
var biRadix = 1 << 16; |
167 |
var biHalfRadix = biRadix >>> 1; |
168 |
var biRadixSquared = biRadix * biRadix;
|
169 |
var maxDigitVal = biRadix - 1; |
170 |
var maxInteger = 9999999999999998; |
171 |
var maxDigits;
|
172 |
var ZERO_ARRAY;
|
173 |
var bigZero, bigOne;
|
174 |
var dpl10 = 15; |
175 |
var highBitMasks = new Array(0x0000, 0x8000, 0xC000, 0xE000, 0xF000, 0xF800, |
176 |
0xFC00, 0xFE00, 0xFF00, 0xFF80, 0xFFC0, 0xFFE0, |
177 |
0xFFF0, 0xFFF8, 0xFFFC, 0xFFFE, 0xFFFF); |
178 |
|
179 |
var hexatrigesimalToChar = new Array( |
180 |
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', |
181 |
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', |
182 |
'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', |
183 |
'u', 'v', 'w', 'x', 'y', 'z' |
184 |
); |
185 |
|
186 |
var hexToChar = new Array('0', '1', '2', '3', '4', '5', '6', '7', '8', '9', |
187 |
'a', 'b', 'c', 'd', 'e', 'f'); |
188 |
|
189 |
var lowBitMasks = new Array(0x0000, 0x0001, 0x0003, 0x0007, 0x000F, 0x001F, |
190 |
0x003F, 0x007F, 0x00FF, 0x01FF, 0x03FF, 0x07FF, |
191 |
0x0FFF, 0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF); |
192 |
|
193 |
function setMaxDigits(value) { |
194 |
maxDigits = value; |
195 |
ZERO_ARRAY = new Array(maxDigits);
|
196 |
for (var iza = 0; iza < ZERO_ARRAY.length; iza++) ZERO_ARRAY[iza] = 0; |
197 |
bigZero = new BigInt();
|
198 |
bigOne = new BigInt();
|
199 |
bigOne.digits[0] = 1; |
200 |
} |
201 |
|
202 |
function BigInt(flag) { |
203 |
if (typeof flag == "boolean" && flag == true) { |
204 |
this.digits = null; |
205 |
} |
206 |
else {
|
207 |
this.digits = ZERO_ARRAY.slice(0); |
208 |
} |
209 |
this.isNeg = false; |
210 |
} |
211 |
|
212 |
function biFromDecimal(s) { |
213 |
var isNeg = s.charAt(0) == '-'; |
214 |
var i = isNeg ? 1 : 0; |
215 |
var result;
|
216 |
while (i < s.length && s.charAt(i) == '0') ++i; |
217 |
if (i == s.length) {
|
218 |
result = new BigInt();
|
219 |
} |
220 |
else {
|
221 |
var digitCount = s.length - i;
|
222 |
var fgl = digitCount % dpl10;
|
223 |
if (fgl == 0) fgl = dpl10; |
224 |
result = biFromNumber(Number(s.substr(i, fgl))); |
225 |
i += fgl; |
226 |
while (i < s.length) {
|
227 |
result = biAdd(biMultiply(result, biFromNumber(1000000000000000)),
|
228 |
biFromNumber(Number(s.substr(i, dpl10)))); |
229 |
i += dpl10; |
230 |
} |
231 |
result.isNeg = isNeg; |
232 |
} |
233 |
return result;
|
234 |
} |
235 |
|
236 |
function biCopy(bi) { |
237 |
var result = new BigInt(true); |
238 |
result.digits = bi.digits.slice(0);
|
239 |
result.isNeg = bi.isNeg; |
240 |
return result;
|
241 |
} |
242 |
|
243 |
function biFromNumber(i) { |
244 |
var result = new BigInt(); |
245 |
result.isNeg = i < 0;
|
246 |
i = Math.abs(i); |
247 |
var j = 0; |
248 |
while (i > 0) { |
249 |
result.digits[j++] = i & maxDigitVal; |
250 |
i >>= biRadixBits; |
251 |
} |
252 |
return result;
|
253 |
} |
254 |
|
255 |
function reverseStr(s) { |
256 |
var result = ""; |
257 |
for (var i = s.length - 1; i > -1; --i) { |
258 |
result += s.charAt(i); |
259 |
} |
260 |
return result;
|
261 |
} |
262 |
|
263 |
function biToString(x, radix) { |
264 |
var b = new BigInt(); |
265 |
b.digits[0] = radix;
|
266 |
var qr = biDivideModulo(x, b);
|
267 |
var result = hexatrigesimalToChar[qr[1].digits[0]]; |
268 |
while (biCompare(qr[0], bigZero) == 1) { |
269 |
qr = biDivideModulo(qr[0], b);
|
270 |
digit = qr[1].digits[0]; |
271 |
result += hexatrigesimalToChar[qr[1].digits[0]]; |
272 |
} |
273 |
return (x.isNeg ? "-" : "") + reverseStr(result); |
274 |
} |
275 |
|
276 |
function biToDecimal(x) { |
277 |
var b = new BigInt(); |
278 |
b.digits[0] = 10; |
279 |
var qr = biDivideModulo(x, b);
|
280 |
var result = String(qr[1].digits[0]); |
281 |
while (biCompare(qr[0], bigZero) == 1) { |
282 |
qr = biDivideModulo(qr[0], b);
|
283 |
result += String(qr[1].digits[0]); |
284 |
} |
285 |
return (x.isNeg ? "-" : "") + reverseStr(result); |
286 |
} |
287 |
|
288 |
function digitToHex(n) { |
289 |
var mask = 0xf; |
290 |
var result = ""; |
291 |
for (i = 0; i < 4; ++i) { |
292 |
result += hexToChar[n & mask]; |
293 |
n >>>= 4;
|
294 |
} |
295 |
return reverseStr(result);
|
296 |
} |
297 |
|
298 |
function biToHex(x) { |
299 |
var result = ""; |
300 |
var n = biHighIndex(x);
|
301 |
for (var i = biHighIndex(x); i > -1; --i) { |
302 |
result += digitToHex(x.digits[i]); |
303 |
} |
304 |
return result;
|
305 |
} |
306 |
|
307 |
function charToHex(c) { |
308 |
var ZERO = 48; |
309 |
var NINE = ZERO + 9; |
310 |
var littleA = 97; |
311 |
var littleZ = littleA + 25; |
312 |
var bigA = 65; |
313 |
var bigZ = 65 + 25; |
314 |
var result;
|
315 |
|
316 |
if (c >= ZERO && c <= NINE) {
|
317 |
result = c - ZERO; |
318 |
} else if (c >= bigA && c <= bigZ) { |
319 |
result = 10 + c - bigA;
|
320 |
} else if (c >= littleA && c <= littleZ) { |
321 |
result = 10 + c - littleA;
|
322 |
} else {
|
323 |
result = 0;
|
324 |
} |
325 |
return result;
|
326 |
} |
327 |
|
328 |
function hexToDigit(s) { |
329 |
var result = 0; |
330 |
var sl = Math.min(s.length, 4); |
331 |
for (var i = 0; i < sl; ++i) { |
332 |
result <<= 4;
|
333 |
result |= charToHex(s.charCodeAt(i)) |
334 |
} |
335 |
return result;
|
336 |
} |
337 |
|
338 |
function biFromHex(s) { |
339 |
var result = new BigInt(); |
340 |
var sl = s.length;
|
341 |
for (var i = sl, j = 0; i > 0; i -= 4, ++j) { |
342 |
result.digits[j] = hexToDigit(s.substr(Math.max(i - 4, 0), Math.min(i, 4))); |
343 |
} |
344 |
return result;
|
345 |
} |
346 |
|
347 |
function biFromString(s, radix) { |
348 |
var isNeg = s.charAt(0) == '-'; |
349 |
var istop = isNeg ? 1 : 0; |
350 |
var result = new BigInt(); |
351 |
var place = new BigInt(); |
352 |
place.digits[0] = 1; // radix^0 |
353 |
for (var i = s.length - 1; i >= istop; i--) { |
354 |
var c = s.charCodeAt(i);
|
355 |
var digit = charToHex(c);
|
356 |
var biDigit = biMultiplyDigit(place, digit);
|
357 |
result = biAdd(result, biDigit); |
358 |
place = biMultiplyDigit(place, radix); |
359 |
} |
360 |
result.isNeg = isNeg; |
361 |
return result;
|
362 |
} |
363 |
|
364 |
function biDump(b) { |
365 |
return (b.isNeg ? "-" : "") + b.digits.join(" "); |
366 |
} |
367 |
|
368 |
function biAdd(x, y) { |
369 |
var result;
|
370 |
|
371 |
if (x.isNeg != y.isNeg) {
|
372 |
y.isNeg = !y.isNeg; |
373 |
result = biSubtract(x, y); |
374 |
y.isNeg = !y.isNeg; |
375 |
} |
376 |
else {
|
377 |
result = new BigInt();
|
378 |
var c = 0; |
379 |
var n;
|
380 |
for (var i = 0; i < x.digits.length; ++i) { |
381 |
n = x.digits[i] + y.digits[i] + c; |
382 |
result.digits[i] = n & 0xffff;
|
383 |
c = Number(n >= biRadix); |
384 |
} |
385 |
result.isNeg = x.isNeg; |
386 |
} |
387 |
return result;
|
388 |
} |
389 |
|
390 |
function biSubtract(x, y) { |
391 |
var result;
|
392 |
if (x.isNeg != y.isNeg) {
|
393 |
y.isNeg = !y.isNeg; |
394 |
result = biAdd(x, y); |
395 |
y.isNeg = !y.isNeg; |
396 |
} else {
|
397 |
result = new BigInt();
|
398 |
var n, c;
|
399 |
c = 0;
|
400 |
for (var i = 0; i < x.digits.length; ++i) { |
401 |
n = x.digits[i] - y.digits[i] + c; |
402 |
result.digits[i] = n & 0xffff;
|
403 |
if (result.digits[i] < 0) result.digits[i] += biRadix; |
404 |
c = 0 - Number(n < 0); |
405 |
} |
406 |
if (c == -1) { |
407 |
c = 0;
|
408 |
for (var i = 0; i < x.digits.length; ++i) { |
409 |
n = 0 - result.digits[i] + c;
|
410 |
result.digits[i] = n & 0xffff;
|
411 |
if (result.digits[i] < 0) result.digits[i] += biRadix; |
412 |
c = 0 - Number(n < 0); |
413 |
} |
414 |
result.isNeg = !x.isNeg; |
415 |
} else {
|
416 |
result.isNeg = x.isNeg; |
417 |
} |
418 |
} |
419 |
return result;
|
420 |
} |
421 |
|
422 |
function biHighIndex(x) { |
423 |
var result = x.digits.length - 1; |
424 |
while (result > 0 && x.digits[result] == 0) --result; |
425 |
return result;
|
426 |
} |
427 |
|
428 |
function biNumBits(x) { |
429 |
var n = biHighIndex(x);
|
430 |
var d = x.digits[n];
|
431 |
var m = (n + 1) * bitsPerDigit; |
432 |
var result;
|
433 |
for (result = m; result > m - bitsPerDigit; --result) {
|
434 |
if ((d & 0x8000) != 0) break; |
435 |
d <<= 1;
|
436 |
} |
437 |
return result;
|
438 |
} |
439 |
|
440 |
function biMultiply(x, y) { |
441 |
var result = new BigInt(); |
442 |
var c;
|
443 |
var n = biHighIndex(x);
|
444 |
var t = biHighIndex(y);
|
445 |
var u, uv, k;
|
446 |
|
447 |
for (var i = 0; i <= t; ++i) { |
448 |
c = 0;
|
449 |
k = i; |
450 |
for (j = 0; j <= n; ++j, ++k) { |
451 |
uv = result.digits[k] + x.digits[j] * y.digits[i] + c; |
452 |
result.digits[k] = uv & maxDigitVal; |
453 |
c = uv >>> biRadixBits; |
454 |
} |
455 |
result.digits[i + n + 1] = c;
|
456 |
} |
457 |
result.isNeg = x.isNeg != y.isNeg; |
458 |
return result;
|
459 |
} |
460 |
|
461 |
function biMultiplyDigit(x, y) { |
462 |
var n, c, uv;
|
463 |
|
464 |
result = new BigInt();
|
465 |
n = biHighIndex(x); |
466 |
c = 0;
|
467 |
for (var j = 0; j <= n; ++j) { |
468 |
uv = result.digits[j] + x.digits[j] * y + c; |
469 |
result.digits[j] = uv & maxDigitVal; |
470 |
c = uv >>> biRadixBits; |
471 |
} |
472 |
result.digits[1 + n] = c;
|
473 |
return result;
|
474 |
} |
475 |
|
476 |
function arrayCopy(src, srcStart, dest, destStart, n) { |
477 |
var m = Math.min(srcStart + n, src.length);
|
478 |
for (var i = srcStart, j = destStart; i < m; ++i, ++j) { |
479 |
dest[j] = src[i]; |
480 |
} |
481 |
} |
482 |
|
483 |
|
484 |
|
485 |
function biShiftLeft(x, n) { |
486 |
var digitCount = Math.floor(n / bitsPerDigit);
|
487 |
var result = new BigInt(); |
488 |
arrayCopy(x.digits, 0, result.digits, digitCount,result.digits.length - digitCount);
|
489 |
var bits = n % bitsPerDigit;
|
490 |
var rightBits = bitsPerDigit - bits;
|
491 |
for (var i = result.digits.length - 1, i1 = i - 1; i > 0; --i, --i1) { |
492 |
result.digits[i] = ((result.digits[i] << bits) & maxDigitVal) | |
493 |
((result.digits[i1] & highBitMasks[bits]) >>> |
494 |
(rightBits)); |
495 |
} |
496 |
result.digits[0] = ((result.digits[i] << bits) & maxDigitVal);
|
497 |
result.isNeg = x.isNeg; |
498 |
return result;
|
499 |
} |
500 |
|
501 |
function biShiftRight(x, n) { |
502 |
var digitCount = Math.floor(n / bitsPerDigit);
|
503 |
var result = new BigInt(); |
504 |
arrayCopy(x.digits, digitCount, result.digits, 0,x.digits.length - digitCount);
|
505 |
var bits = n % bitsPerDigit;
|
506 |
var leftBits = bitsPerDigit - bits;
|
507 |
for (var i = 0, i1 = i + 1; i < result.digits.length - 1; ++i, ++i1) { |
508 |
result.digits[i] = (result.digits[i] >>> bits) | |
509 |
((result.digits[i1] & lowBitMasks[bits]) << leftBits); |
510 |
} |
511 |
result.digits[result.digits.length - 1] >>>= bits;
|
512 |
result.isNeg = x.isNeg; |
513 |
return result;
|
514 |
} |
515 |
|
516 |
function biMultiplyByRadixPower(x, n) { |
517 |
var result = new BigInt(); |
518 |
arrayCopy(x.digits, 0, result.digits, n, result.digits.length - n);
|
519 |
return result;
|
520 |
} |
521 |
|
522 |
function biDivideByRadixPower(x, n) |
523 |
{ |
524 |
var result = new BigInt(); |
525 |
arrayCopy(x.digits, n, result.digits, 0, result.digits.length - n);
|
526 |
return result;
|
527 |
} |
528 |
|
529 |
function biModuloByRadixPower(x, n) |
530 |
{ |
531 |
var result = new BigInt(); |
532 |
arrayCopy(x.digits, 0, result.digits, 0, n); |
533 |
return result;
|
534 |
} |
535 |
|
536 |
function biCompare(x, y) { |
537 |
if (x.isNeg != y.isNeg) {
|
538 |
return 1 - 2 * Number(x.isNeg); |
539 |
} |
540 |
for (var i = x.digits.length - 1; i >= 0; --i) { |
541 |
if (x.digits[i] != y.digits[i]) {
|
542 |
if (x.isNeg) {
|
543 |
return 1 - 2 * Number(x.digits[i] > y.digits[i]); |
544 |
} else {
|
545 |
return 1 - 2 * Number(x.digits[i] < y.digits[i]); |
546 |
} |
547 |
} |
548 |
} |
549 |
return 0; |
550 |
} |
551 |
|
552 |
function biDivideModulo(x, y) { |
553 |
var nb = biNumBits(x);
|
554 |
var tb = biNumBits(y);
|
555 |
var origYIsNeg = y.isNeg;
|
556 |
var q, r;
|
557 |
if (nb < tb) {
|
558 |
if (x.isNeg) {
|
559 |
q = biCopy(bigOne); |
560 |
q.isNeg = !y.isNeg; |
561 |
x.isNeg = false;
|
562 |
y.isNeg = false;
|
563 |
r = biSubtract(y, x); |
564 |
x.isNeg = true;
|
565 |
y.isNeg = origYIsNeg; |
566 |
} else {
|
567 |
q = new BigInt();
|
568 |
r = biCopy(x); |
569 |
} |
570 |
return new Array(q, r); |
571 |
} |
572 |
|
573 |
q = new BigInt();
|
574 |
r = x; |
575 |
|
576 |
var t = Math.ceil(tb / bitsPerDigit) - 1; |
577 |
var lambda = 0; |
578 |
while (y.digits[t] < biHalfRadix) {
|
579 |
y = biShiftLeft(y, 1);
|
580 |
++lambda; |
581 |
++tb; |
582 |
t = Math.ceil(tb / bitsPerDigit) - 1;
|
583 |
} |
584 |
|
585 |
r = biShiftLeft(r, lambda); |
586 |
nb += lambda; |
587 |
var n = Math.ceil(nb / bitsPerDigit) - 1; |
588 |
|
589 |
var b = biMultiplyByRadixPower(y, n - t);
|
590 |
while (biCompare(r, b) != -1) { |
591 |
++q.digits[n - t]; |
592 |
r = biSubtract(r, b); |
593 |
} |
594 |
for (var i = n; i > t; --i) { |
595 |
var ri = (i >= r.digits.length) ? 0 : r.digits[i]; |
596 |
var ri1 = (i - 1 >= r.digits.length) ? 0 : r.digits[i - 1]; |
597 |
var ri2 = (i - 2 >= r.digits.length) ? 0 : r.digits[i - 2]; |
598 |
var yt = (t >= y.digits.length) ? 0 : y.digits[t]; |
599 |
var yt1 = (t - 1 >= y.digits.length) ? 0 : y.digits[t - 1]; |
600 |
if (ri == yt) {
|
601 |
q.digits[i - t - 1] = maxDigitVal;
|
602 |
} else {
|
603 |
q.digits[i - t - 1] = Math.floor((ri * biRadix + ri1) / yt);
|
604 |
} |
605 |
|
606 |
var c1 = q.digits[i - t - 1] * ((yt * biRadix) + yt1); |
607 |
var c2 = (ri * biRadixSquared) + ((ri1 * biRadix) + ri2);
|
608 |
while (c1 > c2) {
|
609 |
--q.digits[i - t - 1];
|
610 |
c1 = q.digits[i - t - 1] * ((yt * biRadix) | yt1);
|
611 |
c2 = (ri * biRadix * biRadix) + ((ri1 * biRadix) + ri2); |
612 |
} |
613 |
|
614 |
b = biMultiplyByRadixPower(y, i - t - 1);
|
615 |
r = biSubtract(r, biMultiplyDigit(b, q.digits[i - t - 1]));
|
616 |
if (r.isNeg) {
|
617 |
r = biAdd(r, b); |
618 |
--q.digits[i - t - 1];
|
619 |
} |
620 |
} |
621 |
r = biShiftRight(r, lambda); |
622 |
|
623 |
q.isNeg = x.isNeg != origYIsNeg; |
624 |
if (x.isNeg) {
|
625 |
if (origYIsNeg) {
|
626 |
q = biAdd(q, bigOne); |
627 |
} else {
|
628 |
q = biSubtract(q, bigOne); |
629 |
} |
630 |
y = biShiftRight(y, lambda); |
631 |
r = biSubtract(y, r); |
632 |
} |
633 |
|
634 |
if (r.digits[0] == 0 && biHighIndex(r) == 0) r.isNeg = false; |
635 |
|
636 |
return new Array(q, r); |
637 |
} |
638 |
|
639 |
function biDivide(x, y) { |
640 |
return biDivideModulo(x, y)[0]; |
641 |
} |
642 |
|
643 |
function biModulo(x, y) { |
644 |
return biDivideModulo(x, y)[1]; |
645 |
} |
646 |
|
647 |
function biMultiplyMod(x, y, m) { |
648 |
return biModulo(biMultiply(x, y), m);
|
649 |
} |
650 |
|
651 |
function biPow(x, y) { |
652 |
var result = bigOne;
|
653 |
var a = x;
|
654 |
while (true) { |
655 |
if ((y & 1) != 0) result = biMultiply(result, a); |
656 |
y >>= 1;
|
657 |
if (y == 0) break; |
658 |
a = biMultiply(a, a); |
659 |
} |
660 |
return result;
|
661 |
} |
662 |
|
663 |
function biPowMod(x, y, m) { |
664 |
var result = bigOne;
|
665 |
var a = x;
|
666 |
var k = y;
|
667 |
while (true) { |
668 |
if ((k.digits[0] & 1) != 0) result = biMultiplyMod(result, a, m); |
669 |
k = biShiftRight(k, 1);
|
670 |
if (k.digits[0] == 0 && biHighIndex(k) == 0) break; |
671 |
a = biMultiplyMod(a, a, m); |
672 |
} |
673 |
return result;
|
674 |
} |
675 |
|
676 |
function BarrettMu(m) { |
677 |
this.modulus = biCopy(m);
|
678 |
this.k = biHighIndex(this.modulus) + 1; |
679 |
var b2k = new BigInt(); |
680 |
b2k.digits[2 * this.k] = 1; |
681 |
this.mu = biDivide(b2k, this.modulus); |
682 |
this.bkplus1 = new BigInt(); |
683 |
this.bkplus1.digits[this.k + 1] = 1; |
684 |
this.modulo = BarrettMu_modulo;
|
685 |
this.multiplyMod = BarrettMu_multiplyMod;
|
686 |
this.powMod = BarrettMu_powMod;
|
687 |
} |
688 |
|
689 |
function BarrettMu_modulo(x) { |
690 |
var q1 = biDivideByRadixPower(x, this.k - 1); |
691 |
var q2 = biMultiply(q1, this.mu); |
692 |
var q3 = biDivideByRadixPower(q2, this.k + 1); |
693 |
var r1 = biModuloByRadixPower(x, this.k + 1); |
694 |
var r2term = biMultiply(q3, this.modulus); |
695 |
var r2 = biModuloByRadixPower(r2term, this.k + 1); |
696 |
var r = biSubtract(r1, r2);
|
697 |
if (r.isNeg) {
|
698 |
r = biAdd(r, this.bkplus1);
|
699 |
} |
700 |
var rgtem = biCompare(r, this.modulus) >= 0; |
701 |
while (rgtem) {
|
702 |
r = biSubtract(r, this.modulus);
|
703 |
rgtem = biCompare(r, this.modulus) >= 0; |
704 |
} |
705 |
return r;
|
706 |
} |
707 |
|
708 |
function BarrettMu_multiplyMod(x, y) { |
709 |
var xy = biMultiply(x, y);
|
710 |
return this.modulo(xy); |
711 |
} |
712 |
|
713 |
function BarrettMu_powMod(x, y) { |
714 |
var result = new BigInt(); |
715 |
result.digits[0] = 1; |
716 |
while (true) { |
717 |
if ((y.digits[0] & 1) != 0) result = this.multiplyMod(result, x); |
718 |
y = biShiftRight(y, 1);
|
719 |
if (y.digits[0] == 0 && biHighIndex(y) == 0) break; |
720 |
x = this.multiplyMod(x, x);
|
721 |
} |
722 |
return result;
|
723 |
} |