Enver Ozdemir & Gözde Sarikaya: A Novel 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.

Computationally Assisted Mathematical Discovery
and Experimental Mathematics: ACMES 2
12-15 May 2016, London, Ontario, Canada

Enver Ozdemir & Gözde Sarikaya, Informatics Institute, Istanbul Technical University
May 15, 2016

Visit the Rotman website for more information on applications, events, project descriptions and openings. http://www.rotman.uwo.ca

Follow The Rotman Institute on Twitter: https://twitter.com/rotmanphilo

Like The Rotman Institute on Facebook: https://www.facebook.com/rotmanphilosophy

Subscribe to our channel: https://www.youtube.com/user/rotmanphilosophy