Self-Initializing Quadratic Sieve in Julia

New to Julia
26

Clone the repo and cd into julia directory.

 julia --project=.

help?> FlintQS
search: FlintQS flintqs

  FlintQS

  Julia port of William Hart's FlintQS: a self-initializing quadratic sieve with single large-prime merging and Block Lanczos linear algebra.

  Exports flintqs (full prime factorization) and siqs_split (one divisor of a ≥ 40-digit composite).
help?> flintqs
search: flintqs FlintQS

  flintqs(n; rng, verbose) -> Vector{BigInt}

  Prime factorization of n ≥ 1 as a sorted vector with multiplicity ([] for n == 1). Strips factors below 1000, reduces perfect powers, and splits
  the rest with Pollard rho (≤ 18 digits) or the self-initializing quadratic sieve.


help?> siqs_split
search: siqs_split Base.shell_split rsplit split eachsplit sincospi eachrsplit

  siqs_split(n; rng, verbose, accept) -> BigInt

  Return a nontrivial divisor of the composite n using the self-initializing quadratic sieve. n must have at least 40 decimal digits, no prime
  factor below 1000 and not be a perfect power. accept(d) filters which divisors may be returned (default: any); the search continues through the
  remaining dependencies, and further sieving, until one is accepted.

include("bench/bench.jl")
| digits | seconds | peak RSS (MB) |
|:--:|:--:|:--:|
| 40 | 0.08 | 401.0 |
| 45 | 0.24 | 416.0 |
| 50 | 0.63 | 475.0 |
| 55 | 1.17 | 556.0 |
| 60 | 3.21 | 842.0 |

That pretty much it.