## 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