{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-01","reactions":{}}