1.0.78 • Published 8 months ago

quadraticsievefactorization v1.0.78

Weekly downloads
-
License
-
Repository
github
Last release
8 months ago

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.

1.0.78

8 months ago

1.0.77

1 year ago

1.0.76

1 year ago

1.0.75

1 year ago

1.0.74

1 year ago

1.0.73

1 year ago

1.0.66

2 years ago

1.0.69

2 years ago

1.0.67

2 years ago

1.0.72

2 years ago

1.0.71

2 years ago

1.0.70

2 years ago

1.0.62

2 years ago

1.0.61

2 years ago

1.0.60

2 years ago

1.0.65

2 years ago

1.0.64

2 years ago

1.0.63

2 years ago

1.0.59

2 years ago

1.0.58

2 years ago

1.0.57

2 years ago

1.0.22

3 years ago

1.0.21

3 years ago

1.0.26

3 years ago

1.0.25

3 years ago

1.0.24

3 years ago

1.0.23

3 years ago

1.0.29

3 years ago

1.0.28

3 years ago

1.0.27

3 years ago

1.0.33

3 years ago

1.0.32

3 years ago

1.0.31

3 years ago

1.0.30

3 years ago

1.0.37

3 years ago

1.0.35

3 years ago

1.0.34

3 years ago

1.0.39

3 years ago

1.0.40

3 years ago

1.0.44

3 years ago

1.0.43

3 years ago

1.0.42

3 years ago

1.0.41

3 years ago

1.0.48

3 years ago

1.0.47

3 years ago

1.0.46

3 years ago

1.0.45

3 years ago

1.0.49

3 years ago

1.0.51

3 years ago

1.0.50

3 years ago

1.0.55

2 years ago

1.0.54

2 years ago

1.0.53

2 years ago

1.0.52

3 years ago

1.0.56

2 years ago

1.0.19

3 years ago

1.0.18

3 years ago

1.0.17

3 years ago

1.0.16

3 years ago

1.0.11

3 years ago

1.0.10

3 years ago

1.0.20

3 years ago

1.0.15

3 years ago

1.0.14

3 years ago

1.0.13

3 years ago

1.0.12

3 years ago

1.0.9

3 years ago

1.0.7

3 years ago

1.0.6

3 years ago

1.0.5

3 years ago

1.0.4

3 years ago

1.0.3

3 years ago

1.0.2

4 years ago

1.0.1

4 years ago

1.0.0

4 years ago