### Abstract

An algorithm is presented that constructs an irreducible polynomial of specified degree n over a finite field F_{q}. The algorithm is probabilistic, and is asymptotically faster than previously known probabilistic algorithms for this problem. It uses an expected number of Oqq(n^{2}+n log q) operations in F_{q}, where the `soft-O' Oqq indicates an implicit factor of (log n)^{O(1)}.

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

Title of host publication | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |

Publisher | Publ by ACM |

Pages | 484-492 |

Number of pages | 9 |

State | Published - 1993 |

Event | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms - Austin, TX, USA Duration: Jan 25 1993 → Jan 27 1993 |

### Other

Other | Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

City | Austin, TX, USA |

Period | 1/25/93 → 1/27/93 |

### ASJC Scopus subject areas

- Engineering(all)

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

## Cite this

Shoup, V. (1993). Fast construction of irreducible polynomials over finite fields. In

*Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 484-492). Publ by ACM.