FIELDS OF ALGEBRAIC NUMBERS COMPUTABLE IN POLYNOMIAL TIME. I

被引：9

作者：

Alaev, P. E. ^{[1
,2
]}

Selivanov, V. L. ^{[3
,4
]}

机构：

[1] Sobolev Inst Math, Pr Akad Koptyuga 4, Novosibirsk 630090, Russia

[2] Novosibirsk State Univ, Ul Pirogova 1, Novosibirsk 630090, Russia

[3] Ershov Inst Informat Syst, Pr Akad Lavrenteva 6, Novosibirsk 630090, Russia

[4] Kazan Volga Reg Fed Univ, Ul Kremlevskaya 18, Kazan 420008, Russia

来源：

ALGEBRA AND LOGIC | 2020年 / 58卷 / 06期

关键词：

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

D O I：

10.1007/s10469-020-09565-0

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

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.

引用

页码：447 / 469

页数：23

共 18 条

[1]

Aho A. V., 1974, The Design and Analysis of Computer Algorithms

[2]

Akritas A. G., 1989, ELEMENTS COMPUTER AL

[3] STRUCTURES COMPUTABLE IN POLYNOMIAL TIME. I [J].