Implementations of ECPP, AKS, and a hybrid of the two Final Project for Suresh Venkatasubramanian's Advanced Algorithms (CS 6150) course at Utah Members: Ryan Lindeman, Steven Lyde, Phillip Mates For more details please see the corresponding final report: report.pdf Compile Instructions: make Run Instructions: There are several programs provided. The primary one is compiled as "run". For program usage information type the following in a CADE lab terminal window: ./run -h You can also run our AKS and Miller-Rabin implementations separately as shown: ./aks ./miller-rabin The Miller-Rabin outputs a 0 for composite numbers, a 1 for probably prime numbers and a 2 for proven prime numbers. There is also the "gprime" program that can generate prime numbers of arbitrary size that uses the Miller-Rabbin implementation. The "run" program is capable of printing certificates as shown: ./run -c < file-with-one-number-per-line The "run" program has a self-test mode that will continually run testing every prime greater than or equal to 4294967279 ./run -t For additional information, see the usage page for the "run" program or the Background information below. Background: The "run" program is a combination of multiple algorithms: AKS, ECPP, and Miller-Rabin. The primary programs are Miller-Rabin and ECPP with a fallback option to AKS. The program has multiple modes of operation as mentioned above. If the ECPP algorithm fails to find the number prime it will run the AKS algorithm to finish the job. Running times for decimal digit numbers of 170 or less typically take under 10 minutes with a few exceptions. The program should be able to compute numbers of any size reasonably quickly. Smaller numbers tend to run the AKS algorithm more frequently than larger numbers.
philomates/ecpp-aks-primality-proving
3 Primality Proving Implementations: ECPP, AKS, and a hybrid of the two
C++MIT