IJCNS  Vol.5 No.9 , September 2012
Primality Testing Using Complex Integers and Pythagorean Triplets
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.
Cite this paper: B. Verkhovsky, "Primality Testing Using Complex Integers and Pythagorean Triplets," International Journal of Communications, Network and System Sciences, Vol. 5 No. 9, 2012, pp. 513-519. doi: 10.4236/ijcns.2012.59062.

[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.