Research ArticleOpen AccessGoogle Scholar indexed
Primality Testing Using Complex Integers and Pythagorean Triplets
Computer Science Department, New Jersey Institute of Technology, Newark, USA
- 1 Computer Science Department, New Jersey Institute of Technology, Newark, USA
International Journal of Communications, Network and System Sciences·Volume 05 (2012)·Pages 513–519·Published 18 September 2012·DOI10.4236/ijcns.2012.59062
Copy link · social · email
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.
KeywordsCryptosystem DesignPrimality TestingFermat TestPythagorean TripletStrong Carmichael NumberQuaternions
- 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
- C. Pomerance, “Paul Erdos, Number Theorist Extraordinaire”, The Notices of the American Mathematical Society, Vol. 45, 1998, pp. 19-23.
- B. Verkhovsky, “Multiplicative Inverse Algorithm and Its Space Complexity”, Annals of European Academy of Sciences, Vol. 2, 2004, pp. 110-124.
- M. Agrawal, N. Kayal and N. Saxena, “PRIMES Is in P”, The Annals of Mathematics, Vol. 160, No. 2, 2002, pp. 781-793.
- 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.
- C. F. Gauss, “Disquisitiones Arithmeticae”, Yale University Press, New Haven, 1986.
- 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
- 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
- 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
- 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
- A. Karatsuba and Yu. Ofman, “Multiplication of Multi- Digit Numbers on Automata”, Soviet Physics Doklady, Vol. 7, 1963, pp. 595-596.
- D. Knuth, “The Art of Computer Programming, Vol. 1: Fundamental Algorithms”, 2d Edition, Addison-Wesley, Boston, 1973.
- 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.
- 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