MPI Implementation of AKS Algorithm

Abstract—AKS algorithm is the first deterministic polynomial time algorithm for primality proving. This project uses MPI (Message Passing Interface) along with GNU MP (Multi Pre-cision) library to implement a variant of AKS algorithm. Two different parallelization strategies have been implemented and we compare these strategies making relevant observations and pro-viding speedups. The method of fast polynomial exponentiation with precomputation has been used to achieve parallelization and improve run time. Further we show experimentally that master slave model of parallelization gives very good results. I