АНАЛОГ ТЕСТА СОЛОВЕЯ–ШТРАССЕНА В КВАДРАТИЧНЫХ ЕВКЛИДОВЫХ КОЛЬЦАХ
Анатацыя
В произвольных квадратичных евклидовых кольцах построен аналог теста Соловея–Штрассена. Доказано, что построенный аналог теста Соловея–Штрассена позволяет показать, что число N является составным с вероятностью не менее 0,5 за полиномиальное время относительно битовой длины числа N. В тесте Соловея– Штрассена ключевую роль играет вычисление символа Якоби. В работе построен эффективный алгоритм для его вычисления в квадратичных факториальных кольцах. Ключевой идеей доказательства является сведение символа Якоби в квадратичных факториальных кольцах к символу Якоби в целых числах.
Аб аўтарах
М. Васьковский
Белорусский государственный университет, Минск
Беларусь
Беларусь
Н. Кондратёнок
Белорусский государственный университет, Минск
Беларусь
Беларусь
Н. Прохоров
Белорусский государственный университет, Минск
Беларусь
Беларусь
Спіс літаратуры
1. Криптология / Ю. С. Харин [и др.]. – Минск: БГУ, 2013. – 511 с.
2. Введение в теоретико-числовые методы криптографии / М. М. Глухов [и др.]. – СПб.: Лань, 2011. – 401 с.
3. Kranakis, E. Primality and cryptography / E. Kranakis. – New Haven: Yale University, 1986. – 235 p.
4. Vaskouski, M. Analogue of the RSA-cryptosystem in quadratic unique factorization domains / M. Vaskouski, N. Kondratyonok // Доклады Национальной академии наук Беларуси. – 2015. – Vol. 59, N 5. – P. 18–23.
5. 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.022
6. Васьковский, М. М. Полиномиальная эквивалентность вычисления функции Эйлера RSA-модуля и поиска секретного ключа в квадратичных евклидовых кольцах / М. М. Васьковский // CSIST’16. Международный конгресс по информатике: Информационные системы и технологии: материалы международного конгресса. – Минск: БГУ, 2016. – С. 427–430.
7. Lemmermeyer, F. Reciprocity laws: from Euler to Eisenstein / F. Lemmermeyer. – Springer, 2000. – 514 p.
8. 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.003
##reviewer.review.form##
Праглядаў: 783
Паслаць артыкул па эл. пошце 