Analysis of Rabin's irreducibility test for polynomials over finite fields

DOI10.1002/rsa.10011zbMath1036.11065OpenAlexW1965196198MaRDI QIDQ2772930

Alfredo Viola, Daniel Panario, Bruce Richmond, Boris G. Pittel

Publication date: 25 February 2003

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/20.500.12008/3455

zbMATH Keywords

average case analysisfinite fields, irreducible polynomialsRabin's irreducibility test

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Polynomials in general fields (irreducibility, etc.) (12E05) Polynomials over finite fields (11T06)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On fast multiplication of polynomials over arbitrary algebras
• Counting irreducible factors of polynomials over a finite field
• Fast multiplication of polynomials over fields of characteristic 2
• Computing Frobenius maps and factoring polynomials
• Fast multiplication of large numbers
• The Complete Analysis of a Polynomial Factorization Algorithm over Finite Fields
• Fast evaluation of logarithms in fields of characteristic two
• Computing Logarithms in Finite Fields of Characteristic Two
• Counting polynomials with a given number of zeros in a finite field
• Probabilistic Algorithms in Finite Fields
• Analysis of Ben-Or's polynomial irreducibility test

This page was built for publication: Analysis of Rabin's irreducibility test for polynomials over finite fields