Home

Welcome to the primes wiki!

Setup

Add this as a dependency to your shard.yml file and run shards install:

  primes:
    github: dkhofer/primes
    branch: master

Then just add require "primes" to any file that needs to use it. Then you can do things like:

57.prime?
720.factorization

Command-line clients

To build binaries, just run make at the top level and they will be created in the bin/ directory.

$ make
mkdir -p ./bin
crystal build --release -o bin/cr-factor command-line/factor.cr
crystal build --release -o bin/is-prime command-line/is_prime.cr
$ bin/cr-factor 761838257287761838257287761838257337
761838257287761838257287761838257337: 7 43 47 3391 51613 2354873 130660417379158169
$ bin/is-prime 761838257287761838257287761838257339
true

The cr-factor program has times just a smidgen slower than GNU's factor program, at least on a mac laptop: http://www.gnu.org/software/coreutils/manual/html_node/factor-invocation.html

Factorization timings

Done on my laptop.

2^67 - 1 = 147573952589676412927:
[[193707721, 1], [761838257287, 1]]
14.74 seconds

2^256 + 1 = 115792089237316195423570985008687907853269984665640564039457584007913129639937:
[[1238926361552897, 1], [93461639715357977769163558199606896584051237541638188580280321, 1]]
40.27 seconds

Factoring algorithm

Details here: https://github.com/dkhofer/primes/wiki/Factorization-algorithm

TODO

Implement the following factorization algorithms:

• Williams's P + 1 method
• The elliptic curve method
• Quadratic sieve

Parallelize the parts of the factorization algorithm that can be.

Pull requests and bug reports welcome!