Geodesic
Fields of algebraic numbers computable in polynomial time. I
Algebra i logika, Tome 58 (2019) no. 6, pp. 673-705.

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{AL_2019_58_6_a0,
     author = {P. E. Alaev and V. L. Selivanov},
     title = {Fields of algebraic numbers computable in polynomial time. {I}},
     journal = {Algebra i logika},
     pages = {673--705},
     publisher = {mathdoc},
     volume = {58},
     number = {6},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/AL_2019_58_6_a0/}
}
TY  - JOUR
AU  - P. E. Alaev
AU  - V. L. Selivanov
TI  - Fields of algebraic numbers computable in polynomial time. I
JO  - Algebra i logika
PY  - 2019
SP  - 673
EP  - 705
VL  - 58
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/AL_2019_58_6_a0/
LA  - ru
ID  - AL_2019_58_6_a0
ER  - 
%0 Journal Article
%A P. E. Alaev
%A V. L. Selivanov
%T Fields of algebraic numbers computable in polynomial time. I
%J Algebra i logika
%D 2019
%P 673-705
%V 58
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/AL_2019_58_6_a0/
%G ru
%F AL_2019_58_6_a0
P. E. Alaev; V. L. Selivanov. Fields of algebraic numbers computable in polynomial time. I. Algebra i logika, Tome 58 (2019) no. 6, pp. 673-705. http://geodesic.mathdoc.fr/item/AL_2019_58_6_a0/

[1] D. Cenzer, J. B. Remmel, “Complexity theoretic model theory and algebra”, Handbook of recursive mathematics, v. 1, Stud. Logic Found. Math., 138, Recursive model theory, eds. Yu. L. Ershov et al., Elsevier, Amsterdam, 1998, 381–513 | DOI | MR | Zbl

[2] G. E. Collins, R. Loos, “Real zeroes of polynomials”, Computer algebra. Symbolic and algebraic computations, Comput. Suppl., 4, eds. B. Buchberger et al., Springer-Verlag, Wien–New York, 1982, 83–94 | DOI | MR

[3] R. Loos, “Computing in algebraic extensions”, Computer algebra. Symbolic and algebraic computations, Comput. Suppl., 4, eds. B. Buchberger et al., Springer-Verlag, Wien–New York, 1982, 173–187 | DOI | MR

[4] A. K. Lenstra, H. W. Lenstra, L. Lovász, “Factoring polynomials with rational coefficients”, Math. Ann., 261 (1982), 515–534 | DOI | MR | Zbl

[5] M. O. Rabin, “Computable algebra, general theory and theory of computable fields”, Trans. Am. Math. Soc., 95 (1960), 341–360 | MR | Zbl

[6] Yu. L. Eršov, “Theorie der Numerierungen. III”, Z. Math. Logik Grundl. Math., 23:4 (1977), 289–371 | MR | Zbl

[7] S. S. Goncharov, Yu. L. Ershov, Konstruktivnye modeli, Sibirskaya shkola algebry i logiki, Nauchnaya kniga, Novosibirsk, 1999 | MR

[8] G. E. Collins, “The calculation of multivariate polynomial resultants”, J. Assoc. Comput. Mach., 18:4 (1971), 515–532 | DOI | MR | Zbl

[9] F. Winkler, Polynomial algorithms in computer algebra, Texts Monogr. Symb. Comput., Springer, Wien, 1996 | MR | Zbl

[10] H. Cohen, A course in computational algebraic number theory, Grad. Texts Math., 138, Springer-Verlag, Berlin, 1993 | DOI | MR | Zbl

[11] C. K. Yap, Fundamental problems of algorithmic algebra, Oxford Univ. Press, Oxford, 2000 | MR | Zbl

[12] G. E. Collins, “Quantifier elimination for real closed fields by cylindrical decomposition”, Autom. Theor. form. Lang., 2nd GI Conf. (Kaiserslautern, 1975), Lect. Notes Comput. Sci., 33, 1975, 134–183 | DOI | MR | Zbl

[13] P. E. Alaev, “Suschestvovanie i edinstvennost struktur, vychislimykh za polinomialnoe vremya”, Algebra i logika, 55:1 (2016), 106–112 | MR | Zbl

[14] P. E. Alaev, “Struktury, vychislimye za polinomialnoe vremya. I”, Algebra i logika, 55:6 (2016), 647–669 | MR

[15] A. Akho, Dzh. Khopkroft, Dzh. Ulman, Postroenie i analiz vychislitelnykh algoritmov, Mir, M., 1979

[16] A. Akritas, Osnovy kompyuternoi algebry s prilozheniyami, Mir, M., 1994

[17] A. Skhreiver, Teoriya lineinogo i tselochislennogo programmirovaniya, v. 1, Mir, M., 1991 | MR

[18] Jianping Zhou, “On the degree of extensions generated by finitely many algebraic numbers”, J. Number Theory, 34:2 (1990), 133–141 | DOI | MR | Zbl