Computing Sums of Radicals in Polynomial Time
Johannes Blömer
International Computer Science Institute
Berkeley, USA
Report B 93-13
August 93
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-93-13.ps.gz
For sums of radicals $\sum_{i=1}^{k}\up_{i}\sqrt[d_{i}]{\rh_{i}}$, where $\up_{i},\rh_{i}$ are elements of some real algebraic number field $\qa,$ $\sqrt[d_{i}]{\rh_{i}}\in\R,$ we present a deterministic polynomial time algorithm to decide whether the sum is zero. The time is polynomial in the number of bits required to represent $\alpha$, the $\up_{i}$'s, $\rh_{i}$'s and $d_{i}$'s. The algorithm can be extended to sums of complex radicals over certain complex algebraic number fields.