×

Analyzing the AKS algorithm and its improved algorithm in detail. (Chinese. English summary) Zbl 1220.11154

Summary: In 2002, M. Agrawal, N. Kayal and N. Saxena [Ann. Math. (2) 160, No. 2, 781–793 (2004; Zbl 1071.11070)] presented a remarkable algorithm (the AKS algorithm). It is the deterministic polynomial-time primality testing algorithm that determines whether an input number is prime or composite. After the AKS algorithm was developed, many researchers improved it. One of the better improvements is due to D. Bernstein (the Bernstein algorithm). In this paper, we analyze the two algorithms in detail and implement the two algorithms for some integers. We compare them using C programs and find the smallest prime number and composite number that are needed to use the AKS algorithm and the Bernstein algorithm and we show the predicted CPU time.

MSC:

11Y11 Primality
11A51 Factorization; primality

Citations:

Zbl 1071.11070
PDFBibTeX XMLCite