Fast construction of irreducible polynomials over finite fields

Victor Shoup

Fast construction of irreducible polynomials over finite fields

Victor Shoup

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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²+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

General Engineering

Cite this

@inproceedings{3294f409d4124a6b9227379943d6c44a,

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

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

author = "Victor Shoup",

year = "1993",

language = "English (US)",

pages = "484--492",

booktitle = "Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Publ by ACM",

note = "Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 25-01-1993 Through 27-01-1993",

}

TY - GEN

T1 - Fast construction of irreducible polynomials over finite fields

AU - Shoup, Victor

PY - 1993

Y1 - 1993

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

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

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

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

M3 - Conference contribution

AN - SCOPUS:0027147589

SP - 484

EP - 492

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

PB - Publ by ACM

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

Y2 - 25 January 1993 through 27 January 1993

ER -

Fast construction of irreducible polynomials over finite fields

Abstract

Other

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this