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: 
File:   pub/reports/
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.