|
This article is cited in 18 scientific papers (total in 18 papers)
Fields of algebraic numbers computable in polynomial time. I
P. E. Alaevab, V. L. Selivanovcd a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
b Novosibirsk State University
c A.P. Ershov Institute of Informatics Systems, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
d Kazan (Volga Region) Federal University
Abstract:
It is proved that the field of complex algebraic numbers has an isomorphic presentation computable in polynomial time. A similar fact is proved for the ordered field of real algebraic numbers. The constructed polynomially computable presentations are based on a natural presentation of algebraic numbers via rational polynomials. Also new algorithms for computing values of polynomials on algebraic numbers and for solving equations in one variable with algebraic coefficients are presented.
Keywords:
field of complex algebraic numbers, ordered field of real algebraic numbers, polynomially computable presentation.
Received: 15.07.2018 Revised: 12.02.2020
Citation:
P. E. Alaev, V. L. Selivanov, “Fields of algebraic numbers computable in polynomial time. I”, Algebra Logika, 58:6 (2019), 673–705; Algebra and Logic, 58:6 (2020), 447–469
Linking options:
https://www.mathnet.ru/eng/al923 https://www.mathnet.ru/eng/al/v58/i6/p673
|
Statistics & downloads: |
Abstract page: | 380 | Full-text PDF : | 48 | References: | 35 | First page: | 18 |
|