Fast construction of irreducible polynomials over finite fields

Victor Shoup

doi:10.1006/jsco.1994.1025

Fast construction of irreducible polynomials over finite fields

Victor Shoup

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

The main result of this paper a new algorithm for constructing an irreducible polynomial of specified degree n over a finite field F_q . The algorithm is probabilistic, and is asymptotically faster than previously known algorithms for this problem. It uses an expected number of O^-(n² + n log q) operations in F_q, where the "soft-O" O^- indicates an implicit factor of (log n)^O(1). In addition, two new polynomial irreducibility tests are described.

Original language	English (US)
Pages (from-to)	371-391
Number of pages	21
Journal	Journal of Symbolic Computation
Volume	17
Issue number	5
DOIs	https://doi.org/10.1006/jsco.1994.1025
State	Published - 1994

ASJC Scopus subject areas

Algebra and Number Theory
Computational Mathematics

Access to Document

10.1006/jsco.1994.1025

Cite this

@article{51ffcda922984199bb73e5ec6bd0727a,

title = "Fast construction of irreducible polynomials over finite fields",

abstract = "The main result of this paper a new algorithm for constructing an irreducible polynomial of specified degree n over a finite field Fq . The algorithm is probabilistic, and is asymptotically faster than previously known algorithms for this problem. It uses an expected number of O-(n2 + n log q) operations in Fq, where the {"}soft-O{"} O- indicates an implicit factor of (log n)O(1). In addition, two new polynomial irreducibility tests are described.",

author = "Victor Shoup",

year = "1994",

doi = "10.1006/jsco.1994.1025",

language = "English (US)",

volume = "17",

pages = "371--391",

journal = "Journal of Symbolic Computation",

issn = "0747-7171",

publisher = "Academic Press",

number = "5",

}

TY - JOUR

T1 - Fast construction of irreducible polynomials over finite fields

AU - Shoup, Victor

PY - 1994

Y1 - 1994

N2 - The main result of this paper a new algorithm for constructing an irreducible polynomial of specified degree n over a finite field Fq . The algorithm is probabilistic, and is asymptotically faster than previously known algorithms for this problem. It uses an expected number of O-(n2 + n log q) operations in Fq, where the "soft-O" O- indicates an implicit factor of (log n)O(1). In addition, two new polynomial irreducibility tests are described.

AB - The main result of this paper a new algorithm for constructing an irreducible polynomial of specified degree n over a finite field Fq . The algorithm is probabilistic, and is asymptotically faster than previously known algorithms for this problem. It uses an expected number of O-(n2 + n log q) operations in Fq, where the "soft-O" O- indicates an implicit factor of (log n)O(1). In addition, two new polynomial irreducibility tests are described.

UR - http://www.scopus.com/inward/record.url?scp=38149147073&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38149147073&partnerID=8YFLogxK

U2 - 10.1006/jsco.1994.1025

DO - 10.1006/jsco.1994.1025

M3 - Article

AN - SCOPUS:38149147073

SN - 0747-7171

VL - 17

SP - 371

EP - 391

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

IS - 5

ER -

Fast construction of irreducible polynomials over finite fields

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this