Fields of Algebraic Numbers Computable in Polynomial Time. I

Fields of Algebraic Numbers Computable in Polynomial Time. I Full article

Journal

Algebra and Logic
ISSN: 0002-5232 , E-ISSN: 1573-8302

Output data

Year: 2020, Volume: 58, Number: 6, Pages: 447-469 Pages count : 23 DOI: 10.1007/s10469-020-09565-0

Tags

field of complex algebraic numbers; ordered field of real algebraic numbers; polynomially computable presentation

Authors

Alaev P.E. ^1,2 , Selivanov V.L. ^3,4

Affiliations

1	Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russian Federation
2	Novosibirsk State University, ul. Pirogova 1, Novosibirsk, 630090, Russian Federation
3	Ershov Institute of Informatics Systems, pr. Akad. Lavrent’eva 6, Novosibirsk, 630090, Russian Federation
4	Kazan (Volga Region) Federal University, ul. Kremlevskaya 18, Kazan, 420008, Russian Federation

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 by 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. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.

Alaev P.E. , Selivanov V.L.
Fields of Algebraic Numbers Computable in Polynomial Time. I
Algebra and Logic. 2020. V.58. N6. P.447-469. DOI: 10.1007/s10469-020-09565-0 WOS Scopus OpenAlex

Алаев П.Е. , Селиванов В.Л.
Поля алгебраических чисел, вычислимые за полиномиальное время. I
Алгебра и логика. 2019. Т.58. №6. С.673-705. DOI: 10.33048/alglog.2019.58.601 OpenAlex

Web of science:	WOS:000518462600004
Scopus:	2-s2.0-85081549779
OpenAlex:	W3009523158

DB	Citing
Scopus	9
OpenAlex	10
Web of science	10