quadraticsievefactorization

QuadraticSieveFactorization

Integer factorization using 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 .

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

The code uses only single thread. It takes approximately 1.5 hours to factor RSA-100 and 13.5 hours to factor RSA-110 on Core i7-1165G7

Probably larger numbers will cause lack of memory.