Доступ открыт Открытый доступ  Доступ закрыт Только для подписчиков

АНАЛОГ ТЕСТА СОЛОВЕЯ–ШТРАССЕНА В КВАДРАТИЧНЫХ ЕВКЛИДОВЫХ КОЛЬЦАХ (Представлено академиком Н. А. Изобовым)

Полный текст:


Аннотация

В произвольных квадратичных евклидовых кольцах построен аналог теста Соловея–Штрассена. Доказано, что построенный аналог теста Соловея–Штрассена позволяет показать, что число 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


Дополнительные файлы

Просмотров: 18

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.

ISSN 1561-8323 (Print)