|
|
 |
| |
|
|
|
Improving AKS Algorithm. Proving the Simplicity of Integers |
|
|
|
PP: 13-20 |
|
|
|
doi:10.18576/amis/170103
|
|
|
|
Author(s) |
|
|
|
O. Kozachok,
|
|
|
|
Abstract |
|
|
| Agrawal-Kayal-Saxena (AKS) theorem was proved, from which the above-mentioned algorithm is directly derived. The study has shown that the problem of simplicity is in the complexity class P of polynomial problems. An advanced AKS algorithm is proposed, which will simplify the initial AKS algorithm and ensure its implementation to determine the simplicity of integers. To implement this task it is necessary to reduce algorithm computational complexity. The block diagram of the algorithm for performing the advanced AKS test is presented. The theorems for prime numbers presented in the form of polynomials were formulated and proved. The AKS algorithm consisting of two phases is implemented: at the first stage, the corresponding parameters r and s were found, and at the second stage, the identity for different values of b presented in the form of consecutive squares was checked. The adequacy of the algorithm for checking numbers for simplicity is proved by the example of a generated arbitrary number of 500 orders. Comparative characterization of the improved AKS test and the Miller-Rabin test was carried out. 50,000 tests were conducted. The maximum test time was 2.3089 s.
|
|
|
|
|
|
|
|
