vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2020-56-2-144-156vestifm-516Research ArticleМАТЕМАТИКАMATHEMATICSВероятностный и детерминированный аналоги алгоритма Миллера – Рабина для идеалов колец целых алгебраических элементов конечных расширений поля QProbabilistic and deterministic analogues of the Miller – Rabin algorithm for ideals of rings of integer algebraic elements of finite extensions of the field ПрохоровН. П.ProchorovN. P.

Прохоров Николай Петрович – ассистент кафедры высшей математики

пр. Независимости, 4, 220072, г. Минск

Nikolai P. Prochorov – Assistant of the Department of Higher Mathematics

4, Nezavisimosti Ave., 220072, Minsk

nprohorovminsk@mail.ruБелорусский государственный университетBelarusian State University202008072020562144156Copyright © Прохоров Н.П., 20202020Прохоров Н.П.Prochorov N.P.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/516

Получены критерии простоты для идеалов колец целых алгебраических элементов конечных расширений поля Q, которые являются аналогами критериев Миллера и Эйлера простоты для кольца целых чисел. Также получены их усиленные аналоги в предположении расширенной гипотезы Римана. Разработаны арифметические и модулярные операции для идеалов колец целых алгебраических элементов расширений поля Q С помощью указанных критериев предложены полиномиальные вероятностные и детерминированные алгоритмы решения задачи тестирования на простоту в кольцах целых алгебраических элементов конечных расширений поля Q.

In this paper, we obtained the primality criteria for ideals of rings of integer algebraic elements of finite extensions of the field Q, which are analogues of Miller and Euler’s primality criteria for rings of integers. Also advanced analogues of these criteria were obtained, assuming the extended Riemann hypothesis. Arithmetic and modular operations for ideals of rings of integer algebraic elements of finite extensions of the field Q were elaborated. Using these criteria, the polynomial probabilistic and deterministic algorithms for the primality testing in rings of integer algebraic elements of finite extensions of the field Q were offered.

