Gozde Sarikaya, Informatics Institute, Istanbul Technical University

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.