The AKS primality test is a reliable method for determining whether a given number N is prime or composite. It is a polynomial time algorithm with a predictable and efficient runtime, and has been rigorously proven to be accurate in all cases. If N is found to be composite using the AKS primality test, the number is then factored into its prime factorization using a combination of trial division, fermat's method, and the quadratic sieve. Trial division is used for small prime factors, the quadratic sieve is used for larger prime factors, and fermat's method is used for extreme cases.
Trial division is used for finding small prime factors, where N is divided by all possible prime factors up to its square root. For larger prime factors, the quadratic sieve works by sieving for integers that can be factored using a predetermined factor base. It then sets up a matrix using these integers and their corresponding congruences, and solves the matrix using linear algebra techniques to find a congruence of squares modulo N. This congruence can then be used to obtain a factorization of N. Finally, for extreme cases where the other methods are not efficient, fermat's method is used. This involves using the fermat's little theorem to quickly check for potential prime factors that would otherwise be challenging to find by the previous methods. By using these methods in combination, the prime factorization of N can be accurately and efficiently determined.
Features:
- Partially Parrellized Primality Test
- Factorization of Composites using Trial Division and Fermat's Method
To do:
- Fully implement QS and verify its correctness
C/C++, Pari GP, NTL, GMP, Gfx2 (not necessary)
Prerequisite: Build all dependencies from source from the links above
Below are some examples on how to interface with the program.
1.0. Compile the program
make clean; make cppversion2.1. Run main routine
./main2.2. Run against test file
./main first1000.txt