Probabilistic and deterministic analogues of the Miller – Rabin algorithm for ideals of rings of integer algebraic elements of finite extensions of the field
https://doi.org/10.29235/1561-2430-2020-56-2-144-156
Abstract
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.
About the Author
N. P. Prochorov
Belarusian State University
Belarus
Belarus
Nikolai P. Prochorov – Assistant of the Department of Higher Mathematics
4, Nezavisimosti Ave., 220072, Minsk
References
1. Miller 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-8
2. Bach 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-8
3. Rabin 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-0
4. Solovay 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/0206006
5. Adleman 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/2006975
6. Agrawal 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
7. Dekker T. J. Primes in quadratic fields. CWI Quartetly, 1994, vol. 7, pp. 367–394.
8. Hecke E. Lection on theory of algebraic numbers. Moscow, Gostekhteoretizdat Publ., 1940. 260 p. (in Russian).
9. Vaskouski 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.022
10. Howe 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-4
11. Steel 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.009
12. Dandan 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-2
13. Cohen H. A Course in Computational Algebraic Number Theory. Springer, 1996. https://doi.org/10.1007/978-3-662- 02945-9
14. Post E. M. Computational Algebraic Number Theory. Berlin, Heidelberg, Springer-Verlag, 1993. 536 pp. https://doi.org/10.1007/978-3-0348-8589-8
15. Kannan 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/0208040
16. Lenstra H. W. Computing Jacoby Symbols in Algebraic Number Fiels. Neieuw Archief voor Wiskunde, 1995, pp. 421–426.
17. Ankeny N. C. The Least Quadratic Non Residue. Annals of Mathematics, 1952, vol. 55, no. 1. pp. 65–72. https://doi.org/10.2307/1969420
18. Wikstrom 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
Review
Views: 909
Email this article 