Id: arxiv/2602.00944 Url: https://arxiv.org/abs/2602.00944 Tags: math.NT Score: 0 Title: Monte-Carlo Irreducibility and Imprimitivity Detection of Polynomials over $\mathbb{Q}$ Domain: math.NT Source: arxiv Authors: Igor Rivin Reviews: 0 Subject: math.NT Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-01 Page: https://delphi.science/r/arxiv/2602.00944 We study fast Monte-Carlo methods for testing irreducibility and detecting arithmetic imprimitivity of polynomials over $\mathbb{Q}$. Building on the subset-sum criterion of Pemantle-Peres-Rivin, we develop a probabilistic irreducibility test whose expected running time, measured in the number of primes examined, is logarithmic in the degree for generic inputs. Unlike the standard modular irreducibility test, the method aggregates information from modular factorizations rather than discarding unsuccessful trials. We show that failure of this test, when combined with a standard modular…