About the Complexity of Square Root Extraction Algorithms in Finite Fields and Residue Rings
Abstract
The article presents a review of the known algorithms for extracting square roots of the quadratic residues modulo primes and prime powers. According to the Chinese remainder theorem, such algorithms can be constructed to calculate square roots modulo any integer. These include the Tonelli and Chipolla probabilistic algorithms and deterministic algorithms for calculating the square roots of quadratic residues in residue rings modulo a prime number not congruent to 1 modulo 8, as well as the algorithms for extracting a square root modulo a power of a prime number constructed on their basis. The article presents new algorithms for extracting square roots in finite fields of characteristic congruent to 3 modulo 4, for square roots of residues congruent to 1 modulo 8, and for square roots in residue rings modulo power of two. For probabilistic algorithms, the calculation complexity and the probability of successfully accomplishing the calculation in the first try are estimated. The square roots extraction problem encountered in number-theoretic algorithms of cryptography used in combination with the Chinese remainder theorem for root square extraction in residue rings modulo an arbitrary number is considered. The article presents known probabilistic and deterministic algorithms for extracting square roots modulo a prime number, along with estimating the complexity of the algorithms and the probability of successfully completing the computation in the first try. New implementing in the elliptic curve cryptography algorithms for extracting square roots in finite fields of characteristic congruent to 3 modulo 4 are substantiated, and estimates of their complexity are given. Algorithms for extracting square roots in fields of even order are studied, and estimates of their complexity are given. Algorithms for extracting square roots in residue rings modulo prime powers and modulo power of two are demonstrated.
References
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.
