ANALOGUE OF THE SOLOVAY–STRASSEN PRIMALITY TEST IN QUADRATIC EUCLIDEAN DOMAINS
Abstract
An analogue of the Solovay–Strassen primality test in general quadratic Euclidean domains is obtained. We prove that the obtained primality test allows us to prove that N is composite and has a probability of no less than 0.5 in polynomial time with respect to a bit size of the number N. The main part of the Solovay-Strassen primality test analogue is the calculation of the Jacobi symbol. The efficient algorithm for its computing in quadratic unique factorization domains is constructed. The main idea of the proof is to reduce the Jacobi symbol to that in integers.
About the Authors
M. M. Vaskouski
Belarusian State University, Minsk
Belarus
Belarus
N. V. Kondratyonok
Belarusian State University, Minsk
Belarus
Belarus
N. P. Prochorov
Belarusian State University, Minsk
Belarus
Belarus
References
1. Kharin Yu. S., Agievich S. V., Vasil’ev D. V., Matveev G. V. Cryptology. Minsk, Belarusian State University, 2013. 511 p. (in Russian).
2. Glukhov M. M., Kruglov I. A., Pichkur A. B., Cheremushkin A. V. Introduction to number theoretical methods in cryptography. Saint-Petersburg, Lan’ Publ., 2011. 401 p. (in Russian).
3. Kranakis E. Primality and cryptography. New Haven, Yale University, 1986. 235 p.
4. Vaskouski M., Kondratyonok N. Analogue of the RSA-cryptosystem in quadratic unique factorization domains. Doklady Natsional’noi akademii nauk Belarusi = Doklady of the National Academy of Sciences of Belarus, 2015, vol. 59, no. 5, pp. 18–23. (in Russian).
5. Vaskouski M., Kondratyonok N., Prochorov N. Primes in quadratic unique factorization domains. Journal of Number Theory, 2016, vol. 168, pp. 101–116. doi.org/10.1016/j.jnt.2016.04.022
6. Vaskouski M. M. Polynomial equivalence of computing Euler’s function from RSA modulus and searching for private key in Euclidean quadriatic domains. CSIST’16. Mezhdunarodnyi kongress po informatike: Informatsionnye sistemy i tekhnologii: materialy mezhdunarodnogo kongressa [CSIST’16. International congress on computer science: information systems and technologies: Proceedings of the International Scientific Congress]. Minsk, Belarusian State University, 2016, pp. 427–430 (in Russian).
7. Lemmermeyer F. Reciprocity laws: from Euler to Eisenstein. Springer, 2000. 514 p.
8. Vaskouski M., Kondratyonok N. Shortest division chains in unique factorization domains. Journal of Symbolic Computation, 2016, vol. 77, pp. 175–188. doi.org/10.1016/j.jsc.2016.02.003
Review
Views: 785
Email this article 