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