GCD, Prime, Exponentiation, Factoring Javascript

Contents

1. General
2. Basic Operations
3. GCD
4. Exponentiation - PowMod
5. Factoring - Pollard p-1
6. Factoring - Pollard Rho
7. Multiple Precision

---

General

JavaScript is an interpreted language which was originally designed by Netscape for use in web documents. JavaScript programs can be run by any modern web browser (and a number of other programs). The JavaScript language is now standardized as ECMAScript.
While JavaScript was never written with number theory (or any other mathematics) in mind, it has the necessary operators and structure for this sort of programming. Modern JavaScript/ECMAScript implementations supports the use of integers up to 53 bits in length, which gives a maximum integer size of slightly larger than 9,000,000,000,000,000. As the algorithms implemented here usually multiply or square before modular reduction, the largest practical modulus is 26 bits, or about 67,000,000. (The JavaScript/ECMAScript Number type is implemented using the double precision type as specified in IEEE-754.)
For each algorithm there is a form where you can type in values and try it out and there is a listing of the program. The copy of the program which is actually executed is in the file NumbThy.js. If you want to modify a program you will need to download both that program file and this page, edit the program file, then load the local copy of this page in your browser.

Basic Operations

The basic arithmetic operations, +, -, /, are available from the keyboard. Note that the division operator normally returns a floating point number (eg 7/2 returns 3.5) so the answer should be truncated with the Math.floor function (eg Math.floor(7/2) returns 3). The modular reduction operator is represented by %.
Examples:

• (8 + 7) % 13
  (returns an answer of 2)
• (5 * 4) % 13
  (returns an answer of 7)
• Math.floor(7 / 2)
  (returns an answer of 3)

The following two subroutines demonstrate both simple programming in JavaScript and how you can use an HTML form to run a JavaScript program.

      function addMod(a,b,n)
      {
      sum = (a + b) % n;
      if (sum < 0) {sum += n;};
      return sum;
      }

      function multMod(a,b,n)
      {
      prod = (a * b) % n;
      if (prod < 0) {prod += n;};
      return prod;
      }

+ (mod ) =
* (mod ) =

GCD

The Euclidean Algorithm to compute an integer gcd can be implemented with the following program:

      function gcd(a,b)
      {
      var temp;
      if(a < 0) {a = -a;};
      if(b < 0) {b = -b;};
      if(b > a) {temp = a; a = b; b = temp;};
      while (true) {
         a %= b;
         if(a == 0) {return b;};
         b %= a;
         if(b == 0) {return a;};
      };
      return b;
      }

gcd(, ) =

The following program implements the extended Euclidean algorithm:

      function xgcd(a,b)
      {
      var quot, a1=1, b1=0, a2=0, b2=1, aneg=1, bneg=1, result=new Array;
      if(a < 0) {a = -a; aneg=-1;};
      if(b < 0) {b = -b; bneg=-1;};
      if(b > a) {temp = a; a = b; b = temp;};
      while (true) {
      	 quot = -Math.floor(a / b);
         a %= b;
         a1 += quot*a2; b1 += quot*b2;
         if(a == 0) {result[0]=b*bneg; result[1]=a2; result[2]=b2; return result;};
         quot = -Math.floor(b / a);
         b %= a;
         a2 += quot*a1; b2 += quot*b1;
        if(b == 0) {result[0]=a*aneg; result[1]=a1; result[2]=b1; return result;};
      };
      return result;
      }

gcd(, ) = (, , )

Exponentiation - PowMod

The following program implements the Russian Peasant algorithm for computing modular exponentiation:

      function powmod(base,exp,modulus)
      {
      var accum=1, i=0, basepow2=base;
      while ((exp>>i)>0) {
      	 if(((exp>>i) & 1) == 1){accum = (accum*basepow2) % modulus;};
      	 basepow2 = (basepow2*basepow2) % modulus;
         i++;
      };
      return accum;
      }

^ (mod ) =

Factoring - Pollard p-1

The following program implements the Pollard's p-1 algorithm for integer factorization:

      function factor_pm1(numb)
      {
      var bound=Math.floor(Math.exp(Math.log(numb)/3)), i=2, thegcd, base=2;
      for (i=2; i<bound; i++) {
      	 base = powmod(base,i,numb);
         if((thegcd=gcd(base-1,numb)) != 1) {return thegcd;};
      };
      return 1;
      }

Factor ... to get a factor of

Factoring - Pollard Rho

The following program implements Pollard's Rho algorithm for integer factorization:

      function factor_rho(numb)
      {
      var numsteps=2*Math.floor(Math.sqrt(Math.sqrt(numb))), slow=2, fast=slow, i;
      for (i=1; i<numsteps; i++){
         slow = (slow*slow + 1) % numb;
         fast = (fast*fast + 1) % numb;
         fast = (fast*fast + 1) % numb;
         if((thegcd=gcd(fast-slow,numb)) != 1) {return thegcd;};
      };
      return 1;
      }

Factor ... to get a factor of

Multiple Precision

JavaScript does not have any built-in multiple precision capabilities but there are several small mp libraries for it.

• RSA code w/ MP library by David Shapiro [http://ohdave.com/rsa/BigInt.js]
• Various Number Theory and Cryptography scripts by Fred Richman (Florida Atlantic Univ) [http://www.math.fau.edu/Richman/jscripts.htm] 

Source : http://userpages.umbc.edu/~rcampbel/NumbThy/Class/Programming/JavaScript/#Basic