Вероятностный и детерминированный аналоги алгоритма Миллера – Рабина для идеалов колец целых алгебраических элементов конечных расширений поля Q
https://doi.org/10.29235/1561-2430-2020-56-2-144-156
Аннотация
Получены критерии простоты для идеалов колец целых алгебраических элементов конечных расширений поля Q, которые являются аналогами критериев Миллера и Эйлера простоты для кольца целых чисел. Также получены их усиленные аналоги в предположении расширенной гипотезы Римана. Разработаны арифметические и модулярные операции для идеалов колец целых алгебраических элементов расширений поля Q С помощью указанных критериев предложены полиномиальные вероятностные и детерминированные алгоритмы решения задачи тестирования на простоту в кольцах целых алгебраических элементов конечных расширений поля Q.
Об авторе
Н. П. Прохоров
Белорусский государственный университет
Беларусь
Беларусь
Прохоров Николай Петрович – ассистент кафедры высшей математики
пр. Независимости, 4, 220072, г. Минск
Список литературы
1. Miller, 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-8
2. Bach, 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-8
3. Rabin, 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-0
4. Solovay, 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/0206006
5. Adleman, 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/2006975
6. Agrawal, 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.781
7. Гекке, Э. Лекции по теории алгебраических чисел / Э. Гекке. – М.: Гостехтеоретиздат, 1940. – 260 с.
8. Dekker, T. J. Primes in quadratic fields / T. J. Dekker // CWI Quartetly – 1994. – Vol. 7. – P. 367–394.
9. 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.022
10. Howe, 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-4
11. Steel, 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.009
12. Dandan, 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-2
13. Cohen, H. A Course in Computational Algebraic Number Theory / H. Cohen. – Springer, 1996. https://doi. org/10.1007/978-3-662-02945-9
14. Post, 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-8
15. Kannan, 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/0208040
16. Lenstra, H. W. Computing Jacoby Symbols in Algebraic Number Fiels / H. W. Lenstra // Neieuw Archief voor Wiskunde. – 1995. – P. 421–426.
17. 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/1969420
18. Wikstrom, 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_96
Рецензия
Просмотров: 906
Послать статью по эл. почте 