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