Changeset 2931 for trunk/phpgwapi


Ignore:
Timestamp:
06/16/10 13:48:27 (14 years ago)
Author:
amuller
Message:

Ticket #1036 - Adicionando ponto e vírgula faltante e mudando nomes

Location:
trunk/phpgwapi
Files:
3 edited
1 moved

Legend:

Unmodified
Added
Removed
  • trunk/phpgwapi/inc/class.common.inc.php

    r2903 r2931  
    419419                                        $GLOBALS[ 'phpgw' ] -> js -> validate_file( 'tools','xevent', NULL, true ); 
    420420                                        $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'] ); 
    422422 
    423423                                        $this -> phpgw_header( $module_content ); 
  • trunk/phpgwapi/js/expressoAjax/bigInt.js

    r2847 r2931  
    6868// Those returning boolean or int will not allocate memory except possibly on the first  
    6969// 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 
    17871 
    17972//globals 
     
    214107rpprb=t; //used in randProbPrimeRounds() (which also uses "primes") 
    215108 
    216 //////////////////////////////////////////////////////////////////////////////////////// 
    217  
    218  
    219 //return array of all primes less than integer n 
    220 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 sieve 
    227   for(;s[p]<n;) {                  //s[p] is the pth prime 
    228     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<x 
    243 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<x 
    256 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_r 
    273   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       } else 
    281         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  
    313109//return a copy of x with at least n elements, adding leading zeros if needed 
    314110function expand(x,n) { 
     
    317113  return ans; 
    318114} 
    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^-80 
    328 function randProbPrime(k) { 
    329   if (k>=600) return randProbPrimeRounds(k,2); //numbers from HAC table 4.3 
    330   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.4 
    336   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 division 
    346   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 <=30000 
    352  
    353   if (rpprb.length!=ans.length) 
    354     rpprb=dup(ans); 
    355  
    356   for (;;) { //keep trying random values for ans until one appears to be prime 
    357     //optimization: pick a random number times L=2*3*5*...*p, plus a  
    358     //   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 check 
    362     ans[0] |= 1;  
    363     divisible=0; 
    364    
    365     //check ans for divisibility by small primes up to B 
    366     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 ans 
    375     for (i=0; i<n && !divisible; i++) { 
    376       randBigInt_(rpprb,k,0); 
    377       while(!greater(ans,rpprb)) //pick a random rpprb that's < ans 
    378         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  
    409115//return (x**y mod n) where x,y,n are bigInts and ** is exponentiation.  0**0=1. Faster for odd n. 
    410116function powMod(x,y,n) { 
    411117  var ans=expand(x,n.length);   
    412   powMod_(ans,trim(y,2),trim(n,2),0);  //this should work without the trim, but doesn't 
    413   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); 
    414120} 
    415121 
     
    418124  var ans=expand(x,(x.length>y.length ? x.length+1 : y.length+1));  
    419125  sub_(ans,y); 
    420   return trim(ans,1); 
     126  return bigintTrim(ans,1); 
    421127} 
    422128 
     
    425131  var ans=expand(x,(x.length>y.length ? x.length+1 : y.length+1));  
    426132  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} 
    602135//Return the greatest common divisor of bigInts x and y (each with same number of elements). 
    603136function GCD(x,y) { 
     
    658191    x[0]%=y[0]; 
    659192    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 exist 
    670     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 even 
    691       halve_(eg_u); 
    692       if (!(eg_A[0]&1) && !(eg_B[0]&1)) { //if eg_A==eg_B==0 mod 2 
    693         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 even 
    702       halve_(eg_v); 
    703       if (!(eg_C[0]&1) && !(eg_D[0]&1)) { //if eg_C==eg_D==0 mod 2 
    704         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_u 
    713       sub_(eg_u,eg_v); 
    714       sub_(eg_A,eg_C); 
    715       sub_(eg_B,eg_D); 
    716     } else {                   //eg_v > eg_u 
    717       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 nonnegative 
    724         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 inverse 
    728         copyInt_(x,0); 
    729         return 0; 
    730       } 
    731       return 1; 
    732     } 
    733193  } 
    734194} 
     
    1385845 
    1386846//return x with exactly k leading zero elements 
    1387 function trim(x,k) { 
     847function bigintTrim(x,k) { 
    1388848  var i,y; 
    1389849  for (i=x.length; i>0 && !x[i-1]; i--); 
  • trunk/phpgwapi/templates/default/head.inc.php

    r2628 r2931  
    2828                        . "<![endif]-->\n"; 
    2929 
    30         $GLOBALS[ 'phpgw' ] -> js -> validate_file( 'jscode', 
     30        $GLOBALS[ 'phpgw' ] -> js -> validate_file( 'templatejs', 
    3131                ( ( ! $GLOBALS['phpgw_info']['user']['preferences']['common']['disable_slider_effects'] ) ? 'slidereffects' : 'simple_show_hide' ), 
    3232                'phpgwapi/templates/' . $GLOBALS[ 'phpgw_info' ][ 'server' ][ 'template_set' ], true ); 
Note: See TracChangeset for help on using the changeset viewer.