This is repository containing all the codes and plots made for experimenting and rediscovering the Miller Rabin Algorithm for primality testing.
This was done as a course project for CS648 (Randomized Algorithms) course at the Indian Institute of Technology Kanpur
- Sankalp Mittal
- Debraj Karmakar
- Naman Kumar Jaiswal
All the .cpp codes in this repository are written using the gmp.h and gmpxx.h C++ library and require a linux environment to run. This is done to handle large numbers and to test how does the code perform as the input size increases
To install the library in Ubuntu/Debian follow these steps
sudo apt update
sudo apt install libgmp-dev
To install in Fedora
sudo dnf install gmp-devel
To compile the .cpp file using this run the following command
g++ -o $(file_name) $(file_name).cpp -lgmp
and run it as
./$(file_name)
The repository has been organized on the following basis
- Applications: This contains a jupyter notebook containing the implementation of primality testing and its usage in some applications
- Basic Analysis: This contains some jupyter notebooks analysing Fermat's Theorem
- data: This contains the data generated from various experiments
- plots: This contains the various plots generated as a result of the experiments
- PlottingCodes: This contains the python scripts used to plot the graphs from the data
- PrimalityTestingCodes: This contaings the codes for primality testing and the various experiments done
The following github repository was used to implement the AKS Primality test