The analysis and implementation of the AKS algorithm and its improvement algorithms
H Li · The University of Bath Online Publications Store (The University of Bath) · 2007
In August 2002, three Indian researchers, Manindra Agrawal and his students Neeraj Kayal and Nitin Saxena presented a remarkable algorithm called AKS algorithm in their paper Primes is in P. It is the first deterministic primality testing algorithm in polynomial time.The project provides experimental data to suggest the complexity time of AKS algorithm is O((log n) 8 log log n).Afterwards, many scientists tried to improve the AKS algorithm, one of the better ones is proposed by Lenstra.R. Crandall and J. Papadopoulos has shown that Lenstras version of the AKS algorithm has a complexity time of C(log n) 6 where C is a logarithm constant.Our testing supports this result and suggest C can be approximate bywhere r is the useful certificate.Further testing results have shown a better complexity time O(log n) 5.73 for lenstra's version.v B.2.9 Output results for Fig. 6.7 . . . . . . . . . . . . . . . . . . . . . . .B.2.10 Output results for Fig. 6.8 . . . . . . . . .