danДоклады Национальной академии наук БеларусиDoklady of the National Academy of Sciences of Belarus1561-83232524-2431The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"dan-453Research ArticleМАТЕМАТИКАMATHEMATICSАНАЛОГ ТЕСТА СОЛОВЕЯ–ШТРАССЕНА В КВАДРАТИЧНЫХ ЕВКЛИДОВЫХ КОЛЬЦАХANALOGUE OF THE SOLOVAY–STRASSEN PRIMALITY TEST IN QUADRATIC EUCLIDEAN DOMAINSВаськовскийМ. М.VaskouskiM. M.

доцент

пр. Независимости, 4, 220030

vaskovskii@bsu.byКондратёнокН. В.KondratyonokN. V.

студент

пр. Независимости, 4, 220030

nkondr2006@rambler.ruПрохоровН. П.ProchorovN. P.

студент

пр. Независимости, 4, 220030

nprohorovminsk@mail.ruБелорусский государственный университет, МинскBelarusian State University, Minsk2017171220176152832Copyright © Васьковский М.М., Кондратёнок Н.В., Прохоров Н.П., 20172017Васьковский М.М., Кондратёнок Н.В., Прохоров Н.П.Vaskouski M.M., Kondratyonok N.V., Prochorov N.P.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.belnauka.by/jour/article/view/453

В произвольных квадратичных евклидовых кольцах построен аналог теста Соловея–Штрассена. Доказано, что построенный аналог теста Соловея–Штрассена позволяет показать, что число N является составным с вероятностью не менее 0,5 за полиномиальное время относительно битовой длины числа N. В тесте Соловея– Штрассена ключевую роль играет вычисление символа Якоби. В работе построен эффективный алгоритм для его вычисления в квадратичных факториальных кольцах. Ключевой идеей доказательства является сведение символа Якоби в квадратичных факториальных кольцах к символу Якоби в целых числах. 

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. 

евклидово кольцопростые числасимвол Якобитест на простотуEuclidean domainprimesJacobi symbolprimality testReferencesКриптология / Ю. С. Харин [и др.]. – Минск: БГУ, 2013. – 511 с.Kharin Yu. S., Agievich S. V., Vasil’ev D. V., Matveev G. V. Cryptology. Minsk, Belarusian State University, 2013. 511 p. (in Russian).Введение в теоретико-числовые методы криптографии / М. М. Глухов [и др.]. – СПб.: Лань, 2011. – 401 с.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).Kranakis, E. Primality and cryptography / E. Kranakis. – New Haven: Yale University, 1986. – 235 p.Kranakis E. Primality and cryptography. New Haven, Yale University, 1986. 235 p.Vaskouski, M. Analogue of the RSA-cryptosystem in quadratic unique factorization domains / M. Vaskouski, N. Kondratyonok // Доклады Национальной академии наук Беларуси. – 2015. – Vol. 59, N 5. – P. 18–23.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).Vaskouski, M. Primes in quadratic unique factorization domains / M. Vaskouski, N. Kondratyonok, N. Prochorov // J. Number Theory. – 2016. – Vol. 168. – P. 101–116. doi.org/10.1016/j.jnt.2016.04.022Vaskouski 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Васьковский, М. М. Полиномиальная эквивалентность вычисления функции Эйлера RSA-модуля и поиска секретного ключа в квадратичных евклидовых кольцах / М. М. Васьковский // CSIST’16. Международный конгресс по информатике: Информационные системы и технологии: материалы международного конгресса. – Минск: БГУ, 2016. – С. 427–430.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).Lemmermeyer, F. Reciprocity laws: from Euler to Eisenstein / F. Lemmermeyer. – Springer, 2000. – 514 p.Lemmermeyer F. Reciprocity laws: from Euler to Eisenstein. Springer, 2000. 514 p.Vaskouski, M. Shortest division chains in unique factorization domains / M. Vaskouski, N. Kondratyonok // J. Symbolic Computation. – 2016. – Vol. 77. – P. 175–188. doi.org/10.1016/j.jsc.2016.02.003Vaskouski 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

The authors declare that there are no conflicts of interest present.