What do random polynomials over finite fields look like?

DOI10.1007/978-3-540-24633-6_8MaRDI QIDQ4832280zbMATH OpenFDO

Authors Daniel Panario

Publication date 4 January 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-24633-6_8

zbMATH Keywords

asymptotic analysisaverage-case analysisdiscrete logarithmfactorizationgenerating functionirreducibility testprobabilistic algorithmunivariate random polynomial

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to number theory (11-02) Polynomials over finite fields (11T06) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Analysis of algorithms and problem complexity (68Q25)

Review text

The paper contains a survey of a methodology that has been successfully used to study random univariate polynomials over a finite field. This approach is based, on the one hand, on generating functions, and, on the other hand, on asymptotic analysis. These components are introduced in the first part of the paper. Next it is indicated how they are employed to provide precise average-case analysis of well-known irreducibility tests, factorization algorithms and several solutions to the discrete logarithm problem. Extensions and further possible applications of the methodology are briefly discussed in the final section. Three pages of references end the paper. For the entire collection see [Zbl 1048.11003].

Recommendations

• Tests and constructions of irreducible polynomials over finite fields
• Random polynomials over a finite field
• scientific article; zbMATH DE number 1055650
• Analysis of Rabin's irreducibility test for polynomials over finite fields
• Analysis of Ben-Or's polynomial irreducibility test

Cited in

(6)

• Interval partitions and polynomial factorization
• Splitting fields for characteristic polynomials of matrices with entries in a finite field
• Random polynomials over a finite field
• Estimating the number of roots of trinomials over finite fields
• Analysis of Ben-Or's polynomial irreducibility test
• On weak keys and forgery attacks against polynomial-based MAC schemes

This page was built for publication: What do random polynomials over finite fields look like?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4832280)