Protection of Sensitive Messages Based on Quadratic Roots of Gaussians: Groups with Complex Modulus

Boris S. Verkhovsky

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

DOI: 10.4236/ijcns.2011.45033                

Abstract

This paper considers three algorithms for the extraction of square roots of complex integers {called Gaussians} using arithmetic based on complex modulus p + iq. These algorithms are almost twice as fast as the analogous algorithms extracting square roots of either real or complex integers in arithmetic based on modulus p, where is a real prime. A cryptographic system based on these algorithms is provided in this paper. A procedure reducing the computational complexity is described as well. Main results are explained in several numeric illustrations.

Keywords

Complex Modulus; Computational Efficiency; Cryptographic Algorithm; Digital Isotopes; Multiplicative Control Parameter; Octadic Roots, Quartic Roots, Rabin Algorithm, Reduction of Complexity, Resolventa, Secure Communication, Square Roots

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	C. F. Gauss, “Theoria Residuorum Biquadraticorum,” 2nd Edition, Chelsea, New York, 1965, pp. 534-586.
[2]	M. Kirsch, “Tutorial on Gaussian Arithmetic Based on Complex Modulus,” 2008. http://wlym.com/~animations/ceres/index.html
[3]	B. Verkhovsky, “Information Protection Based on Extraction of Square Roots of Gaussian Integers,” International Journal of Communications, Network and System Sciences, Vol. 4, No. 3, 2011, pp. 133-138. doi:10.4236/ijcns.2011.43016
[4]	B. Verkhovsky and A. Koval, “Cryptosystem Based on Extraction of Square Roots of Complex Integers,” In: S. Latifi, Ed., Proceedings of 5th International Conference on Information Technology: New Generations, Las Vegas, 7-9 April 2008, pp. 1190-1191.
[5]	E. Bach and J. Shallit, “Efficient Algorithm,” Algorithmic Number Theory, Vol. 1, MIT Press, Cambridge, MA, 1996.
[6]	R. Crandall and C. Pomerance, “Prime Numbers: A computational Perspective,” Springer, New York, 2001.
[7]	R. Schoof, “Elliptic Curves over Finite Fields and the Computation of Square Roots Mod p,” Mathematics of Computation, Vol. 44, No. 170, 1985, pp. 483-494.
[8]	R. V. Churchill, J. W. Brown and R. F. Verhey, “Complex Variables and Applications,” 3rd Edition, McGraw Hill, New York, 1976.
[9]	B. Verkhovsky, “Cubic Root Extractors of Gaussian Integers and Their Application in Fast Encryption for Time-Constrained Secure Communication,” International Journal of Communications, Network and System Sciences, Vol. 4, No. 4, 2011, pp. 197-204. doi:10.4236/ijcns.2011.44024
[10]	M. Rabin, “Digitized Signatures and Public-Key Functions as Intractable as Factorization,” MIT/LCS Technical Report, TR-212, 1979.