Loading...
Please wait, while we are loading the content...
Similar Documents
On lacunary polynomial perfect powers (2008).
| Content Provider | CiteSeerX |
|---|---|
| Author | Giesbrecht, Mark Roche, Daniel S.: |
| Abstract | We consider the problem of determining whether a t-sparse or lacunary polynomial f is a perfect power, that is, f = h r for some other polynomial h and r â N, and of finding h and r should they exist. We show how to determine if f is a perfect power in time polynomial in t and log deg f, i.e., polynomial in the size of the lacunary representation. The algorithm works over Fq[x] (at least for large characteristic) and over Z[x], where the cost is also polynomial in log âfââ. Subject to a conjecture, we show how to find h if it exists via a kind of sparse Newton iteration, again in time polynomial in the size of the sparse representation. Finally, we demonstrate an implementation using the C++ library NTL. |
| File Format | |
| Publisher Date | 2008-01-01 |
| Access Restriction | Open |
| Subject Keyword | Lacunary Polynomial Perfect Power Time Polynomial Perfect Power Lacunary Representation Sparse Representation Sparse Newton Iteration Lacunary Polynomial Log Deg Library Ntl |
| Content Type | Text |
