| Abstrakt: | In the text we investigate the AKS test, the choices of the parameters of the congruence used in this test, as well as the Agrawal's conjecture leading to the speed-up of the algorithm. We show that for some choices of parameter $r$, the Carmichael numbers are passing for all choices of the parameter $a$, providing two different proofs of this fact. We demonstrate that if the widely believed Sophie-Germain primes conjecture is true, there is another infinite class of composite numbers satisfying the congruence. Further we present the heuristic of Lenstra and Pomerance as a potential way of the disproof of the Agrawal's conjecture. We give an alternative proof of it, along with the algorithm derived from a method used in this proof. We use the matrix approach to generalize a known result about the relationship between Fibonacci pseudoprimes and AKS congruence. Finally we present the empiric results contributing to the intuition about the size and existence of the counterexample to the Agrawal's conjecture.
|
|---|