Factorize

A repository for factorizing large integers. The current implementation is the self-initializing quadratic sieve (SIQS). It uses the large prime variant for partial congruences, forgoes sieving with tiny primes (<256), stores basic ``resieved'' values for big primes (>sieve diameter), and uses the Block Wiedemann algorithm for linear dependency extraction.

This is written in C++ using the gmp library mpz for multiprecision arithmetic. The build is managed with make.

Sample Run

The following is a sample run of the main SIQS algorithm on the 330 bit RSA key RSA-100:

Sample usage

Generate empty build/ and obj/ directories:

make gen

Compile:

make

(Optional) Compile and generate compile_commands.json with bear:

bear -- make

Run:

make run

Test (basic util and gf2 functions):

make test