### Abstract

We analyse an extension of Shoup's (Inform. Process. Lett. 33 (1990) 261–267) deterministic algorithm for factoring polynomials over finite prime fields to arbitrary finite fields. In particular, we prove the existence of a deterministic algorithm which completely factors all monic polynomials of degree n over Fq, q odd, except possibly O(n2 log2 q/q) polynomials, using O(n2+ log2q) arithmetical operations in Fq.

Original language | English |
---|---|

Pages (from-to) | 301-308 |

Journal | Theoretical Computer Science |

Volume | 234 |

Issue number | 1-2 |

DOIs | |

Publication status | Published - 2000 |

## Fingerprint Dive into the research topics of 'Factoring polynomials over arbitrary finite fields'. Together they form a unique fingerprint.

## Cite this

Lange, T., & Winterhof, A. (2000). Factoring polynomials over arbitrary finite fields.

*Theoretical Computer Science*,*234*(1-2), 301-308. https://doi.org/10.1016/S0304-3975(99)00291-1