Changeset 2931 for trunk/phpgwapi
- Timestamp:
- 06/16/10 13:48:27 (14 years ago)
- Location:
- trunk/phpgwapi
- Files:
-
- 3 edited
- 1 moved
Legend:
- Unmodified
- Added
- Removed
-
trunk/phpgwapi/inc/class.common.inc.php
r2903 r2931 419 419 $GLOBALS[ 'phpgw' ] -> js -> validate_file( 'tools','xevent', NULL, true ); 420 420 $GLOBALS[ 'phpgw' ] -> js -> validate_file( 'tools','xobject', NULL, true ); 421 $GLOBALS[ 'phpgw' ] -> js -> validate_file( ' jscode', 'cookieManager', 'phpgwapi/templates/' . $GLOBALS['phpgw_info']['server']['template_set'] );421 $GLOBALS[ 'phpgw' ] -> js -> validate_file( 'templatejs', 'cookieManager', 'phpgwapi/templates/' . $GLOBALS['phpgw_info']['server']['template_set'] ); 422 422 423 423 $this -> phpgw_header( $module_content ); -
trunk/phpgwapi/js/expressoAjax/bigInt.js
r2847 r2931 68 68 // Those returning boolean or int will not allocate memory except possibly on the first 69 69 // time they're called with a given parameter size. 70 // 71 // bigInt add(x,y) //return (x+y) for bigInts x and y. 72 // bigInt addInt(x,n) //return (x+n) where x is a bigInt and n is an integer. 73 // string bigInt2str(x,base) //return a string form of bigInt x in a given base, with 2 <= base <= 95 74 // int bitSize(x) //return how many bits long the bigInt x is, not counting leading zeros 75 // bigInt dup(x) //return a copy of bigInt x 76 // boolean equals(x,y) //is the bigInt x equal to the bigint y? 77 // boolean equalsInt(x,y) //is bigint x equal to integer y? 78 // bigInt expand(x,n) //return a copy of x with at least n elements, adding leading zeros if needed 79 // Array findPrimes(n) //return array of all primes less than integer n 80 // bigInt GCD(x,y) //return greatest common divisor of bigInts x and y (each with same number of elements). 81 // boolean greater(x,y) //is x>y? (x and y are nonnegative bigInts) 82 // boolean greaterShift(x,y,shift)//is (x <<(shift*bpe)) > y? 83 // bigInt int2bigInt(t,n,m) //return a bigInt equal to integer t, with at least n bits and m array elements 84 // bigInt inverseMod(x,n) //return (x**(-1) mod n) for bigInts x and n. If no inverse exists, it returns null 85 // int inverseModInt(x,n) //return x**(-1) mod n, for integers x and n. Return 0 if there is no inverse 86 // boolean isZero(x) //is the bigInt x equal to zero? 87 // boolean millerRabin(x,b) //does one round of Miller-Rabin base integer b say that bigInt x is possibly prime? (b is bigInt, 1<b<x) 88 // boolean millerRabinInt(x,b) //does one round of Miller-Rabin base integer b say that bigInt x is possibly prime? (b is int, 1<b<x) 89 // bigInt mod(x,n) //return a new bigInt equal to (x mod n) for bigInts x and n. 90 // int modInt(x,n) //return x mod n for bigInt x and integer n. 91 // bigInt mult(x,y) //return x*y for bigInts x and y. This is faster when y<x. 92 // bigInt multMod(x,y,n) //return (x*y mod n) for bigInts x,y,n. For greater speed, let y<x. 93 // boolean negative(x) //is bigInt x negative? 94 // bigInt 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. 95 // bigInt randBigInt(n,s) //return an n-bit random BigInt (n>=1). If s=1, then the most significant of those n bits is set to 1. 96 // bigInt randTruePrime(k) //return a new, random, k-bit, true prime bigInt using Maurer's algorithm. 97 // bigInt randProbPrime(k) //return a new, random, k-bit, probable prime bigInt (probability it's composite less than 2^-80). 98 // bigInt str2bigInt(s,b,n,m) //return a bigInt for number represented in string s in base b with at least n bits and m array elements 99 // bigInt sub(x,y) //return (x-y) for bigInts x and y. Negative answers will be 2s complement 100 // bigInt trim(x,k) //return a copy of x with exactly k leading zero elements 101 // 102 // 103 // The following functions each have a non-underscored version, which most users should call instead. 104 // These functions each write to a single parameter, and the caller is responsible for ensuring the array 105 // passed in is large enough to hold the result. 106 // 107 // void addInt_(x,n) //do x=x+n where x is a bigInt and n is an integer 108 // void add_(x,y) //do x=x+y for bigInts x and y 109 // void copy_(x,y) //do x=y on bigInts x and y 110 // void copyInt_(x,n) //do x=n on bigInt x and integer n 111 // void GCD_(x,y) //set x to the greatest common divisor of bigInts x and y, (y is destroyed). (This never overflows its array). 112 // boolean inverseMod_(x,n) //do x=x**(-1) mod n, for bigInts x and n. Returns 1 (0) if inverse does (doesn't) exist 113 // void mod_(x,n) //do x=x mod n for bigInts x and n. (This never overflows its array). 114 // void mult_(x,y) //do x=x*y for bigInts x and y. 115 // void multMod_(x,y,n) //do x=x*y mod n for bigInts x,y,n. 116 // void powMod_(x,y,n) //do x=x**y mod n, where x,y,n are bigInts (n is odd) and ** is exponentiation. 0**0=1. 117 // void randBigInt_(b,n,s) //do b = an n-bit random BigInt. if s=1, then nth bit (most significant bit) is set to 1. n>=1. 118 // void randTruePrime_(ans,k) //do ans = a random k-bit true random prime (not just probable prime) with 1 in the msb. 119 // void sub_(x,y) //do x=x-y for bigInts x and y. Negative answers will be 2s complement. 120 // 121 // The following functions do NOT have a non-underscored version. 122 // They each write a bigInt result to one or more parameters. The caller is responsible for 123 // ensuring the arrays passed in are large enough to hold the results. 124 // 125 // void addShift_(x,y,ys) //do x=x+(y<<(ys*bpe)) 126 // void carry_(x) //do carries and borrows so each element of the bigInt x fits in bpe bits. 127 // void divide_(x,y,q,r) //divide x by y giving quotient q and remainder r 128 // int divInt_(x,n) //do x=floor(x/n) for bigInt x and integer n, and return the remainder. (This never overflows its array). 129 // int eGCD_(x,y,d,a,b) //sets a,b,d to positive bigInts such that d = GCD_(x,y) = a*x-b*y 130 // void halve_(x) //do x=floor(|x|/2)*sgn(x) for bigInt x in 2's complement. (This never overflows its array). 131 // void leftShift_(x,n) //left shift bigInt x by n bits. n<bpe. 132 // void linComb_(x,y,a,b) //do x=a*x+b*y for bigInts x and y and integers a and b 133 // void linCombShift_(x,y,b,ys) //do x=x+b*(y<<(ys*bpe)) for bigInts x and y, and integers b and ys 134 // void mont_(x,y,n,np) //Montgomery multiplication (see comments where the function is defined) 135 // void multInt_(x,n) //do x=x*n where x is a bigInt and n is an integer. 136 // void rightShift_(x,n) //right shift bigInt x by n bits. 0 <= n < bpe. (This never overflows its array). 137 // void squareMod_(x,n) //do x=x*x mod n for bigInts x,n 138 // void subShift_(x,y,ys) //do x=x-(y<<(ys*bpe)). Negative answers will be 2s complement. 139 // 140 // The following functions are based on algorithms from the _Handbook of Applied Cryptography_ 141 // powMod_() = algorithm 14.94, Montgomery exponentiation 142 // eGCD_,inverseMod_() = algorithm 14.61, Binary extended GCD_ 143 // GCD_() = algorothm 14.57, Lehmer's algorithm 144 // mont_() = algorithm 14.36, Montgomery multiplication 145 // divide_() = algorithm 14.20 Multiple-precision division 146 // squareMod_() = algorithm 14.16 Multiple-precision squaring 147 // randTruePrime_() = algorithm 4.62, Maurer's algorithm 148 // millerRabin() = algorithm 4.24, Miller-Rabin algorithm 149 // 150 // Profiling shows: 151 // randTruePrime_() spends: 152 // 10% of its time in calls to powMod_() 153 // 85% of its time in calls to millerRabin() 154 // millerRabin() spends: 155 // 99% of its time in calls to powMod_() (always with a base of 2) 156 // powMod_() spends: 157 // 94% of its time in calls to mont_() (almost always with x==y) 158 // 159 // This suggests there are several ways to speed up this library slightly: 160 // - convert powMod_ to use a Montgomery form of k-ary window (or maybe a Montgomery form of sliding window) 161 // -- this should especially focus on being fast when raising 2 to a power mod n 162 // - convert randTruePrime_() to use a minimum r of 1/3 instead of 1/2 with the appropriate change to the test 163 // - tune the parameters in randTruePrime_(), including c, m, and recLimit 164 // - speed up the single loop in mont_() that takes 95% of the runtime, perhaps by reducing checking 165 // within the loop when all the parameters are the same length. 166 // 167 // There are several ideas that look like they wouldn't help much at all: 168 // - replacing trial division in randTruePrime_() with a sieve (that speeds up something taking almost no time anyway) 169 // - 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) 170 // - speeding up mont_(x,y,n,np) when x==y by doing a non-modular, non-Montgomery square 171 // followed by a Montgomery reduction. The intermediate answer will be twice as long as x, so that 172 // method would be slower. This is unfortunate because the code currently spends almost all of its time 173 // doing mont_(x,x,...), both for randTruePrime_() and powMod_(). A faster method for Montgomery squaring 174 // would have a large impact on the speed of randTruePrime_() and powMod_(). HAC has a couple of poorly-worded 175 // sentences that seem to imply it's faster to do a non-modular square followed by a single 176 // Montgomery reduction, but that's obviously wrong. 177 //////////////////////////////////////////////////////////////////////////////////////// 70 178 71 179 72 //globals … … 214 107 rpprb=t; //used in randProbPrimeRounds() (which also uses "primes") 215 108 216 ////////////////////////////////////////////////////////////////////////////////////////217 218 219 //return array of all primes less than integer n220 function findPrimes(n) {221 var i,s,p,ans;222 s=new Array(n);223 for (i=0;i<n;i++)224 s[i]=0;225 s[0]=2;226 p=0; //first p elements of s are primes, the rest are a sieve227 for(;s[p]<n;) { //s[p] is the pth prime228 for(i=s[p]*s[p]; i<n; i+=s[p]) //mark multiples of s[p]229 s[i]=1;230 p++;231 s[p]=s[p-1]+1;232 for(; s[p]<n && s[s[p]]; s[p]++); //find next prime (where s[p]==0)233 }234 ans=new Array(p);235 for(i=0;i<p;i++)236 ans[i]=s[i];237 return ans;238 }239 240 241 //does a single round of Miller-Rabin base b consider x to be a possible prime?242 //x is a bigInt, and b is an integer, with b<x243 function millerRabinInt(x,b) {244 if (mr_x1.length!=x.length) {245 mr_x1=dup(x);246 mr_r=dup(x);247 mr_a=dup(x);248 }249 250 copyInt_(mr_a,b);251 return millerRabin(x,mr_a);252 }253 254 //does a single round of Miller-Rabin base b consider x to be a possible prime?255 //x and b are bigInts with b<x256 function millerRabin(x,b) {257 var i,j,k,s;258 259 if (mr_x1.length!=x.length) {260 mr_x1=dup(x);261 mr_r=dup(x);262 mr_a=dup(x);263 }264 265 copy_(mr_a,b);266 copy_(mr_r,x);267 copy_(mr_x1,x);268 269 addInt_(mr_r,-1);270 addInt_(mr_x1,-1);271 272 //s=the highest power of two that divides mr_r273 k=0;274 for (i=0;i<mr_r.length;i++)275 for (j=1;j<mask;j<<=1)276 if (x[i] & j) {277 s=(k<mr_r.length+bpe ? k : 0);278 i=mr_r.length;279 j=mask;280 } else281 k++;282 283 if (s)284 rightShift_(mr_r,s);285 286 powMod_(mr_a,mr_r,x);287 288 if (!equalsInt(mr_a,1) && !equals(mr_a,mr_x1)) {289 j=1;290 while (j<=s-1 && !equals(mr_a,mr_x1)) {291 squareMod_(mr_a,x);292 if (equalsInt(mr_a,1)) {293 return 0;294 }295 j++;296 }297 if (!equals(mr_a,mr_x1)) {298 return 0;299 }300 }301 return 1;302 }303 304 //returns how many bits long the bigInt is, not counting leading zeros.305 function bitSize(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 109 //return a copy of x with at least n elements, adding leading zeros if needed 314 110 function expand(x,n) { … … 317 113 return ans; 318 114 } 319 320 //return a k-bit true random prime using Maurer's algorithm.321 function randTruePrime(k) {322 var ans=int2bigInt(0,k,0);323 randTruePrime_(ans,k);324 return trim(ans,1);325 }326 327 //return a k-bit random probable prime with probability of error < 2^-80328 function randProbPrime(k) {329 if (k>=600) return randProbPrimeRounds(k,2); //numbers from HAC table 4.3330 if (k>=550) return randProbPrimeRounds(k,4);331 if (k>=500) return randProbPrimeRounds(k,5);332 if (k>=400) return randProbPrimeRounds(k,6);333 if (k>=350) return randProbPrimeRounds(k,7);334 if (k>=300) return randProbPrimeRounds(k,9);335 if (k>=250) return randProbPrimeRounds(k,12); //numbers from HAC table 4.4336 if (k>=200) return randProbPrimeRounds(k,15);337 if (k>=150) return randProbPrimeRounds(k,18);338 if (k>=100) return randProbPrimeRounds(k,27);339 return randProbPrimeRounds(k,40); //number from HAC remark 4.26 (only an estimate)340 }341 342 //return a k-bit probable random prime using n rounds of Miller Rabin (after trial division with small primes)343 function randProbPrimeRounds(k,n) {344 var ans, i, divisible, B;345 B=30000; //B is largest prime to use in trial division346 ans=int2bigInt(0,k,0);347 348 //optimization: try larger and smaller B to find the best limit.349 350 if (primes.length==0)351 primes=findPrimes(30000); //check for divisibility by primes <=30000352 353 if (rpprb.length!=ans.length)354 rpprb=dup(ans);355 356 for (;;) { //keep trying random values for ans until one appears to be prime357 //optimization: pick a random number times L=2*3*5*...*p, plus a358 // random element of the list of all numbers in [0,L) not divisible by any prime up to p.359 // This can reduce the amount of random number generation.360 361 randBigInt_(ans,k,0); //ans = a random odd number to check362 ans[0] |= 1;363 divisible=0;364 365 //check ans for divisibility by small primes up to B366 for (i=0; (i<primes.length) && (primes[i]<=B); i++)367 if (modInt(ans,primes[i])==0 && !equalsInt(ans,primes[i])) {368 divisible=1;369 break;370 }371 372 //optimization: change millerRabin so the base can be bigger than the number being checked, then eliminate the while here.373 374 //do n rounds of Miller Rabin, with random bases less than ans375 for (i=0; i<n && !divisible; i++) {376 randBigInt_(rpprb,k,0);377 while(!greater(ans,rpprb)) //pick a random rpprb that's < ans378 randBigInt_(rpprb,k,0);379 if (!millerRabin(ans,rpprb))380 divisible=1;381 }382 383 if(!divisible)384 return ans;385 }386 }387 388 //return a new bigInt equal to (x mod n) for bigInts x and n.389 function mod(x,n) {390 var ans=dup(x);391 mod_(ans,n);392 return trim(ans,1);393 }394 395 //return (x+n) where x is a bigInt and n is an integer.396 function addInt(x,n) {397 var ans=expand(x,x.length+1);398 addInt_(ans,n);399 return trim(ans,1);400 }401 402 //return x*y for bigInts x and y. This is faster when y<x.403 function mult(x,y) {404 var ans=expand(x,x.length+y.length);405 mult_(ans,y);406 return trim(ans,1);407 }408 409 115 //return (x**y mod n) where x,y,n are bigInts and ** is exponentiation. 0**0=1. Faster for odd n. 410 116 function powMod(x,y,n) { 411 117 var ans=expand(x,n.length); 412 powMod_(ans, trim(y,2),trim(n,2),0); //this should work without the trim, but doesn't413 return trim(ans,1);118 powMod_(ans,bigintTrim(y,2),bigintTrim(n,2),0); //this should work without the bigintTrim, but doesn't 119 return bigintTrim(ans,1); 414 120 } 415 121 … … 418 124 var ans=expand(x,(x.length>y.length ? x.length+1 : y.length+1)); 419 125 sub_(ans,y); 420 return trim(ans,1);126 return bigintTrim(ans,1); 421 127 } 422 128 … … 425 131 var ans=expand(x,(x.length>y.length ? x.length+1 : y.length+1)); 426 132 add_(ans,y); 427 return trim(ans,1); 428 } 429 430 //return (x**(-1) mod n) for bigInts x and n. If no inverse exists, it returns null 431 function inverseMod(x,n) { 432 var ans=expand(x,n.length); 433 var s; 434 s=inverseMod_(ans,n); 435 return s ? trim(ans,1) : null; 436 } 437 438 //return (x*y mod n) for bigInts x,y,n. For greater speed, let y<x. 439 function multMod(x,y,n) { 440 var ans=expand(x,n.length); 441 multMod_(ans,y,n); 442 return trim(ans,1); 443 } 444 445 //generate a k-bit true random prime using Maurer's algorithm, 446 //and put it into ans. The bigInt ans must be large enough to hold it. 447 function randTruePrime_(ans,k) { 448 var c,m,pm,dd,j,r,B,divisible,z,zz,recSize; 449 450 if (primes.length==0) 451 primes=findPrimes(30000); //check for divisibility by primes <=30000 452 453 if (pows.length==0) { 454 pows=new Array(512); 455 for (j=0;j<512;j++) { 456 pows[j]=Math.pow(2,j/511.-1.); 457 } 458 } 459 460 //c and m should be tuned for a particular machine and value of k, to maximize speed 461 c=0.1; //c=0.1 in HAC 462 m=20; //generate this k-bit number by first recursively generating a number that has between k/2 and k-m bits 463 recLimit=20; //stop recursion when k <=recLimit. Must have recLimit >= 2 464 465 if (s_i2.length!=ans.length) { 466 s_i2=dup(ans); 467 s_R =dup(ans); 468 s_n1=dup(ans); 469 s_r2=dup(ans); 470 s_d =dup(ans); 471 s_x1=dup(ans); 472 s_x2=dup(ans); 473 s_b =dup(ans); 474 s_n =dup(ans); 475 s_i =dup(ans); 476 s_rm=dup(ans); 477 s_q =dup(ans); 478 s_a =dup(ans); 479 s_aa=dup(ans); 480 } 481 482 if (k <= recLimit) { //generate small random primes by trial division up to its square root 483 pm=(1<<((k+2)>>1))-1; //pm is binary number with all ones, just over sqrt(2^k) 484 copyInt_(ans,0); 485 for (dd=1;dd;) { 486 dd=0; 487 ans[0]= 1 | (1<<(k-1)) | Math.floor(Math.random()*(1<<k)); //random, k-bit, odd integer, with msb 1 488 for (j=1;(j<primes.length) && ((primes[j]&pm)==primes[j]);j++) { //trial division by all primes 3...sqrt(2^k) 489 if (0==(ans[0]%primes[j])) { 490 dd=1; 491 break; 492 } 493 } 494 } 495 carry_(ans); 496 return; 497 } 498 499 B=c*k*k; //try small primes up to B (or all the primes[] array if the largest is less than B). 500 if (k>2*m) //generate this k-bit number by first recursively generating a number that has between k/2 and k-m bits 501 for (r=1; k-k*r<=m; ) 502 r=pows[Math.floor(Math.random()*512)]; //r=Math.pow(2,Math.random()-1); 503 else 504 r=.5; 505 506 //simulation suggests the more complex algorithm using r=.333 is only slightly faster. 507 508 recSize=Math.floor(r*k)+1; 509 510 randTruePrime_(s_q,recSize); 511 copyInt_(s_i2,0); 512 s_i2[Math.floor((k-2)/bpe)] |= (1<<((k-2)%bpe)); //s_i2=2^(k-2) 513 divide_(s_i2,s_q,s_i,s_rm); //s_i=floor((2^(k-1))/(2q)) 514 515 z=bitSize(s_i); 516 517 for (;;) { 518 for (;;) { //generate z-bit numbers until one falls in the range [0,s_i-1] 519 randBigInt_(s_R,z,0); 520 if (greater(s_i,s_R)) 521 break; 522 } //now s_R is in the range [0,s_i-1] 523 addInt_(s_R,1); //now s_R is in the range [1,s_i] 524 add_(s_R,s_i); //now s_R is in the range [s_i+1,2*s_i] 525 526 copy_(s_n,s_q); 527 mult_(s_n,s_R); 528 multInt_(s_n,2); 529 addInt_(s_n,1); //s_n=2*s_R*s_q+1 530 531 copy_(s_r2,s_R); 532 multInt_(s_r2,2); //s_r2=2*s_R 533 534 //check s_n for divisibility by small primes up to B 535 for (divisible=0,j=0; (j<primes.length) && (primes[j]<B); j++) 536 if (modInt(s_n,primes[j])==0 && !equalsInt(s_n,primes[j])) { 537 divisible=1; 538 break; 539 } 540 541 if (!divisible) //if it passes small primes check, then try a single Miller-Rabin base 2 542 if (!millerRabinInt(s_n,2)) //this line represents 75% of the total runtime for randTruePrime_ 543 divisible=1; 544 545 if (!divisible) { //if it passes that test, continue checking s_n 546 addInt_(s_n,-3); 547 for (j=s_n.length-1;(s_n[j]==0) && (j>0); j--); //strip leading zeros 548 for (zz=0,w=s_n[j]; w; (w>>=1),zz++); 549 zz+=bpe*j; //zz=number of bits in s_n, ignoring leading zeros 550 for (;;) { //generate z-bit numbers until one falls in the range [0,s_n-1] 551 randBigInt_(s_a,zz,0); 552 if (greater(s_n,s_a)) 553 break; 554 } //now s_a is in the range [0,s_n-1] 555 addInt_(s_n,3); //now s_a is in the range [0,s_n-4] 556 addInt_(s_a,2); //now s_a is in the range [2,s_n-2] 557 copy_(s_b,s_a); 558 copy_(s_n1,s_n); 559 addInt_(s_n1,-1); 560 powMod_(s_b,s_n1,s_n); //s_b=s_a^(s_n-1) modulo s_n 561 addInt_(s_b,-1); 562 if (isZero(s_b)) { 563 copy_(s_b,s_a); 564 powMod_(s_b,s_r2,s_n); 565 addInt_(s_b,-1); 566 copy_(s_aa,s_n); 567 copy_(s_d,s_b); 568 GCD_(s_d,s_n); //if s_b and s_n are relatively prime, then s_n is a prime 569 if (equalsInt(s_d,1)) { 570 copy_(ans,s_aa); 571 return; //if we've made it this far, then s_n is absolutely guaranteed to be prime 572 } 573 } 574 } 575 } 576 } 577 578 //Return an n-bit random BigInt (n>=1). If s=1, then the most significant of those n bits is set to 1. 579 function randBigInt(n,s) { 580 var a,b; 581 a=Math.floor((n-1)/bpe)+2; //# array elements to hold the BigInt with a leading 0 element 582 b=int2bigInt(0,0,a); 583 randBigInt_(b,n,s); 584 return b; 585 } 586 587 //Set b to an n-bit random BigInt. If s=1, then the most significant of those n bits is set to 1. 588 //Array b must be big enough to hold the result. Must have n>=1 589 function randBigInt_(b,n,s) { 590 var i,a; 591 for (i=0;i<b.length;i++) 592 b[i]=0; 593 a=Math.floor((n-1)/bpe)+1; //# array elements to hold the BigInt 594 for (i=0;i<a;i++) { 595 b[i]=Math.floor(Math.random()*(1<<(bpe-1))); 596 } 597 b[a-1] &= (2<<((n-1)%bpe))-1; 598 if (s==1) 599 b[a-1] |= (1<<((n-1)%bpe)); 600 } 601 133 return bigintTrim(ans,1); 134 } 602 135 //Return the greatest common divisor of bigInts x and y (each with same number of elements). 603 136 function GCD(x,y) { … … 658 191 x[0]%=y[0]; 659 192 t=x[0]; x[0]=y[0]; y[0]=t; 660 }661 }662 663 //do x=x**(-1) mod n, for bigInts x and n.664 //If no inverse exists, it sets x to zero and returns 0, else it returns 1.665 //The x array must be at least as large as the n array.666 function inverseMod_(x,n) {667 var k=1+2*Math.max(x.length,n.length);668 669 if(!(x[0]&1) && !(n[0]&1)) { //if both inputs are even, then inverse doesn't exist670 copyInt_(x,0);671 return 0;672 }673 674 if (eg_u.length!=k) {675 eg_u=new Array(k);676 eg_v=new Array(k);677 eg_A=new Array(k);678 eg_B=new Array(k);679 eg_C=new Array(k);680 eg_D=new Array(k);681 }682 683 copy_(eg_u,x);684 copy_(eg_v,n);685 copyInt_(eg_A,1);686 copyInt_(eg_B,0);687 copyInt_(eg_C,0);688 copyInt_(eg_D,1);689 for (;;) {690 while(!(eg_u[0]&1)) { //while eg_u is even691 halve_(eg_u);692 if (!(eg_A[0]&1) && !(eg_B[0]&1)) { //if eg_A==eg_B==0 mod 2693 halve_(eg_A);694 halve_(eg_B);695 } else {696 add_(eg_A,n); halve_(eg_A);697 sub_(eg_B,x); halve_(eg_B);698 }699 }700 701 while (!(eg_v[0]&1)) { //while eg_v is even702 halve_(eg_v);703 if (!(eg_C[0]&1) && !(eg_D[0]&1)) { //if eg_C==eg_D==0 mod 2704 halve_(eg_C);705 halve_(eg_D);706 } else {707 add_(eg_C,n); halve_(eg_C);708 sub_(eg_D,x); halve_(eg_D);709 }710 }711 712 if (!greater(eg_v,eg_u)) { //eg_v <= eg_u713 sub_(eg_u,eg_v);714 sub_(eg_A,eg_C);715 sub_(eg_B,eg_D);716 } else { //eg_v > eg_u717 sub_(eg_v,eg_u);718 sub_(eg_C,eg_A);719 sub_(eg_D,eg_B);720 }721 722 if (equalsInt(eg_u,0)) {723 if (negative(eg_C)) //make sure answer is nonnegative724 add_(eg_C,n);725 copy_(x,eg_C);726 727 if (!equalsInt(eg_v,1)) { //if GCD_(x,n)!=1, then there is no inverse728 copyInt_(x,0);729 return 0;730 }731 return 1;732 }733 193 } 734 194 } … … 1385 845 1386 846 //return x with exactly k leading zero elements 1387 function trim(x,k) {847 function bigintTrim(x,k) { 1388 848 var i,y; 1389 849 for (i=x.length; i>0 && !x[i-1]; i--); -
trunk/phpgwapi/templates/default/head.inc.php
r2628 r2931 28 28 . "<![endif]-->\n"; 29 29 30 $GLOBALS[ 'phpgw' ] -> js -> validate_file( ' jscode',30 $GLOBALS[ 'phpgw' ] -> js -> validate_file( 'templatejs', 31 31 ( ( ! $GLOBALS['phpgw_info']['user']['preferences']['common']['disable_slider_effects'] ) ? 'slidereffects' : 'simple_show_hide' ), 32 32 'phpgwapi/templates/' . $GLOBALS[ 'phpgw_info' ][ 'server' ][ 'template_set' ], true );
Note: See TracChangeset
for help on using the changeset viewer.