quadraticsievefactorization - npm Package Compare versions

Comparing version 1.0.72 to 1.0.73

package.json

 {
   "name": "quadraticsievefactorization",
-  "version": "1.0.72",
+  "version": "1.0.73",
   "description": "Quadratic Sieve integer factorization method for JavaScript bigints",
@@ -27,2 +27,4 @@ "main": "QuadraticSieveFactorization.js",
     "isPrime.js",
+    "isProbablyPrime64.js",
+    "PollardsRho64.js",
     "solve.js",
@@ -29,0 +31,0 @@ "sqrtMod.js",

README.md

 # QuadraticSieveFactorization
-Integer factorization using [Quadratic Sieve](https://en.wikipedia.org/wiki/Quadratic_sieve) algorithm in JavaScript using native BigInt
+Integer factorization using [Quadratic Sieve](https://en.wikipedia.org/wiki/Quadratic_sieve) algorithm in JavaScript.
+The variant is multipolynomial self-initializing with two large-primes.
 
 There is series of videos explaining the algorithm at https://www.youtube.com/playlist?list=PL0OUqr2O9PxLd35SgBiWIxuLgm7mYksfp .
-
 Useful info can also be found at https://www.rieselprime.de/ziki/Self-initializing_quadratic_sieve and at https://www.enseignement.polytechnique.fr/informatique/INF558/TD/td_5/S0025-5718-1987-0866119-8.pdf .
@@ -33,2 +33,6 @@
 
-It took almost 3.5 hours to factor [RSA-100](https://en.wikipedia.org/wiki/RSA_numbers#RSA-100) on Core i7-1165G7 .
+The code uses only single thread.
+It takes approximately 1.5 hours to factor [RSA-100](https://en.wikipedia.org/wiki/RSA_numbers#RSA-100) 
+and 13.5 hours to factor [RSA-110](https://en.wikipedia.org/wiki/RSA_numbers#RSA-110) on Core i7-1165G7
+
+Probably larger numbers will cause lack of memory.

solve.js

 /*jshint esversion:6, bitwise:false*/
 
-const BitSetWordSize = 31; // see https://v8.dev/blog/pointer-compression
+// see https://v8.dev/blog/pointer-compression
 
@@ -15,4 +15,5 @@ function packedArray(n) {
 function BitSet(size) {
-  const n = Math.ceil(size / (4 * BitSetWordSize)) * 4;
-  this.data = packedArray(n);
+  const n = Math.ceil(size / (8 * 32)) * 8;
+  this.data = new Uint32Array(n);
+  this.data64 = new BigUint64Array(this.data.buffer);
   this.size = size;
@@ -25,6 +26,5 @@ }
   const data = this.data;
-  let q = Math.floor(index / BitSetWordSize);
-  let r = index % BitSetWordSize;
-  let x = data[q] >> r;
-  while (x === 0) {
+  let q = index >> 5;
+  let r = index & 31;
+  while ((data[q] >> r) === 0) {
     q += 1;
@@ -34,13 +34,7 @@ if (q === data.length) {
     }
-    x = data[q];
     r = 0;
   }
-  if (x === (-1 << (BitSetWordSize - 1))) {
-    // -x overflows
-    r += BitSetWordSize - 1;
-  } else {
-    // https://stackoverflow.com/questions/61442006/whats-the-most-efficient-way-of-getting-position-of-least-significant-bit-of-a
-    r += 31 - Math.clz32(x & -(+x));
-  }
-  return q * BitSetWordSize + r;
+  // https://stackoverflow.com/questions/61442006/whats-the-most-efficient-way-of-getting-position-of-least-significant-bit-of-a
+  r += 31 - Math.clz32((data[q] >> r) & -(data[q] >> r));
+  return (q * 32) + r;
 };
@@ -51,18 +45,14 @@ BitSet.prototype.toggle = function (index) {
   }
-  const q = Math.floor(index / BitSetWordSize);
-  const r = index % BitSetWordSize;
-  this.data[q] ^= (r === BitSetWordSize - 1 ? ((-1) << r) : (1 << r));
+  this.data[index >> 5] ^= (1 << (index & 31));
 };
 BitSet.prototype.xor = function (other) {
-  const a = this.data;
-  const b = other.data;
+  const a = this.data64;
+  const b = other.data64;
   const n = a.length | 0;
-  if (n !== b.length || n % 4 !== 0) {
+  if (n !== b.length || n % 2 !== 0) {
     throw new RangeError();
   }
-  for (let i = 0; i < n; i += 4) {
-    a[i + 0] ^= b[i + 0] | 0;
-    a[i + 1] ^= b[i + 1] | 0;
-    a[i + 2] ^= b[i + 2] | 0;
-    a[i + 3] ^= b[i + 3] | 0;
+  for (let i = 0; i < n; i += 2) {
+    a[i + 0] ^= b[i + 0];
+    a[i + 1] ^= b[i + 1];
   }
@@ -76,3 +66,3 @@ };
 BitSet.prototype.toString = function () {
-  return this.data.map(x => (x >>> 0).toString(2).padStart(BitSetWordSize, '0').split('').reverse().join('')).join('').slice(0, this.size);
+  return this.data.map(x => (x >>> 0).toString(2).padStart(32, '0').split('').reverse().join('')).join('').slice(0, this.size);
 };
@@ -79,0 +69,0 @@

sqrtMod.js

@@ -0,1 +1,2 @@
+"use strict";
 
@@ -9,6 +10,8 @@ // https://rosettacode.org/wiki/Tonelli-Shanks_algorithm#Python
       exponent /= 2;
-      base = (base * base) % modulus;
+      base = (base * base);
+      base = base - Math.floor(base / modulus) * modulus;
     } else {
       exponent -= 1;
-      accumulator = (accumulator * base) % modulus;
+      accumulator = (accumulator * base);
+      accumulator = accumulator - Math.floor(accumulator / modulus) * modulus;
     }
@@ -19,7 +22,44 @@ }
 
-function legendre(a, p) {
-  console.assert((p - 1) % 2 === 0);
-  return modPowSmall(a, (p - 1) / 2, p);
+
+//function legendre(a, p) {
+//  console.assert((p - 1) % 2 === 0);
+//  return (modPowSmall(a, (p - 1) / 2, p) + 1) % p - 1;
+//}
+
+// a/n is represented as (a,n)
+function legendre(a, n) {
+    if (typeof a !== 'number' || typeof n !== 'number') {
+      throw new TypeError();
+    }
+    // from https://en.wikipedia.org/wiki/Jacobi_symbol#Implementation_in_C++ :
+    a = a | 0;
+    n = n | 0;
+    //console.assert(n > 0 && n%2 == 1);
+    //step 1
+    a = (a | 0) % (n | 0);
+    var t = 1;
+    var r = 0;
+    //step 3
+    while (a !== 0) {
+        //step 2
+        while ((a & 1) === 0) {
+            a >>= 1;
+            r = n & 7;
+            if (r === 3 || r === 5) {
+                t = -t;
+            }
+        }
+        //step 4
+        r = n;
+        n = a;
+        a = r;
+        if ((a & 3) === 3 && (n & 3) === 3) {
+            t = -t;
+        }
+        a = (a | 0) % (n | 0);
+    }
+    return n === 1 ? t : 0;
 }
 
+
 function sqrtMod(n, p) {
@@ -42,3 +82,3 @@ // Tonelli–Shanks algorithm:
   let z = 2;
-  while (z <= p && p - 1 !== legendre(z, p)) {
+  while (z <= p && legendre(z, p) !== -1) {
     z += 1;
@@ -45,0 +85,0 @@ }

wast2wasm.js

@@ -5,2 +5,3 @@ /*jshint esversion:6, bitwise:false*/
 
+
 function wast2wasm(sExpression) {
@@ -30,2 +31,31 @@
 
+  function pushVarint(value, size) {
+    // from Wikipedia - https://en.wikipedia.org/wiki/LEB128#Encode_signed_integer
+    let more = true;
+    let negative = (value < 0n);
+
+    /* the size in bits of the variable value, e.g., 64 if value's type is int64_t */
+    // size = no. of bits in signed integer;
+
+    while (more) {
+      //byte = low-order 7 bits of value;
+      let byte = Number(BigInt.asUintN(7, value));
+      value >>= 7n;
+      /* the following is only necessary if the implementation of >>= uses a
+         logical shift rather than an arithmetic shift for a signed left operand */
+      if (negative) {
+        value |= (-1n << (size - 7)); /* sign extend */
+      }
+
+      /* sign bit of byte is second high-order bit (0x40) */
+      if ((value == 0n && (byte & 0x40) === 0) || (value == -1n && (byte & 0x40) !== 0)) {
+        more = false;
+      } else {
+        //set high-order bit of byte;
+        byte |= (1 << 7);
+      }
+      bytes.push(byte);
+    }
+  }
+
   function pushSize(f) {
@@ -48,5 +78,10 @@ const start = bytes.length;
       bytes.push(opcode);
-    } else {
+    } else if (opcode <= 0xFDFF) {
       bytes.push((opcode >> 8));
       pushUnsignedInteger(bytes.length, opcode & 0xFF);
+    } else if (opcode <= 0xFD1FF) {
+      bytes.push(0xFD);
+      pushUnsignedInteger(bytes.length, opcode & 0xFFF);
+    } else {
+      throw new Error();
     }
@@ -85,3 +120,7 @@ }
           emitTypes(node[1], 'param');
-          emitTypes(node[2], 'result');
+          if (node.length < 3) {
+            pushByte(0x00);
+          } else {
+            emitTypes(node[2], 'result');
+          }
         } else {
@@ -162,30 +201,26 @@ throw new TypeError();
   // from https://pengowray.github.io/wasm-ops/:
+  const OpcodesStart = 0;
   const OpcodesList = 'unreachable nop block loop if else - - - - - end br br_if br_table return call call_indirect - - - - - - - - drop select - - - - local.get local.set local.tee global.get global.set - - - i32.load i64.load f32.load f64.load i32.load8_s i32.load8_u i32.load16_s i32.load16_u i64.load8_s i64.load8_u i64.load16_s i64.load16_u i64.load32_s i64.load32_u i32.store i64.store f32.store f64.store i32.store8 i32.store16 i64.store8 i64.store16 i64.store32 memory.size memory.grow i32.const i64.const f32.const f64.const i32.eqz i32.eq i32.ne i32.lt_s i32.lt_u i32.gt_s i32.gt_u i32.le_s i32.le_u i32.ge_s i32.ge_u i64.eqz i64.eq i64.ne i64.lt_s i64.lt_u i64.gt_s i64.gt_u i64.le_s i64.le_u i64.ge_s i64.ge_u f32.eq f32.ne f32.lt f32.gt f32.le f32.ge f64.eq f64.ne f64.lt f64.gt f64.le f64.ge i32.clz i32.ctz i32.popcnt i32.add i32.sub i32.mul i32.div_s i32.div_u i32.rem_s i32.rem_u i32.and i32.or i32.xor i32.shl i32.shr_s i32.shr_u i32.rotl i32.rotr i64.clz i64.ctz i64.popcnt i64.add i64.sub i64.mul i64.div_s i64.div_u i64.rem_s i64.rem_u i64.and i64.or i64.xor i64.shl i64.shr_s i64.shr_u i64.rotl i64.rotr f32.abs f32.neg f32.ceil f32.floor f32.trunc f32.nearest f32.sqrt f32.add f32.sub f32.mul f32.div f32.min f32.max f32.copysign f64.abs f64.neg f64.ceil f64.floor f64.trunc f64.nearest f64.sqrt f64.add f64.sub f64.mul f64.div f64.min f64.max f64.copysign i32.wrap_i64 i32.trunc_f32_s i32.trunc_f32_u i32.trunc_f64_s i32.trunc_f64_u i64.extend_i32_s i64.extend_i32_u i64.trunc_f32_s i64.trunc_f32_u i64.trunc_f64_s i64.trunc_f64_u f32.convert_i32_s f32.convert_i32_u f32.convert_i64_s f32.convert_i64_u f32.demote_f64 f64.convert_i32_s f64.convert_i32_u f64.convert_i64_s f64.convert_i64_u f64.promote_f32 i32.reinterpret_f32 i64.reinterpret_f64 f32.reinterpret_i32 f64.reinterpret_i64'.split(' ');
+  const FCExtStart = 0xFC00;
+  const FCExtList = 'i32.trunc_sat_f32_s i32.trunc_sat_f32_u i32.trunc_sat_f64_s i32.trunc_sat_f64_u i64.trunc_sat_f32_s i64.trunc_sat_f32_u i64.trunc_sat_f64_s i64.trunc_sat_f64_u'.split(' ');
+  const SIMDOpcodesStart = 0xFD00;
+  const SIMDOpcodesList = 'v128.load v128.load8x8_s v128.load8x8_u v128.load16x4_s v128.load16x4_u v128.load32x2_s v128.load32x2_u v128.load8_splat v128.load16_splat v128.load32_splat v128.load64_splat v128.store v128.const i8x16.shuffle i8x16.swizzle i8x16.splat i16x8.splat i32x4.splat i64x2.splat f32x4.splat f64x2.splat i8x16.extract_lane_s i8x16.extract_lane_u i8x16.replace_lane i16x8.extract_lane_s i16x8.extract_lane_u i16x8.replace_lane i32x4.extract_lane i32x4.replace_lane i64x2.extract_lane i64x2.replace_lane f32x4.extract_lane f32x4.replace_lane f64x2.extract_lane f64x2.replace_lane i8x16.eq i8x16.ne i8x16.lt_s i8x16.lt_u i8x16.gt_s i8x16.gt_u i8x16.le_s i8x16.le_u i8x16.ge_s i8x16.ge_u i16x8.eq i16x8.ne i16x8.lt_s i16x8.lt_u i16x8.gt_s i16x8.gt_u i16x8.le_s i16x8.le_u i16x8.ge_s i16x8.ge_u i32x4.eq i32x4.ne i32x4.lt_s i32x4.lt_u i32x4.gt_s i32x4.gt_u i32x4.le_s i32x4.le_u i32x4.ge_s i32x4.ge_u f32x4.eq f32x4.ne f32x4.lt f32x4.gt f32x4.le f32x4.ge f64x2.eq f64x2.ne f64x2.lt f64x2.gt f64x2.le f64x2.ge v128.not v128.and v128.andnot v128.or v128.xor v128.bitselect v128.any_true v128.load8_lane v128.load16_lane v128.load32_lane v128.load64_lane v128.store8_lane v128.store16_lane v128.store32_lane v128.store64_lane v128.load32_zero v128.load64_zero f32x4.demote_f64x2_zero f64x2.promote_low_f32x4 i8x16.abs i8x16.neg i8x16.popcnt i8x16.all_true i8x16.bitmask i8x16.narrow_i16x8_s i8x16.narrow_i16x8_u f32x4.ceil f32x4.floor f32x4.trunc f32x4.nearest i8x16.shl i8x16.shr_s i8x16.shr_u i8x16.add i8x16.add_sat_s i8x16.add_sat_u i8x16.sub i8x16.sub_sat_s i8x16.sub_sat_u f64x2.ceil f64x2.floor i8x16.min_s i8x16.min_u i8x16.max_s i8x16.max_u f64x2.trunc i8x16.avgr_u i16x8.extadd_pairwise_i8x16_s i16x8.extadd_pairwise_i8x16_u i32x4.extadd_pairwise_i16x8_s i32x4.extadd_pairwise_i16x8_u i16x8.abs i16x8.neg i16x8.q15mulr_sat_s i16x8.all_true i16x8.bitmask i16x8.narrow_i32x4_s i16x8.narrow_i32x4_u i16x8.extend_low_i8x16_s i16x8.extend_high_i8x16_s i16x8.extend_low_i8x16_u i16x8.extend_high_i8x16_u i16x8.shl i16x8.shr_s i16x8.shr_u i16x8.add i16x8.add_sat_s i16x8.add_sat_u i16x8.sub i16x8.sub_sat_s i16x8.sub_sat_u f64x2.nearest i16x8.mul i16x8.min_s i16x8.min_u i16x8.max_s i16x8.max_u  i16x8.avgr_u i16x8.extmul_low_i8x16_s i16x8.extmul_high_i8x16_s i16x8.extmul_low_i8x16_u i16x8.extmul_high_i8x16_u i32x4.abs i32x4.neg i8x16.relaxed_swizzle i32x4.all_true i32x4.bitmask i32x4.relaxed_trunc_f32x4_s i32x4.relaxed_trunc_f32x4_u i32x4.extend_low_i16x8_s i32x4.extend_high_i16x8_s i32x4.extend_low_i16x8_u i32x4.extend_high_i16x8_u i32x4.shl i32x4.shr_s i32x4.shr_u i32x4.add f32x4.relaxed_madd f32x4.relaxed_nmadd i32x4.sub i8x16.relaxed_laneselect i16x8.relaxed_laneselect f32x4.relaxed_min i32x4.mul i32x4.min_s i32x4.min_u i32x4.max_s i32x4.max_u i32x4.dot_i16x8_s  i32x4.extmul_low_i16x8_s i32x4.extmul_high_i16x8_s i32x4.extmul_low_i16x8_u i32x4.extmul_high_i16x8_u i64x2.abs i64x2.neg  i64x2.all_true i64x2.bitmask i32x4.relaxed_trunc_f64x2_s_zero i32x4.relaxed_trunc_f64x2_u_zero i64x2.extend_low_i32x4_s i64x2.extend_high_i32x4_s i64x2.extend_low_i32x4_u i64x2.extend_high_i32x4_u i64x2.shl i64x2.shr_s i64x2.shr_u i64x2.add f64x2.relaxed_madd f64x2.relaxed_nmadd i64x2.sub i32x4.relaxed_laneselect i64x2.relaxed_laneselect f64x2.relaxed_min i64x2.mul i64x2.eq i64x2.ne i64x2.lt_s i64x2.gt_s i64x2.le_s i64x2.ge_s i64x2.extmul_low_i32x4_s i64x2.extmul_high_i32x4_s i64x2.extmul_low_i32x4_u i64x2.extmul_high_i32x4_u f32x4.abs f32x4.neg f32x4.relaxed_max f32x4.sqrt f32x4.add f32x4.sub f32x4.mul f32x4.div f32x4.min f32x4.max f32x4.pmin f32x4.pmax f64x2.abs f64x2.neg f64x2.relaxed_max f64x2.sqrt f64x2.add f64x2.sub f64x2.mul f64x2.div f64x2.min f64x2.max f64x2.pmin f64x2.pmax i32x4.trunc_sat_f32x4_s i32x4.trunc_sat_f32x4_u f32x4.convert_i32x4_s f32x4.convert_i32x4_u i32x4.trunc_sat_f64x2_s_zero i32x4.trunc_sat_f64x2_u_zero f64x2.convert_low_i32x4_s f64x2.convert_low_i32x4_u'.split(' ');
 
-  const Opcodes = {};
+  const RelaxedSIMDOpcodesStart = 0xFD100;
+  const RelaxedSIMDOpCodesList = 'i8x16.relaxed_swizzle i32x4.relaxed_trunc_f32x4_s i32x4.relaxed_trunc_f32x4_u i32x4.relaxed_trunc_f64x2_s_zero i32x4.relaxed_trunc_f64x2_u_zero f32x4.relaxed_madd f32x4.relaxed_nmadd f64x2.relaxed_madd f64x2.relaxed_nmadd i8x16.relaxed_laneselect i16x8.relaxed_laneselect i32x4.relaxed_laneselect i64x2.relaxed_laneselect f32x4.relaxed_min f32x4.relaxed_max f64x2.relaxed_min f64x2.relaxed_max i16x8.relaxed_q15mulr_s i16x8.relaxed_dot_i8x16_i7x16_s i32x4.relaxed_dot_i8x16_i7x16_add_s f32x4.relaxed_dot_bf16x8_add_f32x4'.split(' ');
+
+  const AllOpcodes = {};
   for (let i = 0; i < OpcodesList.length; i++) {
-    Opcodes[OpcodesList[i]] = i;
+    AllOpcodes[OpcodesList[i]] = i + OpcodesStart;
   }
+  for (let i = 0; i < FCExtList.length; i++) {
+    AllOpcodes[FCExtList[i]] = i + FCExtStart;
+  }
+  for (let i = 0; i < SIMDOpcodesList.length; i++) {
+    AllOpcodes[SIMDOpcodesList[i]] = i + SIMDOpcodesStart;
+  }
+  for (let i = 0; i < RelaxedSIMDOpCodesList.length; i++) {
+    AllOpcodes[RelaxedSIMDOpCodesList[i]] = i + RelaxedSIMDOpcodesStart;
+  }
 
-  const SIMDOpcodes = {
-    'i8x16.splat': 0xFD0F,
-    'i8x16.ge_u': 0xFD2C,
-    'i8x16.all_true': 0xFD63,
-
-    'i32x4.splat': 0xFD11,
-    'i32x4.lt_s': 0xFD39,
-    'i32x4.ge_s': 0xFD3F,
-    'i32x4.gt_s': 0xFD3B,
-    'i32x4.all_true': 0xFDA3,
-    'v128.any_true': 0xFD53,
-    'i8x16.gt_s': 0xFD27,
-    'i8x16.gt_u': 0xFD28,
-
-    'v128.xor': 0xFD51,
-    'v128.load': 0xFD00,
-    'v128.store': 0xFD0B
-  };
-
-  const AllOpcodes = Object.assign({}, Opcodes, SIMDOpcodes);
-
   function opcode(name) {
@@ -219,2 +254,15 @@ const code = AllOpcodes[name];
     if (node.length !== 2) {
+      if (node.length === 6 && node[0] === "v128.const" && node[1] === "i32x4") {
+        //TODO:
+        bytes.push(0xFD);
+        bytes.push(0x0C);
+        for (var i = 0; i < 4; i++) {
+          var v = Number(node[2 + i]) >>> 0;
+          bytes.push((v >>> 0) & 0xFF);
+          bytes.push((v >>> 8) & 0xFF);
+          bytes.push((v >>> 16) & 0xFF);
+          bytes.push((v >>> 24) & 0xFF);
+        }
+        return;
+      }
       throw new TypeError();
@@ -224,6 +272,21 @@ }
     if ((Number(node[1]) & 0x3F).toString() !== node[1]) {
-      throw new RangeError('unsupported literal: ' + node[1]);
+      if (node[0] === 'i64.const') {//TODO: !?
+        if (BigInt(node[1]) < 0 | BigInt(node[1]) >= 2n**64n) {
+          throw new RangeError('unsupported literal: ' + node[1]);
+        }
+        pushByte(opcode(node[0]));
+        pushVarint(BigInt(node[1]), 64);
+      } else if (node[0] === 'i32.const') {//TODO: !?
+        if (BigInt(node[1]) < 0 | BigInt(node[1]) >= 2n**32n) {
+          throw new RangeError('unsupported literal: ' + node[1]);
+        }
+        pushByte(opcode(node[0]));
+        pushVarint(BigInt(node[1]), 32);
+      } else {
+        throw new RangeError('unsupported literal: ' + node[1]);
+      }
+    } else {
+      pushByte(opcode(node[0]));
+      pushByte(Number(node[1]));
     }
-    pushByte(opcode(node[0]));
-    pushByte(Number(node[1]));
   }
@@ -320,6 +383,12 @@
     } else {
-      for (let i = 1; i < node.length; i++) {
-        emitCode(node[i]);
+      if (node[0] === "i32x4.extract_lane" && node.length === 3) {//TODO: !?
+        emitCode(node[2]);
+        pushOpcode(opcode(node[0]));
+        pushByte(Number(node[1]));
+      } else {
+        for (let i = 1; i < node.length; i++) {
+          emitCode(node[i]);
+        }
+        pushOpcode(opcode(node[0]));
       }
-      pushOpcode(opcode(node[0]));
     }
@@ -326,0 +395,0 @@ }

No alert changes

Improved metrics

Total package byte prevSize

133043

69.83%

Number of package files

9

28.57%

Lines of code

2822

26.04%

Number of lines in readme file

38

11.76%

No dependency changes