Generally Grouped Integer Model Based On Sequential Modular Arithmetic For Primality Testing Followed By Constant Time Factorization

Abstract

While primality testing and factorization are mathematically interrelated in principle, they are very different computationally in the algorithm with the time complexity. The most efficient primality test algorithm to be concurrently general, unconditional, deterministic and polynomial is known to be AKS primality test. But no factorization algorithm except for quantum computing like the Shor’s algorithm has been published that can factor all integers in polynomial time. The fastest prime factorization algorithm for a large number is the general number field sieve (GNFS) with sub-exponential time complexity, which usually takes too much longer time than AKS primality test algorithm. In this paper a new Generally Grouped Integer Model (GGIM) based on sequential modular arithmetic is proposed. This proposed methodology is a unified single algorithm for primality test and subsequent factorization, which is concurrently general, unconditional and deterministic. Moreover factorization takes constant time additionally just after a given integer is proved to be composite through primality test. This paper is anticipated to be a starting point for more sophisticated studies on optimization of the time complexity of primality testing based on the proposed model. It is hoped that a new approach proposed in this paper may shed some light on what is really a very difficult subject, polynomial primality test with subsequent constant time factorization, not solved for long time.