### Abstract

New probabilistic algorithms are presented for factoring univariate polynomials over finite fields. The algorithms factor a polynomial of degree n over a finite field of constant cardinality in time O(n^{1.815}). Previous algorithms required time θ(n^{2+0(1)}). The new algorithms rely on fast matrix multiplication techniques. More generally, to factor a polynomial of degree n over the finite field double-struck F_{q} with q elements, the algorithms use O(n^{1.815} log q) arithmetic operations in double-struck F_{q}. The new "baby step/giant step" techniques used in our a gorithms also yield new fast practical algorithms at super-quadratic asymptotic running time, and subquadratic-tirne methods for manipulating normal bases of finite fields.

Original language | English (US) |
---|---|

Pages (from-to) | 1179-1197 |

Number of pages | 19 |

Journal | Mathematics of Computation |

Volume | 67 |

Issue number | 223 |

DOIs | |

State | Published - Jul 1998 |

### Keywords

- Factoring
- Finite fields
- Normal bases
- Polynomials
- Randomized algorithms

### ASJC Scopus subject areas

- Algebra and Number Theory
- Computational Mathematics
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Subquadratic-time factoring of polynomials over finite fields'. Together they form a unique fingerprint.

## Cite this

*Mathematics of Computation*,

*67*(223), 1179-1197. https://doi.org/10.1090/s0025-5718-98-00944-2