### Abstract

An algorithm is presented for finding an irreducible polynomial of specified degree over a finite field. It is deterministic and runs in polynomial time for fields of small characteristics. A proof is given of the stronger result, that the problem of finding irreducible polynomials of specified degree over a finite field K is deterministic-polynomial-time reducible to the problem of factoring polynomials over the prime field of K.

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

Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |

Publisher | Publ by IEEE |

Pages | 283-290 |

Number of pages | 8 |

ISBN (Print) | 0818608773, 9780818608773 |

DOIs | |

State | Published - 1988 |

### Publication series

Name | Annual Symposium on Foundations of Computer Science (Proceedings) |
---|---|

ISSN (Print) | 0272-5428 |

### ASJC Scopus subject areas

- Hardware and Architecture

## Fingerprint Dive into the research topics of 'New algorithms for finding irreducible polynomials over finite fields'. Together they form a unique fingerprint.

## Cite this

Shoup, V. (1988). New algorithms for finding irreducible polynomials over finite fields. In

*Annual Symposium on Foundations of Computer Science (Proceedings)*(pp. 283-290). (Annual Symposium on Foundations of Computer Science (Proceedings)). Publ by IEEE. https://doi.org/10.1109/sfcs.1988.21944