University of Bath Computer Science MSc. Dissertation Project

On the implementation of the AKS algorithm in CUDA

An implementation of the Lenstra variant of the AKS primality test and a further, unimplemented variant suggestion from Crandall & Papadopoulos (2003).

Stages of Development

• Review and validate (respectively) previous implementations from:
  • Gallot
  • Hua Li - Lenstra/$Z_n(x)$ version
• Implement Lenstra/$Z_n(x)$ version as GPU accelerated versions in CUDA C++ for deployment on a GEFORCE RTX 3090 GPU cloud.
• Develop $Z_n$ version from Crandall & Papadopoulos (2003)
• Optimise above implementation, using MIRACL or NTL

Other information

Personal System Specifications for home benchmarking purposes:

• Eight-core AMD Ryzen 7 4700U, 8GB RAM
• Dual-core Intel(R) Pentium(R) CPU G860 @ 3.00GHz, 16GB DDR3 RAM @ 1333MHz, Radeon HD 7770 GPU

Local Setup

1. Download and install GMP
2. Download and install the Number Theory Library

Running

1. Compile the program with:

   g++ -g -O2 -std=c++11 -pthread -march=native devVR/LenstraZnx.cpp -o devVR/LenstraZnx.out -lntl -lgmp -lm

2. Run the program with:

   ./devVR/LenstraZnx.out