quadraticsievefactorization

1.0.72 • Public • Published

QuadraticSieveFactorization

Integer factorization using Quadratic Sieve algorithm in JavaScript using native BigInt

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 .

See other links in the code.

Example

import factorize from './QuadraticSieveFactorization.js';
console.time();
const f = factorize(2n**128n + 1n);
console.timeEnd();
// ~50ms
console.assert(f === 5704689200685129054721n || f === 59649589127497217n, f);

Usage notes:

  • Do not call for the prime numbers. It may hang for them. Check if the number is prime instead.
  • Do not call for the perfect powers. it may hang for them. Check if the number is a perfect power instead.
  • Do not call for the numbers with a small factor, it is as slow as for semiprimes with similar factor size for them. Try other algorithms to check for small factors instead.
  • The returned value is a some factor, not necessary prime.

See https://www.rieselprime.de/ziki/Factorization for the more detailed usage notes.

Demo

See demo.

Performance

It took almost 3.5 hours to factor RSA-100 on Core i7-1165G7 .

Package Sidebar

Install

npm i quadraticsievefactorization

Weekly Downloads

8

Version

1.0.72

License

none

Unpacked Size

78.3 kB

Total Files

7

Last publish

Collaborators

  • yaffle