### Abstract

We present a new deterministic algorithm for factoring polynomials over Z_{p} of degree n. We show that the worst-case running time of our algorithm is O(p^{ 1 2}(log p)^{2}n^{2+∈}), which is faster than the running times of previous determi nistic algorithms with respect to both n and p. We also show that our algorithm runs in polynomial time for all but at most an exponentially small fraction of the polynomials of degree n over Z_{p}. Specifically, we prove that the fraction of polynomials of degree n over Z_{p} for which our algorithm fails to halt in time O((log p)^{2}n^{2+∈}) is ((n log p)^{2}/p). Consequently, the average-case running time of our algorithm is polynomial in n and log p.

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

Pages (from-to) | 261-267 |

Number of pages | 7 |

Journal | Information Processing Letters |

Volume | 33 |

Issue number | 5 |

DOIs | |

State | Published - Jan 10 1990 |

### Keywords

- Factorization
- finite fields
- irreducible polynomials

### ASJC Scopus subject areas

- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications