Об оценках сложности алгоритмов извлечения квадратных корней в конечных полях и кольцах вычетов

  • Сергей [Sergey] Борисович [B.] Гашков [Gashkov]
  • Александр [Aleksandr] Борисович [B.] Фролов [Frolov]
  • Елизавета [Elizaveta] Петровна [P.] Попова [Popova]
Ключевые слова: конечное поле, кольцо вычетов, извлечение квадратного корня, квадратный корень по модулю простого числа, квадратный корень по модулю степени простого числа, подъем решений, оценка сложности алгоритма

Аннотация

Представлен обзор известных алгоритмов извлечения квадратных корней из квадратичных вычетов по простому модулю и модулю степени простого числа, используемых посредством китайской теоремы об остатках для вычисления квадратных корней по любому числовому модулю. К ним относятся вероятностные алгоритмы Тонелли и Чиполлы и детерминированные алгоритмы для вычисления квадратных корней из квадратичных вычетов в кольцах вычетов по простому модулю, не сравнимому с единицей по модулю 8, а также строящиеся на их основе алгоритмы извлечения квадратного корня по модулю, равному степени простого числа. Приведены новые алгоритмы извлечения квадратных корней в полях характеристики, сравнимой с тройкой по модулю 4, и квадратных корней из вычетов, сравнимых с единицей по модулю 8, в кольцах вычетов по модулю степени двойки. Для вероятностных алгоритмов даны оценки сложности и вероятности успешного выполнения при первой попытке. Рассмотрена задача извлечения квадратных корней, встречающаяся в теоретико-числовых алгоритмах криптографии, используемых в сочетании с китайской теоремой об остатках для извлечения квадратного корня в кольцах вычетов по произвольному модулю. Показаны известные вероятностные и детерминированные алгоритмы извлечения квадратных корней по модулю простого числа и оценки их сложности и вероятности успешного завершения с первой попытки. Обоснованы новые находящие применение в эллиптической криптографии алгоритмы извлечения квадратных корней в полях характеристики, сравнимой с 3 по модулю 4, с оценками сложности. Изучены алгоритмы извлечения квадратных корней в полях четного порядка также с оценками сложности. Продемонстрированы алгоритмы извлечения квадратных корней из квадратичных вычетов в кольцах по модулю степени нечетного простого числа и по модулю степени двойки.

Сведения об авторах

Сергей [Sergey] Борисович [B.] Гашков [Gashkov]

Учёная степень:

доктор физико-математических наук

Место работы

кафедра Дискретной математики Московского государственного университета им. М. В. Ломоносова

Должность

профессор

Александр [Aleksandr] Борисович [B.] Фролов [Frolov]

Учёная степень:

доктор технических наук

Место работы

кафедра Математического моделирования НИУ «МЭИ»

Должность

профессор

Елизавета [Elizaveta] Петровна [P.] Попова [Popova]

Место работы

институт Автоматики и вычислительной техники НИУ «МЭИ»

Должность

студентка

Литература

1. Коблиц Н. Курс теории чисел и криптографии. М.: Науч. Изд-во НТП, 2001.

2. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии. Изд-во МЦНМО, 2003.

3. Глухов М.М., Круглов И.А., Пичкур А.Б., Черемушкин А.В. Введение в теоретико-числовые методы криптографии. СПб. — М. — Краснодар: Изд-во Лань, 2011.

4. Болотов А.А., Гашков С.Б., Фролов А.Б. Часовских А.А. Элементарное введение в эллиптическую криптографию. Кн. 1. Алгебраические и алгоритмические основы. М.: Изд-во Ленанд, 2019.

5. Кредалл Р., Померанс К. Простые числа. Криптографические и вычислительные аспекты. М.: Изд-во «Книжный дом «Либерком», 2011.

6. Венбо Мао. Современная криптография. М.: Издат. дом Вильямс, 2005.

7. Furer M. Faster Integer Multiplication // SIAM J. Computing. 2009. Iss. 3. V. 39. Pр. 979—1005.

8. Saha A., C., Kurur P., Saptharishi R. Fast Integer Multiplication Using Modular Arithmetic // SIAM J. Computing. 2013. Iss. 2. V. 42. Pp. 685—699.

9. Harvey D., van der Hoeven J., Lecerf G. Even Faster Integer Multiplication // J. Complexity. 2016. V. 36. Pp. 1—30.

10. Covanov S., Thome E. Fast Integer Multiplication Using Generalized Fermat Primes // J. Mathematics of Computation. 2016. V. 1. Pp. 1—27.

11. Bernstein D.J. Chuengsatiansup C., Lange T. Curve41417:Karatsuba Revisited // Proc. Cryptographic Hardware and Embedded Systems. 2014. Pp. 316—334.

12. Bach E. Explicit Bounds for Primality Testing and Related Problems // Math.Comp.1989. No. 55. Pp. 355—380.

13. Harvey D.,van der Hoeven J., Lecerf G. Faster Polynomial Multiplication Over Finite Fields // ArXive. arXiv:1407.3361. 2014.

14. Гашков С.Б., Сергеев И.С. О сложности и глубине булевых схем для умножения и инвертирования в конечных полях характеристики два // Дискретная математика. 2013. № 1 (25). С. 3—32.

15. Bernstein D.J. Batch Binary Edwards // Proc. Crypto — 2009. 2009. Pp. 317—336.

16. Bach E. A Note to Square Roots in Finite Fields // IEEE Trans. Inform. Theory. 1990. No. 36. Pp. 1494—1498.

17. Гашков С.Б., Сергеев И.С. О сложности и глубине булевых схем для умножения и инвертирования в некоторых полях // Вестник МГУ. Серия «Математика. Механика». 2009. № 4. С. 3—7.

18. Гашков С.Б., Сергеев И.С. О применении метода аддитивных цепочек для инвертирования в конечных полях // Дискретная математика. 2006. № 4 (18). С. 56—72.

19. Гашков С.Б., Сергеев И.С. Сложность вычислений в конечных полях // Фундаментальная и прикладная математика. 2012. № 4 (17). С. 95—131.

20. Umans C. Fast Polynomial Factorization and Modular Composition in Small Characteristic // Proc. 40 th Symp. Theory of Computing. 2008. Pp. 481—490.

21. Ahmadi O., Hankerson D., Menezes A. Formulas for Cube Roots // Discrete Appl. Math. 2007. V. 155 (3). Pp. 260—270.
---
Для цитирования: Гашков С.Б., Фролов А.Б., Попова Е.П. Об оценках сложности алгоритмов извлечения квадратных корней в конечных полях и кольцах вычетов // Вестник МЭИ. 2018. № 5. С. 79—88. DOI: 10.24160/1993-6982-2018-5-79-88.
#
1. Koblits N. Kurs Teorii Chisel i Kriptografii. M.: Nauch. Izd-vo NTP, 2001. (in Russian).

2. Vasilenko O.N. Teoretiko-chislovye Algoritmy v Kriptografii. Izd-vo MTSNMO, 2003. (in Russian).

3. Glukhov M.M., Kruglov I.A., Pichkur A.B., Cheremushkin A.V. Vvedenie v Teoretiko-chislovye Metody Kriptografii. SPb. — M. — Krasnodar: Izd-vo Lan', 2011. (in Russian).

4. Bolotov A.A., Gashkov S.B., Frolov A.B. Chasovskikh A.A. Elementarnoe Vvedenie v Ellipticheskuyu Kriptografiyu. Kn. 1. Algebraicheskie i Algoritmicheskie Osnovy. M.: Izd-vo Lenand, 2019. (in Russian).

5. Kredall R., Pomerans K. Prostye Chisla. Kriptograficheskie i Vychislitel'nye Aspekty. M.: Izd-vo «Knizhnyy Dom «Liberkom», 2011. (in Russian).

6. Venbo Mao. Sovremennaya Kriptografiya. M.: Izdat. Dom Vil'yams, 2005. (in Russian).

7. Furer M. Faster Integer Multiplication. SIAM J. Computing. 2009;3;39:979—1005.

8. Saha A., C., Kurur P., Saptharishi R. Fast Integer Multiplication Using Modular Arithmetic. SIAM J. Computing. 2013;2;42:685—699.

9. Harvey D., van der Hoeven J., Lecerf G. Even Faster Integer Multiplication. J. Complexity. 2016;36: 1—30.

10. Covanov S., Thome E. Fast Integer Multiplication Using Generalized Fermat Primes. J. Mathematics of Computation. 2016;1:1—27.

11. Bernstein D.J. Chuengsatiansup C., Lange T. Curve41417:Karatsuba Revisited. Proc. Cryptographic Hardware and Embedded Systems. 2014:316—334.

12. Bach E. Explicit Bounds for Primality Testing and Related Problems. Math.Comp.1989;55:355—380.

13. Harvey D.,van der Hoeven J., Lecerf G. Faster Polynomial Multiplication Over Finite Fields. ArXive. arXiv:1407.3361. 2014.

14. Gashkov S.B., Sergeev I.S. O Slozhnosti i Glubine Bulevykh Skhem dlya Umnozheniya i Invertirovaniya v Konechnykh Polyakh Kharakteristiki Dva. Diskretnaya Matematika. 2013;1 (25):3—32. (in Russian).

15. Bernstein D.J. Batch Binary Edwards. Proc. Crypto — 2009. 2009:317—336.

16. Bach E. A Note to Square Roots in Finite Fields. IEEE Trans. Inform. Theory. 1990;36:1494—1498.

17. Gashkov S.B., Sergeev I.S. O Slozhnosti i Glubine Bulevykh Skhem dlya Umnozheniya i Invertirovaniya v Nekotorykh Polyakh. Vestnik MGU. Seriya «Matematika. Mekhanika». 2009;4:3—7. (in Russian).

18. Gashkov S.B., Sergeev I.S. O Primenenii Metoda Additivnykh Tsepochek dlya Invertirovaniya v Konechnykh Polyakh. Diskretnaya Matematika. 2006;4 (18): 56—72. (in Russian).

19. Gashkov S.B., Sergeev I.S. Slozhnost' Vychisleniy v Konechnykh Polyakh. Fundamental'naya i Prikladnaya Matematika. 2012;4 (17):95—131. (in Russian).

20. Umans C. Fast Polynomial Factorization and Modular Composition in Small Characteristic. Proc. 40 th Symp. Theory of Computing. 2008:481—490.

21. Ahmadi O., Hankerson D., Menezes A. Formulas for Cube Roots. Discrete Appl. Math. 2007;155 (3): 260—270.
---
For citation: Gashkov S.B., Frolov A.B., Popova E.P. About the Complexity of Square Root Extraction Algorithms in Finite Fields and Residue Rings. MPEI Vestnik. 2018;5:79—88. (in Russian). DOI: 10.24160/1993-6982-2018-5-79-88.
Опубликован
2018-10-01
Раздел
Информатика, вычислительная техника и управление (05.13.00)