Primality Testing Using Complex Integers and Pythagorean Triplets

Boris Verkhovsky

Computer Science Department, New Jersey Institute of Technology, Newark, USA.

DOI: 10.4236/ijcns.2012.59062                

Abstract

Prime integers and their generalizations play important roles in protocols for secure transmission of information via open channels of telecommunication networks. Generation of multidigit large primes in the design stage of a cryptographic system is a formidable task. Fermat primality checking is one of the simplest of all tests. Unfortunately, there are composite integers (called Carmichael numbers) that are not detectable by the Fermat test. In this paper we consider modular arithmetic based on complex integers; and provide several tests that verify the primality of real integers. Although the new tests detect most Carmichael numbers, there are a small percentage of them that escape these tests.

Keywords

Cryptosystem Design; Primality Testing; Fermat Test; Pythagorean Triplet; Strong Carmichael Number; Quaternions

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	L. M. Adleman, C. Pomerance and R. S. Rumley, “On Distinguishing Prime Numbers from Composite Numbers”, The Annals of Mathematics, Vol. 117, No. 1, 1983, pp. 173-206. doi:10.2307/2006975
[2]	C. Pomerance, “Paul Erdos, Number Theorist Extraordinaire”, The Notices of the American Mathematical Society, Vol. 45, 1998, pp. 19-23.
[3]	B. Verkhovsky, “Multiplicative Inverse Algorithm and Its Space Complexity”, Annals of European Academy of Sciences, Vol. 2, 2004, pp. 110-124.
[4]	M. Agrawal, N. Kayal and N. Saxena, “PRIMES Is in P”, The Annals of Mathematics, Vol. 160, No. 2, 2002, pp. 781-793.
[5]	W. R. Alford, A. Granville and C. Pomerance, “There Are Infinitely Many Carmichael Numbers”, The Annals of Mathematics, Vol. 140, No. 3, 1994, pp. 703-722.
[6]	C. F. Gauss, “Disquisitiones Arithmeticae”, Yale University Press, New Haven, 1986.
[7]	T. ElGamal, “A Public Key Cryptosystem and a Signature Scheme Based on Discrete Log-Arithmetic”, IEEE Transactions on Information Theory, Vol. 31, No. 4, 1985, pp. 469-472. doi:10.2307/2006975
[8]	N. Koblitz, A. Menezes and S. Vanstone, “The State of Elliptic Curve Cryptography”, Designs, Codes and Cryptography, Vol. 19, No. 2-3, 2000, pp. 173-193. doi:10.1023/A:1008354106356
[9]	E. Gethner, S. Wagon and B. Wick, “A Stroll through the Gaussian Primes”, American Mathematics Monthly, Vol. 105, No. 4, 1998, pp. 327-337. doi:10.2307/2589708
[10]	B. Verkhovsky, “Double-Moduli Gaussian Encryption/Decryption with Primary Residues and Secret Controls”, International Journal of Communications, Network and System Sciences, Vol. 4, No. 7, 2011, pp. 475-481. doi:10.4236/ijcns.2011.47058
[11]	A. Karatsuba and Yu. Ofman, “Multiplication of Multi- Digit Numbers on Automata”, Soviet Physics Doklady, Vol. 7, 1963, pp. 595-596.
[12]	D. Knuth, “The Art of Computer Programming, Vol. 1: Fundamental Algorithms”, 2d Edition, Addison-Wesley, Boston, 1973.
[13]	B. Verkhovsky, “Hardness of Cryptanalysis of Public Keys Crypto-Systems with Known Timing of Modular Exponentiation”, Advances in Computer Cybernetics, Vol. 6, 1998, pp. 80-84.
[14]	B. Verkhovsky, “Space Complexity of Algorithm for Modular Multiplicative Inverse”, International Journal of Communications, Network and System Sciences, Vol. 4, No. 6, 2011, pp. 357-363. doi:10.4236/ijcns.2011.46041
[15]	R. D. Carmichael, “Note on a New Number Theory Function”, Bulletin of American Mathematical Society, Vol. 16, No. 5, 1910, pp. 232-238. doi:10.1090/S0002-9904-1910-01892-9
[16]	R. G. E. Pinch, “The Carmichael Numbers up to 1015”, Mathematics of Computation, Vol. 61, 1993, pp. 381-391.
[17]	H. Dubner, “A New Method for Producing Large Carmichael Numbers”, Mathematics of Computation, Vol. 53, 1989, pp. 411-414. doi:10.1090/S0025-5718-1989-0969484-8
[18]	B. Verkhovsky and A. Mutovic, “Primality Testing Algorithm Using Pythagorean Integers”, Proceedings of International Computer Science and Information Systems Conference, Athens, June 2005.