Fast Polynomial Factorization and Modular Composition
We obtain randomized algorithms for factoring degree n univariate polynomials over $\mathbb{F}_q$ requiring $O(n^{1.5 + o(1)}\,{\rm log}^{1+o(1)} q+ n^{1 + o(1)}\,{\rm log}^{2+o(1)} q)$ bit operations. When ${\rm log}\, q < n$, this is asymptotically faster than the best previous algorithms [J. v...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2012
|
| Online Access: | http://hdl.handle.net/1721.1/71792 |