Gozde Sarikaya, Informatics Institute, Istanbul Technical University
A Primality Test Algorithm
Prime numbers are the main ingredient of the cryptosystems such as RSA, Elliptic Curve
Cryptosystem etc. The critical aspect of RSA is the difficulty of factorization of large integers that have
several hundred digits. It is not always easy to construct such large integers with large prime factors
so that factoring is hard for these numbers. The first task is to determine the primality of an integer.
One of the primality test algorithms that is being used in practice, Miller Rabin test, guarantee
compositeness of most integers but it may fail to determine the compositeness of some. In this
work, we test a conjecture by S. Ling et.al which adds a single condition to strong pseudoprime test
to base 2. The test we conducted gives clues to pattern of strong pseudoprimes to base 2 and
explains why the strong pseudo prime test base 2 with the additional condition catches all
composite integers. We have been able to show that the test catches all composite integers to 10^20.
In this work, we explain the algorithm in details and present our observation of the computational
tests. The observation will show that why the conjectured primality test is actually a primality test.
The conjectured primality test has running time of O(log^2 n) and it uses singular cubics.