конечное расширениекольцо целых алгебраических элементовидеалпростота идеалатестирование на простотукритерий Миллеракритерий Эйлератест Миллера – Рабинаfinite extensionring of integer algebraic elementsidealprimality of idealprimality testingMiller criterionEuler criterionMiller – Rabin testReferencesMiller, G. Riemann’s Hypothesis and Tests for Primality / G. Miller // J. Comput. System Sci. – 1976. – Vol. 13, № 3. – P. 300–317. https://doi.org/10.1016/s0022-0000(76)80043-8Miller G. Riemann’s Hypothesis and Tests for Primality. Journal of Computer and System Sciences, 1976, vol. 13, no. 3, pp. 300–317. https://doi.org/10.1016/s0022-0000(76)80043-8Bach, E. Explicit bounds for primality testing and related problems / E. Bach // Math. Comput. – 1990. – Vol. 55, № 191. – P. 355–380. https://doi.org/10.1090/s0025-5718-1990-1023756-8Bach E. Explicit bounds for primality testing and related problems. Mathematics of Computation, 1990, vol. 55, no. 191, pp. 355–380. https://doi.org/10.1090/s0025-5718-1990-1023756-8Rabin, M. O. Probabilistic Algorithm for Testing Primality / M. O. Rabin // J. Number Theory. – 1980. – Vol. 12, № 1. – P. 128–138. https://doi.org/10.1016/0022-314X(80)90084-0Rabin M. O. Probabilistic Algorithm for Testing Primality. Journal of Number Theory, 1980, vol. 12, no. 1, pp. 128– 138. https://doi.org/10.1016/0022-314X(80)90084-0Solovay, R. A fast Monte-Carlo test for primality / R. Solovay, S. Folker // SIAM J. Comput. – 1977. – Vol. 6, № 1. – P. 84–85. https://doi.org/10.1137/0206006Solovay R., Folker S. A fast Monte-Carlo test for primality. SIAM Journal on Computing, 1977, vol. 6, no. 1, pp. 84–85. https://doi.org/10.1137/0206006Adleman, M. L. On distinguishing prime numbers from composite numbers / L. M. Adleman, C. Pomerance, R. S. Rumely // Ann. Math. – 1983. – Vol. 117, № 1. – P. 173–206. https://doi.org/10.2307/2006975Adleman M. L., Pomerance C., Rumely R. S. On distinguishing prime numbers from composite numbers. Annals of Mathematics, 1983, vol. 117, no. 1, pp. 173–206. https://doi.org/10.2307/2006975Agrawal, M. Primes is in P. / M. Agrawal, N. Kayal, N. Saxena // Ann. Math. – 2004. – Vol. 160, № 2. – P. 781–793. https://doi.org/10.4007/annals.2004.160.781Agrawal M., Kayal N., Saxena N. Primes is in P. Annals of Mathematics, 2004, vol. 160, no. 2, pp. 781–793. https://doi.org/10.4007/annals.2004.160.781Гекке, Э. Лекции по теории алгебраических чисел / Э. Гекке. – М.: Гостехтеоретиздат, 1940. – 260 с.Dekker T. J. Primes in quadratic fields. CWI Quartetly, 1994, vol. 7, pp. 367–394.Dekker, T. J. Primes in quadratic fields / T. J. Dekker // CWI Quartetly – 1994. – Vol. 7. – P. 367–394.Hecke E. Lection on theory of algebraic numbers. Moscow, Gostekhteoretizdat Publ., 1940. 260 p. (in Russian).Vaskouski, M. Primes in quadratic unique factorization domains / M. Vaskouski, N. Kondratyonok, N. Prochorov // J. Number Theory. – 2016. – Vol. 168. – P. 101–116. https://doi.org/10.1016/j.jnt.2016.04.022Vaskouski M., Kondratyonok N., Prochorov N. Primes in quadratic unique factorization domains. Journal of Number Theory, 2016, vol. 168, pp. 101–116. https://doi.org/10.1016/j.jnt.2016.04.022Howe, E. W. Higher order Carmichael Numbers / E. W. Howe // Math. Comp. – 2000. – Vol. 69, № 232. – P. 1711– 1719. https://doi.org/10.1090/s0025-5718-00-01225-4Howe E. W. Higher order Carmichael Numbers. Mathematics of Computation, 2000, vol. 69, no. 232, pp. 1711–1719. https://doi.org/10.1090/s0025-5718-00-01225-4Steel, G. A. Carmichael numbers in number rings / G. A. Steel // J. Number Theory. – 2008. – Vol. 128, № 4. – P. 910– 917. https://doi.org/10.1016/j.jnt.2007.08.009Steel G. A. Carmichael numbers in number rings. Journal of Number Theory, 2008, vol. 128, no. 4, pp. 910–917. https://doi.org/10.1016/j.jnt.2007.08.009Dandan, H. An algorithm for computing the factor ring of an ideal in Dedekind domain with finite rank / H. Dandan, D. Yingpu // Science China Mathematics. – 2017. – Vol. 61, № 5. – P. 783–796. https://doi.org/10.1007/s11425-016-9060-2Dandan Huang, Deng Yingpu. An algorithm for computing the factor ring of an ideal in Dedekind domain with finite rank. Science China Mathematics, 2017, vol. 61, no. 5, pp. 783–796. https://doi.org/10.1007/s11425-016-9060-2Cohen, H. A Course in Computational Algebraic Number Theory / H. Cohen. – Springer, 1996. https://doi. org/10.1007/978-3-662-02945-9Cohen H. A Course in Computational Algebraic Number Theory. Springer, 1996. https://doi.org/10.1007/978-3-662- 02945-9Post, E. M. Computational Algebraic Number Theory / M. E. Post. – Berlin; Heidelberg: Springer-Verlag, 1993. – 536 p. https://doi.org/10.1007/978-3-0348-8589-8Post E. M. Computational Algebraic Number Theory. Berlin, Heidelberg, Springer-Verlag, 1993. 536 pp. https://doi.org/10.1007/978-3-0348-8589-8Kannan, R. Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix / R. Kannan, A. Bachem // SIAM J. Comput. – 1979. – Vol. 8, № 4. – P. 499–507. https://doi.org/10.1137/0208040Kannan R., Bachem A. Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix. SIAM Journal on Computing, 1979, vol. 8, no. 4, pp. 499–507. https://doi.org/10.1137/0208040Lenstra, H. W. Computing Jacoby Symbols in Algebraic Number Fiels / H. W. Lenstra // Neieuw Archief voor Wiskunde. – 1995. – P. 421–426.Lenstra H. W. Computing Jacoby Symbols in Algebraic Number Fiels. Neieuw Archief voor Wiskunde, 1995, pp. 421–426.Ankeny, N. C. The Least Quadratic Non Residue / N. C. Ankeny // Ann. Math. – 1952. – Vol. 55, № 1. – P. 65–72. https://doi.org/10.2307/1969420Ankeny N. C. The Least Quadratic Non Residue. Annals of Mathematics, 1952, vol. 55, no. 1. pp. 65–72. https://doi.org/10.2307/1969420Wikstrom, D. On the l-Ary GCD-Algotihm in Ring of Integers / D. Wikstrom. – Berlin; Heidelberg: Springer-Verlag, 2005. – P. 1189–1201. https://doi.org/10.1007/11523468_96Wikstrom D. On the l-Ary GCD-Algotihm in Ring of Integers. Berlin, Heidelberg, Springer-Verlag, 2005, pp. 1189– 1201. https://doi.org/10.1007/11523468_96

The authors declare that there are no conflicts of interest present.