Certifying Irreducibility in Z[x]

2020/05/10 by John Abbott, Abbott, John · 1 citation
Computer Science · #12-08 #12E05 #13P05 #Commutative Algebra (math.AC) #Cryptography and Data Security #Cryptography and Residue Arithmetic #FOS: Mathematics #Number Theory (math.NT) #Polynomial and algebraic computation

paper · pdf · doi:10.48550/arxiv.2005.04633

openalex publication_date 2020/05/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the question of certifying that a polynomial in \mathbb Z[x] or \mathbb Q[x] is irreducible. Knowing that a polynomial is irreducible lets us recognise that a quotient ring is actually a field extension (equiv.~that a polynomial ideal is maximal). Checking that a polynomial is irreducible by factorizing it is unsatisfactory because it requires trusting a relatively large and complicated program (whose correctness cannot easily be verified). We present a practical method for generating certificates of irreducibility which can be verified by relatively simple computations; we assume that primes and irreducibles in \mathbb F_p[x] are self-certifying.

Cited by

• On irreducible factors of polynomials over integers

Related

• Polynomials in Base x and the Prime-Irreducible Affinity
• Using approximate roots for irreducibility and equi-singularity issues\n in K[[x]][y]
• Another irreducibility criterion
• An irreducible class of polynomials over integers
• A quasi-linear irreducibility test in K[[x]][y]