JavaScript is an interpreted language which was designed by Netscape for use in web documents. JavaScript programs can be run by both Netscape and Internet Explorer web browsers. The JavaScript language is now standardized as ECMAScript.
These programs are written twice in this document. In each section there is a copy of the program which can be read. The copy which is executed is contained in a block at the very beginning of the document which is not visible in the browser window. To modify a program you will need to open this document in an editor, change the definition at the top of the document, reload the document in your browser and rerun the program.
JavaScript seems to support the use of integers up to 64 bits in size, so the largest number which can be used in most of these algorithms is about 4000000000. (Some care should be used though, as I have seen JavaScript documentation which indicates that its integer size is 32 bits.
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(5 * 4) % 13Math.floor(7 / 2)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;
}
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;
}
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;
}
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;
}
The following program implements the Pollard's p-1 algorithm for integer factorization:
function factorpm1(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;
}
The following program implements Pollard's Rho algorithm for integer factorization:
function factorrho(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;
}
JavaScript does not have any built-in multiple precision capabilities but there are several small mp libraries for it.
http://www.davesucks.com/rsa/BigInt.js]
http://www.math.fau.edu/Richman/long.htm]