Skip to content

Instantly share code, notes, and snippets.

@Element118

Element118/primefinding.html

Created April 2, 2017 09:55
Show Gist options
  • Save Element118/e9b7e32d5308b0eb332826e1874ba7e9 to your computer and use it in GitHub Desktop.
Save Element118/e9b7e32d5308b0eb332826e1874ba7e9 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
primefinding.html
<!DOCTYPE html>
<html>
<head>
<title>Prime Checking</title>
<script>
/**
* BigInteger
* Uses 32768's complement
*
* Why 32768?
* It is a power of 2 (2^15), and when multiplied by itself, it is less than 2^31-1.
*
* Guarantee: At least 1 digit
* Begin with 32767: negative
* Begin with 0: positive
*
* If a function is used in this class, be careful and remember to clone your object before running itself as a parameter. This is not guaranteed yet!
*
* Finds primes in about at most 1 minute
*/
var new_ = Object.constructor("cls", "args",
"args = Array.prototype.slice.call(args);\n" +
"args.unshift(undefined);\n" +
"var obj = new (Function.prototype.bind.apply(cls, args))();\n" +
"obj.constructor = cls;\n" +
"return obj;"
);
var BigInteger = function(digits) {
if (!this instanceof BigInteger) {
return new_(BigInteger, [digits]);
}
if (typeof digits === "number") {
this.digits = [];
digits = Math.floor(digits);
if (digits<0) {
digits = -digits;
while (digits) {
this.digits.push(digits % 32768);
digits = Math.floor(digits / 32768); // in case it is not integer
}
this.digits.push(0);
this.negate();
} else {
while (digits) {
this.digits.push(digits % 32768);
digits = Math.floor(digits / 32768); // in case it is not integer
}
this.digits.push(0);
}
this.simplify();
} else if (typeof digits === "string") {
if (digits.startsWith("0x")) {
this.digits = [];
var hash = {
0: 0, 1: 1, 2: 2, 3: 3,
4: 4, 5: 5, 6: 6, 7: 7,
8: 8, 9: 9, A: 10, B: 11,
C: 12, D: 13, E: 14, F: 15
};
var bits = 0;
var numBits = 0;
for (var i=digits.length-1;i>=2;i--) {
bits += hash[digits[i]]<<numBits;
numBits += 4;
if (numBits>=15) {
this.digits.push(bits % 32768);
bits >>= 15;
numBits -= 15;
}
}
if (digits[2] === "F") { // negative
while (this.digits[this.digits.length-1] !== 32767) {
while (numBits<15) {
bits += 15<<numBits;
numBits += 4;
}
this.digits.push(bits % 32768);
bits >>= 15;
numBits -= 15;
}
} else { // positive
while (this.digits[this.digits.length-1] !== 0) {
while (numBits<15) {
numBits += 4;
}
this.digits.push(bits % 32768);
bits >>= 15;
numBits -= 15;
}
}
} else {
var negate = false;
this.digits = [0]; // start with 0
if (digits[0] === "-") {
negate = true;
digits = digits.substring(1);
}
if (digits.length < 8) {
for (var i=0;i<digits.length;i++) {
this.multiplySmall(10);
this.addSmall(+digits[i]);
}
} else {
var basePowers = [new_(BigInteger, [[10, 0]])]; // TODO: Precompute
while ((1<<basePowers.length)<=digits.length) {
basePowers.push(basePowers[basePowers.length-1].getProductFast(basePowers[basePowers.length-1]));
}
var subResult = {};
for (var i=1;i<=digits.length;i++) {
var p = i&-i;
subResult[p] = new_(BigInteger, [[+digits[digits.length-i], 0]]);
for (var j=0;(1<<j)<p;j++) {
subResult[p] = subResult[p].getProductFast(basePowers[j]);
subResult[p].add(subResult[1<<j]); subResult[1<<j] = null;
}
}
for (var i=0;(1<<i)<=digits.length;i++) {
if (subResult[1<<i]) {
this.digits = this.getProductFast(basePowers[i]).digits;
this.add(subResult[1<<i]);
}
}
}
if (negate) {
this.negate();
}
}
} else {
this.digits = digits.slice(0) || [0];
}
};
BigInteger.ONE = new_(BigInteger, [[1, 0]]);
BigInteger.ZERO = new_(BigInteger, [[0, 0]]);
BigInteger.prototype.clone = function() {
return new_(BigInteger, [this.digits]);
};
BigInteger.prototype.extend = function(length) {
var sign = this.digits[this.digits.length-1];
while (this.digits.length < length) {
this.digits.push(sign);
}
};
BigInteger.prototype.simplify = function() {
while (this.digits.length >= 2 && this.digits[this.digits.length-1] === this.digits[this.digits.length-2]) {
this.digits.pop();
}
};
BigInteger.prototype.plusOne = function() {
this.digits.push(this.digits[this.digits.length-1]);
var i = 0;
while (i<this.digits.length) {
this.digits[i]++;
if (this.digits[i]>=32768) {
this.digits[i] = 0;
i++;
} else { break; }
}
this.simplify();
};
BigInteger.prototype.getPlusOne = function() {
var newBigInt = new_(BigInteger, [this.digits]);
newBigInt.plusOne();
return newBigInt;
};
BigInteger.prototype.negate = function() {
var i = this.digits.length;
while (i--) {
this.digits[i] = 32767-this.digits[i];
}
this.plusOne();
};
BigInteger.prototype.getNegation = function() {
var newBigInt = new_(BigInteger, [this.digits]);
newBigInt.negate();
return newBigInt;
};
BigInteger.prototype.toString = function() {
// let's use a base 16 string first
var baseConv = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F"];
var str = "";
var leftoverBits = 0;
var leftover = 0;
for (var i=0;i<this.digits.length;i++) {
leftover += this.digits[i]<<leftoverBits;
leftoverBits += 15;
while (leftoverBits >= 4) {
str = baseConv[leftover%16]+str;
leftover >>= 4;
leftoverBits -= 4;
}
}
return "0x"+str.replace(/^0+/, "0").replace(/^F+/, "F");
};
// Can run with self as argument.
BigInteger.prototype.equals = function(that) {
this.simplify();
that.simplify();
if (this === that) { return true; }
if (this.digits.length !== that.digits.length) {
return false;
}
var i = this.digits.length;
while (i--) {
if (this.digits[i] !== that.digits[i]) {
return false;
}
}
return true;
};
BigInteger.prototype.sign = function() {
this.simplify();
if (this.digits.length === 1 && this.digits[0] === 0) {
return 0;
} else if (this.digits[this.digits.length-1] === 0) {
return 1;
}
return -1;
};
BigInteger.prototype.abs = function() {
if (this.digits[this.digits.length-1]) {
this.negate();
}
};
BigInteger.prototype.getAbs = function() {
var newBigInt = new_(BigInteger, [this.digits]);
newBigInt.abs();
return newBigInt;
};
// Can run with self as argument.
BigInteger.prototype.add = function(that) {
var addAmt = that.digits.length, i = 0, carry = 0, sign = that.digits[that.digits.length-1];
this.extend(addAmt+2);
while (i<addAmt) {
this.digits[i] += carry + that.digits[i];
if (this.digits[i] > 32767) {
this.digits[i] -= 32768;
carry = 1;
} else {
carry = 0;
}
i++;
}
addAmt = this.digits.length;
if (carry && sign === 0) {
while (i<addAmt) {
if (++this.digits[i] === 32768) {
this.digits[i] = 0;
} else { break; }
i++;
}
} else if (!carry && sign === 32767) {
while (i<addAmt) {
if (--this.digits[i] < 0) {
this.digits[i] = 32767;
} else { break; }
i++;
}
}
this.simplify();
};
// Can run with self as argument.
BigInteger.prototype.getSum = function(that) {
var newBigInt = new_(BigInteger, [this.digits]);
newBigInt.add(that);
return newBigInt;
};
BigInteger.prototype.multiplyByPowerOf32768 = function(power) {
if (power) { // power >= 0
var i = this.digits.length+power;
this.extend(i);
while (i--) {
this.digits[i] = this.digits[i-power];
}
i = power;
while (i--) {
this.digits[i] = 0;
}
}
};
BigInteger.prototype.getMultiplyByPowerOf32768 = function(power) {
var newBigInt = new_(BigInteger, [this.digits]);
newBigInt.multiplyByPowerOf32768(power);
return newBigInt;
};
// Can run with self as argument
BigInteger.prototype.multiplyByPowerOf32768AndAddTo = function(that, power) {
var addAmt = that.digits.length+power, carry = 0, i = power, sign = that.digits[that.digits.length-1];
this.extend(addAmt+2);
while (i<addAmt) {
this.digits[i] += that.digits[i-power] + carry;
if (this.digits[i] > 32767) {
this.digits[i] -= 32768;
carry = 1;
} else {
carry = 0;
}
i++;
}
addAmt = this.digits.length;
if (carry && sign === 0) {
while (i<addAmt) {
if (++this.digits[i] === 32768) {
this.digits[i] = 0;
} else { break; }
i++;
}
} else if (!carry && sign === 32767) {
while (i<addAmt) {
if (--this.digits[i] < 0) {
this.digits[i] = 32767;
} else { break; }
i++;
}
}
this.simplify();
};
// Can run with self as argument.
BigInteger.prototype.subtract = function(that) {
this.add(that.getNegation());
};
// Can run with self as argument.
BigInteger.prototype.getDifference = function(that) {
var minusThat = that.getNegation();
minusThat.add(this);
return minusThat;
};
BigInteger.prototype.addSmall = function(number) {
this.digits.push(this.digits[this.digits.length-1]);
this.digits[0] += number;
if (this.digits[0] >= 32768) {
this.digits[0] -= 32768;
var i = 1;
while (i<this.digits.length) {
this.digits[i]++;
if (this.digits[i]>=32768) {
this.digits[i] = 0;
} else { break; }
}
}
this.simplify();
};
BigInteger.prototype.multiplySmall = function(number) {
var i = 1, positive = this.sign()>0;
this.abs();
var newLength = this.digits.length+2;
this.digits.push(this.digits[this.digits.length-1]);
this.digits.push(this.digits[this.digits.length-1]);
this.digits[0] *= number;
while (i < newLength) {
this.digits[i] *= number;
this.digits[i] += this.digits[i-1] >> 15;
this.digits[i-1] %= 32768;
i++;
}
if (!positive) {
this.negate();
}
};
// Can run with self as argument.
BigInteger.prototype.getProduct = function(that) {
var negative = (this.sign() === -that.sign());
var thisAbs = this.getAbs();
that = that.getAbs();
var i = thisAbs.digits.length+that.digits.length+2, j;
var result = Array(i);
while (i--) {
result[i] = 0;
}
i = thisAbs.digits.length;
while (i--) {
j = that.digits.length;
while (j--) {
result[i+j] += thisAbs.digits[i]*that.digits[j];
result[i+j+1] += result[i+j] >> 15;
result[i+j] %= 32768;
}
}
for (var i=0;i<result.length-1;i++) {
result[i+1] += result[i] >> 15;
result[i] %= 32768;
}
result = new_(BigInteger, [result]);
if (negative) { result.negate(); }
return result;
};
// Can run with self as argument.
BigInteger.prototype.getProductFast = function(that) {
// base case (chosen by experiment)
if (this.digits.length < 100 || that.digits.length < 100) {
return this.getProduct(that);
}
this.simplify(); that.simplify();
var negative = (this.sign() === -that.sign());
var thisAbs = this.getAbs();
that = that.getAbs();
if (thisAbs.digits.length*2 < that.digits.length) {
var temp = thisAbs;
thisAbs = that;
that = temp;
}
var result = BigInteger.ZERO.clone();
if (thisAbs.digits.length > 2*that.digits.length) {
var numberOfMults = Math.floor(thisAbs.digits.length/that.digits.length);
for (var i=0;i<thisAbs.digits.length;i+=that.digits.length) {
var arr = thisAbs.digits.slice(i, i+that.digits.length);
arr.push(0); // positive
result.multiplyByPowerOf32768AndAddTo(new_(BigInteger, [arr]).getProductFast(that), i);
}
} else { // comparable size
var cutPoint = Math.min(thisAbs.digits.length, that.digits.length)>>1;
var arr = thisAbs.digits.slice(0, cutPoint); arr.push(0);
var smallThis = new_(BigInteger, [arr]);
var bigThis = new_(BigInteger, [thisAbs.digits.slice(cutPoint)]);
arr = that.digits.slice(0, cutPoint); arr.push(0);
var smallThat = new_(BigInteger, [arr]);
var bigThat = new_(BigInteger, [that.digits.slice(cutPoint)]);
var smallProd = smallThis.getProductFast(smallThat);
var bigProd = bigThis.getProductFast(bigThat);
var intermediate = smallThis.getSum(bigThis).getProductFast(smallThat.getSum(bigThat));
intermediate.subtract(smallProd);
intermediate.subtract(bigProd);
result = smallProd;
result.multiplyByPowerOf32768AndAddTo(intermediate, cutPoint);
result.multiplyByPowerOf32768AndAddTo(bigProd, cutPoint*2);
}
if (negative) { result.negate(); }
return result;
};
// Can run with self as argument.
BigInteger.prototype.less = function(that) {
this.simplify();
that.simplify();
if (this.sign() !== that.sign()) {
return this.sign() < that.sign();
} else if (this.equals(that)) {
return false;
} else if (this.digits.length !== that.digits.length) {
return (this.digits.length<that.digits.length) === (this.sign() === 1);
}
var i = this.digits.length;
while (i--) {
if (this.digits[i] !== that.digits[i]) {
return this.digits[i] < that.digits[i];
}
}
return false;
};
// Can run with self as argument.
BigInteger.prototype.lessEqual = function(that) {
this.simplify();
that.simplify();
if (this.sign() !== that.sign()) {
return this.sign() < that.sign();
} else if (this.equals(that)) {
return true;
} else if (this.digits.length !== that.digits.length) {
return (this.digits.length<that.digits.length) === (this.sign() === 1);
}
var i = this.digits.length;
while (i--) {
if (this.digits[i] !== that.digits[i]) {
return this.digits[i] < that.digits[i];
}
}
return false;
};
// Can run with self as argument.
BigInteger.prototype.divide = function(that) {
var result = new_(BigInteger, ["0"]);
if (that.equals(BigInteger.ZERO)) { return null; }
var negative = false;
if (this.sign() === -that.sign()) {
negative = true;
}
var thisAbs = this.getAbs(), that = that.getAbs();
var multiples = { 0: new_(BigInteger, ["0"]) };
var largestPower = 0;
var multipleLength = that.digits.length+2;
while (that.getMultiplyByPowerOf32768(largestPower).lessEqual(thisAbs)) {
largestPower++;
}
var minTimes, maxTimes, mid, j;
while (largestPower--) {
minTimes = 0; maxTimes = 32767;
while (minTimes < maxTimes) {
mid = (minTimes+maxTimes+1)>>1;
if (!multiples[mid]) {
multiples[mid] = that.clone();
multiples[mid].extend(multipleLength);
j = 0;
while (j < multipleLength) {
multiples[mid].digits[j] *= mid;
if (j) {
multiples[mid].digits[j] += multiples[mid].digits[j-1] >> 15;
multiples[mid].digits[j-1] %= 32768;
}
j++;
}
}
var cmpre = multiples[mid].getMultiplyByPowerOf32768(largestPower);
if (cmpre.less(thisAbs)) {
minTimes = mid;
} else if (thisAbs.less(cmpre)) {
maxTimes = mid-1;
} else {
minTimes = maxTimes = mid;
}
}
if (minTimes === 0) {
continue;
}
thisAbs.subtract(multiples[minTimes].getMultiplyByPowerOf32768(largestPower));
result.multiplyByPowerOf32768AndAddTo(new_(BigInteger, [minTimes]), largestPower);
}
if (negative) {
result.negate();
thisAbs.negate();
}
return {
quotient: result,
remainder: thisAbs
};
};
BigInteger.prototype.getQuotient = function(that) {
var result = new_(BigInteger, ["0"]);
if (that.equals(BigInteger.ZERO)) { return null; }
var negative = false;
if (this.sign() === -that.sign()) {
negative = true;
}
var thisAbs = this.getAbs();
that = that.getAbs();
var multiples = { 0: new_(BigInteger, ["0"]) };
var largestPower = 0;
var multipleLength = that.digits.length+2;
while (that.getMultiplyByPowerOf32768(largestPower).lessEqual(thisAbs)) {
largestPower++;
}
var minTimes, maxTimes, mid, j;
while (largestPower--) {
minTimes = 0; maxTimes = 32767;
while (minTimes < maxTimes) {
mid = (minTimes+maxTimes+1)>>1;
if (!multiples[mid]) {
multiples[mid] = that.clone();
multiples[mid].extend(multipleLength);
j = 0;
while (j < multipleLength) {
multiples[mid].digits[j] *= mid;
if (j) {
multiples[mid].digits[j] += multiples[mid].digits[j-1] >> 15;
multiples[mid].digits[j-1] %= 32768;
}
j++;
}
}
var cmpre = multiples[mid].getMultiplyByPowerOf32768(largestPower);
if (cmpre.less(thisAbs)) {
minTimes = mid;
} else if (thisAbs.less(cmpre)) {
maxTimes = mid-1;
} else {
minTimes = maxTimes = mid;
}
}
if (minTimes === 0) {
continue;
}
thisAbs.subtract(multiples[minTimes].getMultiplyByPowerOf32768(largestPower));
result.multiplyByPowerOf32768AndAddTo(new_(BigInteger, [minTimes]), largestPower);
}
if (negative) {
result.negate();
}
return result;
};
BigInteger.prototype.getMod = function(that) {
if (that.equals(BigInteger.ZERO)) { return null; }
var negative = false;
if (this.sign() === -1) {
negative = true;
}
var thisAbs = this.getAbs(), that = that.getAbs();
var multiples = { 0: new_(BigInteger, ["0"]) };
var largestPower = 0;
var multipleLength = that.digits.length+2;
while (that.getMultiplyByPowerOf32768(largestPower).lessEqual(thisAbs)) {
largestPower++;
}
var minTimes, maxTimes, mid, j;
while (largestPower--) {
minTimes = 0; maxTimes = 32767;
while (minTimes < maxTimes) {
mid = (minTimes+maxTimes+1)>>1;
if (!multiples[mid]) {
multiples[mid] = that.clone();
multiples[mid].extend(multipleLength);
j = 0;
while (j < multipleLength) {
multiples[mid].digits[j] *= mid;
if (j) {
multiples[mid].digits[j] += multiples[mid].digits[j-1] >> 15;
multiples[mid].digits[j-1] %= 32768;
}
j++;
}
}
var cmpre = multiples[mid].getMultiplyByPowerOf32768(largestPower);
if (cmpre.less(thisAbs)) {
minTimes = mid;
} else if (thisAbs.less(cmpre)) {
maxTimes = mid-1;
} else {
minTimes = maxTimes = mid;
}
}
if (minTimes === 0) {
continue;
}
thisAbs.subtract(multiples[minTimes].getMultiplyByPowerOf32768(largestPower));
}
if (negative) {
thisAbs.negate();
}
return thisAbs;
};
BigInteger.prototype.mod = function(that) {
if (that.equals(BigInteger.ZERO)) { return null; }
var negative = false;
if (this.sign() === -1) {
negative = true;
}
this.abs();
that = that.getAbs();
var multiples = { 0: new_(BigInteger, ["0"]) };
var largestPower = 0;
var multipleLength = that.digits.length+2;
while (that.getMultiplyByPowerOf32768(largestPower).lessEqual(this)) {
largestPower++;
}
var minTimes, maxTimes, mid, j;
while (largestPower--) {
minTimes = 0; maxTimes = 32767;
while (minTimes < maxTimes) {
mid = (minTimes+maxTimes+1)>>1;
if (!multiples[mid]) {
multiples[mid] = that.clone();
multiples[mid].extend(multipleLength);
j = 0;
while (j < multipleLength) {
multiples[mid].digits[j] *= mid;
if (j) {
multiples[mid].digits[j] += multiples[mid].digits[j-1] >> 15;
multiples[mid].digits[j-1] %= 32768;
}
j++;
}
}
var cmpre = multiples[mid].getMultiplyByPowerOf32768(largestPower);
if (cmpre.less(this)) {
minTimes = mid;
} else if (this.less(cmpre)) {
maxTimes = mid-1;
} else {
minTimes = maxTimes = mid;
}
}
if (minTimes === 0) {
continue;
}
this.subtract(multiples[minTimes].getMultiplyByPowerOf32768(largestPower));
}
if (negative) {
this.negate();
}
};
BigInteger.prototype.exponentiateInt = function(amount) {
if (amount === 0) {
return 1;
} else if (amount === 1) {
return this.clone();
}
var square = this.getProductFast(this);
if (amount%2 === 0) {
return square.exponentiateInt(amount>>1);
}
return this.getProduct(square.exponentiateInt(amount>>1));
};
BigInteger.prototype.exponentiate = function(amount) {
var z = BigInteger.ZERO;
var o = BigInteger.ONE;
var t = new_(BigInteger, ["2"]);
if (amount.equals(z)) {
return o;
} else if (amount.equals(o)) {
return this.clone();
}
var square = this.getProductFast(this);
var nextPower = amount.getQuotient(t);
if (amount.digits[0]%2 === 0) {
return square.exponentiate(nextPower);
}
return this.getProduct(square.exponentiate(nextPower));
};
BigInteger.prototype.exponentiateMod = (function() {
var z = BigInteger.ZERO;
var o = BigInteger.ONE;
var t = new_(BigInteger, [[2, 0]]);
return function(amount, mod) {
var base = this.getMod(mod);
if (amount.equals(z)) {
if (mod.equals(o)) {
return z;
}
return o;
} else if (amount.equals(o)) {
return base;
}
var arr = [base];
var p2 = BigInteger.ONE.clone();
var result = BigInteger.ONE.clone();
var p2Arr = [p2];
while (p2.less(amount)) {
arr.push(arr[arr.length-1].getProductFast(arr[arr.length-1]));
arr[arr.length-1].mod(mod);
p2Arr.push(p2 = p2.getSum(p2));
}
var i = p2Arr.length;
var left = amount.clone();
while (i--) {
if (p2Arr[i].lessEqual(left)) {
result = result.getProduct(arr[i]);
result.mod(mod);
p2Arr[i].negate(); left.add(p2Arr[i]);
}
}
return result;
};
})();
BigInteger.prototype.exponentiateModNew = (function() { // TODO: Check if faster than exponentiateMod (probably slower, can optimise somehow)
var z = BigInteger.ZERO;
var o = BigInteger.ONE;
var t = new_(BigInteger, [[2, 0]]);
return function(amount, mod) {
var base = this.getMod(mod);
if (amount.equals(z)) {
if (mod.equals(o)) {
return z;
}
return o;
} else if (amount.equals(o)) {
return base;
}
amount.simplify();
var arr = Array(15), result = BigInteger.ONE.clone(), i=0, stop = amount.digits.length-2;
arr[0] = base;
while (i<stop) {
if (1&amount.digits[i]) {
result = result.getProductFast(arr[0]);
result.mod(mod);
}
for (var j=1;j<=14;j++) {
arr[j] = arr[j-1].getProductFast(arr[j-1]);
arr[j].mod(mod);
if ((1<<j)&amount.digits[i]) {
result = result.getProductFast(arr[j]);
result.mod(mod);
}
}
arr[0] = arr[14].getProductFast(arr[14]);
i++;
}
if (1&amount.digits[i]) {
result = result.getProductFast(arr[0]);
result.mod(mod);
}
for (var j=1;(1<<j)<=amount.digits[i];j++) {
arr[j] = arr[j-1].getProductFast(arr[j-1]);
arr[j].mod(mod);
if ((1<<j)&amount.digits[i]) {
result = result.getProductFast(arr[j]);
result.mod(mod);
}
}
return result;
};
})();
BigInteger.prototype.minusOne = function() {
this.extend(this.digits.length+2); // in case of carry over
var position = 0;
while (position<this.digits.length) {
this.digits[position]--;
if (this.digits[position] < 0) {
this.digits[position] = 32767;
} else { break; }
position++;
}
this.simplify();
};
BigInteger.gcd = function(a, b) {
a = a.getAbs();
b = b.getAbs();
while (a.sign()) {
b.mod(a);
if (b.sign()) {
a.mod(b);
} else { return a; }
}
return b;
};
BigInteger.factorial = function(a) {
var aCopy = a.clone();
var product = new_(BigInteger, [[1, 0]]);
while (aCopy.sign() === 1) {
product = product.getProduct(aCopy);
aCopy.minusOne();
}
return product;
};
BigInteger.random = function(x, y) {
if (arguments.length === 1) {
x.simplify();
var arr, candidate;
do {
var arr = [0];
arr.push(Math.floor(Math.random()*(x.digits[x.digits.length-2]+1)));
for (var i=x.digits.length-3;i>=0;i--) {
arr.push(Math.floor(Math.random()*32768));
}
arr.reverse();
candidate = new_(BigInteger, [arr]);
} while (!candidate.less(x));
return candidate;
}
if (arguments.length === 2) {
if (y.less(x)) {
x = arguments[1];
y = arguments[0];
}
var r = BigInteger.random(y.getDifference(x));
r.add(x);
return x;
}
};
BigInteger.fromBase = (function() { // assume positive
var hash = {
0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9,
A: 10, B: 11, C: 12, D: 13, E: 14, F: 15, G: 16, H: 17, I: 18, J: 19,
K: 20, L: 21, M: 22, N: 23, O: 24, P: 25, Q: 26, R: 27, S: 28, T: 29,
U: 30, V: 31, W: 32, X: 33, Y: 34, Z: 35, a: 36, b: 37, c: 38, d: 39,
e: 40, f: 41, g: 42, h: 43, i: 44, j: 45, k: 46, l: 47, m: 48, n: 49,
o: 50, p: 51, q: 52, r: 53, s: 54, t: 55, u: 56, v: 57, w: 58, x: 59,
y: 60, z: 61
};
var fromBaseNaive = function(number, base) {
var result = BigInteger.ZERO.clone();
for (var i=0;i<number.length;i++) {
result.multiplySmall(base);
result.addSmall(hash[number[i]]);
}
return result;
};
return function(number, base) {
if (number.length < 8) {
return fromBaseNaive(number, base);
}
var basePowers = [new_(BigInteger, [base || [10, 0]])];
while ((1<<basePowers.length)<=number.length) {
basePowers.push(basePowers[basePowers.length-1].getProductFast(basePowers[basePowers.length-1]));
}
var subResult = {};
for (var i=1;i<=number.length;i++) {
var p = i&-i;
subResult[p] = new_(BigInteger, [[hash[number[number.length-i]], 0]]);
for (var j=0;(1<<j)<p;j++) {
subResult[p] = subResult[p].getProductFast(basePowers[j]);
subResult[p].add(subResult[1<<j]); subResult[1<<j] = null;
}
}
var result = BigInteger.ZERO.clone();
for (var i=0;(1<<i)<=number.length;i++) {
if (subResult[1<<i]) {
result = result.getProductFast(basePowers[i]);
result.add(subResult[1<<i]);
}
}
return result;
};
})();
BigInteger.isProbablePrime = (function() {
/**
* Precondition: 2 <= d < n
*/
var primeSingle = function(n, d, beginExpo, nMinusOne, timesRepeat) {
var t = timesRepeat, testWith;
testWith = d.exponentiateMod(beginExpo, n);
if (testWith.equals(BigInteger.ONE) || testWith.equals(nMinusOne)) {
return true;
}
while (t--) {
testWith = testWith.getProduct(testWith);
testWith.mod(n);
if (testWith.equals(BigInteger.ONE)) {
return false;
} else if (testWith.equals(nMinusOne)) {
return true;
}
}
return testWith.equals(BigInteger.ONE);
};
// Assumption: Number being tested >= 2 and is not divisible by 2 or 5
var trialDivision = (function() {
var smallTests = [3, 5], sieve = Array(0xF), i = 0xF, j;
while (i--) { sieve[i] = 0xAAAAAAAA; }
sieve[0] = 0xAAAAAAAC; // Small primes
for (j=9;j<0x200;j+=6) {
sieve[j>>5] = sieve[j>>5]&~(1<<(j&31));
}
for (j=25;j<0x200;j+=10) {
sieve[j>>5] = sieve[j>>5]&~(1<<(j&31));
}
for (i=7;i<0x200;i+=2) {
if (sieve[i>>5]&(1<<(i&31))) {
smallTests.push(i);
for (j=i*i;j<0x200;j+=2*i) {
sieve[j>>5] = sieve[j>>5]&~(1<<(j&31));
}
}
i+=4;
if (sieve[i>>5]&(1<<(i&31))) {
smallTests.push(i);
for (j=i*i;j<0x200;j+=2*i) {
sieve[j>>5] = sieve[j>>5]&~(1<<(j&31));
}
}
}
var rem = Array(smallTests.length);
return function(x) {
x.simplify();
var i = x.digits.length, j = smallTests.length;
while (j--) {
rem[j] = 0;
}
while (i--) {
j = smallTests.length;
while (j--) {
rem[j] = (rem[j]*32768+x.digits[i])%smallTests[j];
}
}
j = smallTests.length;
while (j--) {
if (!rem[j]) { return false; }
}
return true;
};
})();
var smallTests = [new_(BigInteger, [[2, 0]]), new_(BigInteger, [[3, 0]]), new_(BigInteger, [[5, 0]]), new_(BigInteger, [[7, 0]]), new_(BigInteger, [[11, 0]]), new_(BigInteger, [[13, 0]]), new_(BigInteger, [[17, 0]]), new_(BigInteger, [[19, 0]]), new_(BigInteger, [[23, 0]]), new_(BigInteger, [[29, 0]]), new_(BigInteger, [[31, 0]]), new_(BigInteger, [[37, 0]]), new_(BigInteger, [[41, 0]])];
var two = new_(BigInteger, [[2, 0]]);
var boundTests = new_(BigInteger, ["3317044064679887385961981"]);
return function(n, extraTests) {
if (n.less(two)) {
return false;
} else if (n.equals(two)) {
return true;
} else if (n.digits[0]%2 === 0) {
return false;
} else if (n.digits.length<=2 && n.digits[0] < 0x200) {
var x = n.digits[0];
return sieve[i>>5]&(1<<(i&31));
}
if (!trialDivision(n)) { return false; }
var endNMinusOne = n.clone();
endNMinusOne.minusOne();
var nMinusOne = endNMinusOne.clone();
var timesRepeat = 0;
while (endNMinusOne.digits[0]%2 === 0) {
endNMinusOne = endNMinusOne.getQuotient(two);
timesRepeat++;
}
for (var i=0;i<13;i++) {
if (!primeSingle(n, smallTests[i], endNMinusOne, nMinusOne, timesRepeat)) {
return false;
}
}
if (n.less(boundTests)) { return true; }
while (extraTests--) {
var test = BigInteger.random(two, nMinusOne);
if (!primeSingle(n, test, endNMinusOne, nMinusOne, timesRepeat)) {
return false;
}
}
return true;
};
})();
BigInteger.isProbablePrimeWithoutExtraTests = (function() {
/**
* Precondition: 2 <= d < n
*/
var primeSingle = function(n, d, beginExpo, nMinusOne, timesRepeat) {
var t = timesRepeat, testWith;
testWith = d.exponentiateMod(beginExpo, n);
if (testWith.equals(BigInteger.ONE) || testWith.equals(nMinusOne)) {
return true;
}
while (t--) {
testWith = testWith.getProduct(testWith);
testWith.mod(n);
if (testWith.equals(BigInteger.ONE)) {
return false;
} else if (testWith.equals(nMinusOne)) {
return true;
}
}
return testWith.equals(BigInteger.ONE);
};
// Assumption: Number being tested >= 2 and is not divisible by 2 or 5
var trialDivision = (function() {
var smallTests = [[3, 5], [], []], sieve = Array(0xFFFFF), i = 0xFFFFF, j;
while (i--) { sieve[i] = 0xAAAAAAAA; }
sieve[0] = 0xAAAAAAAC; // Small primes
for (j=9;j<0x2000000;j+=6) {
sieve[j>>5] = sieve[j>>5]&~(1<<(j&31));
}
for (j=25;j<0x2000000;j+=10) {
sieve[j>>5] = sieve[j>>5]&~(1<<(j&31));
}
for (i=7;i<0x20000;i+=2) {
if (sieve[i>>5]&(1<<(i&31))) {
smallTests[0].push(i);
for (j=i*i;j<0x2000000;j+=2*i) {
sieve[j>>5] = sieve[j>>5]&~(1<<(j&31));
}
}
i+=4;
if (sieve[i>>5]&(1<<(i&31))) {
smallTests[0].push(i);
for (j=i*i;j<0x2000000;j+=2*i) {
sieve[j>>5] = sieve[j>>5]&~(1<<(j&31));
}
}
}
for (i=0x20003;i<0x200000;i+=2) {
if (sieve[i>>5]&(1<<(i&31))) {
smallTests[1].push(i);
for (j=i*i;j<0x2000000;j+=2*i) {
sieve[j>>5] = sieve[j>>5]&~(1<<(j&31));
}
}
i+=4;
if (sieve[i>>5]&(1<<(i&31))) {
smallTests[1].push(i);
for (j=i*i;j<0x2000000;j+=2*i) {
sieve[j>>5] = sieve[j>>5]&~(1<<(j&31));
}
}
}
for (i=0x200003;i<0x2000000;i+=2) {
if (sieve[i>>5]&(1<<(i&31))) {
smallTests[2].push(i);
for (j=i*i;j<0x2000000;j+=2*i) {
sieve[j>>5] = sieve[j>>5]&~(1<<(j&31));
}
}
i+=4;
if (sieve[i>>5]&(1<<(i&31))) {
smallTests[2].push(i);
for (j=i*i;j<0x2000000;j+=2*i) {
sieve[j>>5] = sieve[j>>5]&~(1<<(j&31));
}
}
}
var rem = Array(smallTests[2].length);
return function(x) {
x.simplify();
var i = x.digits.length, j = smallTests[0].length;
while (j--) {
rem[j] = 0;
}
while (i--) {
j = smallTests[0].length;
while (j--) {
rem[j] = (rem[j]*32768+x.digits[i])%smallTests[0][j];
}
}
j = smallTests[0].length;
while (j--) {
if (!rem[j]) { return false; }
}
j = smallTests[1].length;
while (j--) {
rem[j] = 0;
}
i = x.digits.length;
while (i--) {
j = smallTests[1].length;
while (j--) {
rem[j] = (rem[j]*32768+x.digits[i])%smallTests[1][j];
}
}
j = smallTests[1].length;
while (j--) {
if (!rem[j]) { return false; }
}
j = smallTests[2].length;
while (j--) {
rem[j] = 0;
}
i = x.digits.length;
while (i--) {
j = smallTests[2].length;
while (j--) {
rem[j] = (rem[j]*32768+x.digits[i])%smallTests[2][j];
}
}
j = smallTests[2].length;
while (j--) {
if (!rem[j]) { return false; }
}
return true;
};
})();
var two = new_(BigInteger, [[2, 0]]);
return function(n, extraTests) {
if (n.less(two)) {
return false;
} else if (n.equals(two)) {
return true;
} else if (n.digits[0]%2 === 0) {
return false;
} else if (n.digits.length<=3 && (+n.toString()) < 0x2000000) {
var x = +n.toString();
return sieve[x>>5]&(1<<(x&31));
}
if (!trialDivision(n)) { return false; }
var endNMinusOne = n.clone();
endNMinusOne.minusOne();
var nMinusOne = endNMinusOne.clone();
var timesRepeat = 0;
while (endNMinusOne.digits[0]%2 === 0) {
endNMinusOne = endNMinusOne.getQuotient(two);
timesRepeat++;
}
console.log("Running tests: "+extraTests);
for (var i=0;i<extraTests;i++) {
var test = BigInteger.random(two, nMinusOne);
if (!primeSingle(n, test, endNMinusOne, nMinusOne, timesRepeat)) {
console.log("Not prime: Found on test "+i);
return false;
}
console.log("Still prime on test "+i);
}
return true;
};
})();
var start = new Date().getTime();
var bound = new BigInteger("0x0"+"F".repeat(64)); // should be reasonable
var prime = bound.getSum(BigInteger.random(bound));
var trials = 0;
while (!BigInteger.isProbablePrimeWithoutExtraTests(prime, 5)) {
console.log("Trials without primes: "+(trials++));
prime.plusOne(); // = bound.getSum(BigInteger.random(bound));
}
console.log("Found prime on trial "+(trials++));
console.log(prime+"");
var timeTaken = new Date().getTime()-start;
console.log("Time taken: "+(timeTaken/1000)+" seconds");
</script>
</head>
<body>Checking primes in console...</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment