Implementations Of Two Improved Versions Of The AKS Primality Testing Algorithm

Primality testing is one of the central subjects in computational num-ber theory. In August 2002, Agrawal, Kayal and Saxena constructed a polynomialtime deterministic primality testing algorithm (called AKS algorithm). It's a theo-retical breakthrough, but it is not yet suitable for use in practice. Bernstein firstlypresented a good improvement (called the first AKS-Bernstein algorithm). ZhuWenyu implemented the above two algorithms on a PC, testing 3640471 with AKSalgorithm and 4295884871 with the first AKS-Bernstein algorithm in about 2478.94hours and 28.35 hours respectively. She concluded that it's almost impossible tojudge the primality of a given integer directly with AKS algorithm, and testifiedthat the first AKS-Bernstein algorithm improves the AKS algorithm, but it's notyet suitable for use in practice, either. Almost at the same time, Berrizbeitia pro-posed a variant of the AKS algorithm (called AKS-Berrizbeitia algorithm), whichis a deterministic primality test for a large family of integers. Later, Bernstein alsogave an improved version of the AKS algorithm for proving primality in essentiallyquartic random time (called the second AKS-Bernstein algorithm), which is moregeneral than AKS-Berrizbeitia algorithm.In this paper, we first describe our implementation of the AKS-Berrizbeitiaalgorithm on a PC Pentium IV/1.8G with Delphi-Pascal language, testing integerswhich have only 5 digits in about 2 hours. This means that the AKS-Berrizbeitiaalgorithm remains unsuitable for use in practice. Then, for practical purposes,we consider the only interesting case of the second AKS-Bernstein algorithm andimplement it. For all above integers, it only takes several seconds, and even for someintegers which have 15 digits and 41 digits, it can finish testing in 3 minutes and10 hours respectively. Together with the comparisons of computational operationsin above four algorithms, we conclude that the second AKS-Bernstein algorithmtruly improves the earlier versions of the AKS a lot. At last, by analyzing defectsof the second AKS-Bernstein algorithm and transversely comparing the practicale?ciency between the second AKS-Bernstein algorithm and the test which is acombination of several Miller tests, we realize that the later runs thousands oftimes faster than the former when the tested integers has about 15 digits and sothat the second AKS-Bernstein algorithm and its implementation should be furtherimproved. Meanwhile, we realize that the research of the deterministic test whichis a combination of several Miller tests is very meaningful in practice.