АНАЛОГ ТЕСТА СОЛОВЕЯ–ШТРАССЕНА В КВАДРАТИЧНЫХ ЕВКЛИДОВЫХ КОЛЬЦАХ
Аннотация
В произвольных квадратичных евклидовых кольцах построен аналог теста Соловея–Штрассена. Доказано, что построенный аналог теста Соловея–Штрассена позволяет показать, что число N является составным с вероятностью не менее 0,5 за полиномиальное время относительно битовой длины числа N. В тесте Соловея– Штрассена ключевую роль играет вычисление символа Якоби. В работе построен эффективный алгоритм для его вычисления в квадратичных факториальных кольцах. Ключевой идеей доказательства является сведение символа Якоби в квадратичных факториальных кольцах к символу Якоби в целых числах.
Об авторах
М. М. Васьковский
Белорусский государственный университет, Минск
Беларусь
Беларусь
доцент
пр. Независимости, 4, 220030
Н. В. Кондратёнок
Белорусский государственный университет, Минск
Беларусь
Беларусь
студент
пр. Независимости, 4, 220030
Н. П. Прохоров
Белорусский государственный университет, Минск
Беларусь
Беларусь
студент
пр. Независимости, 4, 220030
Список литературы
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
Рецензия
Просмотров: 771
Послать статью по эл. почте 