Monte-Carlo Irreducibility and Imprimitivity Detection of Polynomials over ℚ \mathbb{Q} Thanks: The author would like to thank Ramin Takloo-Bighash for bringing this circle of question back to the author’s attention, Rich Zippel for being such a wonderful influence for the last half many years, and Yuval Peres and Robin Pemantle for developing the baase methodology for the PPR approach. Igor Rivin Abstract . 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 irreducibility certificate, is a strong indicator of non-generic algebraic structure. In particular, it often signals arithmetic imprimitivity of the Galois action. We present an explicit and efficient Monte-Carlo algorithm for detecting such imprimitivity via subfield extraction, yielding constructive algebraic certificates in the imprimitive case. To our knowledge, this is the first practical algorithm for detecting arithmetic imprimitivity of polynomials over ℚ \mathbb{Q} in high degree. We further show that the subset-sum data produced by the Pemantle–Peres–Rivin test provides a warm start for polynomial factorization by sharply restricting the possible degrees of rational factors, significantly accelerating subsequent lifting procedures. The proposed methods are orders of magnitude faster in practice than known deterministic algorithms, and are effective in degrees far beyond the reach of current deterministic techniques. 2020 Mathematics Subject Classification 11Y16, 12Y05, 12F10, 68W40 1. Introduction 1.1. Factoring, irreducibility, and Galois groups The problems of factoring polynomials over \mathbb{Q} , testing irreducibility, and determining Galois groups are central in computational algebra and number theory. Deterministic algorithms are polynomial-time in theory but can be impractical at modest degrees; modular methods scale extremely well. 1.2. The Pemantle–Peres–Rivin subset-sum criterion Given the factor degrees (d_{i}) of f\bmod p , form the subset-sum set S_{p} of all sums \sum_{i\in I}d_{i} . If f has a rational factor of degree d , then d\in S_{p} for all good primes. If the intersection over sampled primes contains no proper degrees, then f is irreducible. 1.3. Failure modes and arithmetic imprimitivity Persistent subset-sum intersections often correlate with arithmetic imprimitivity, which we exploit as a fast structure flag. 1.4. Contributions and outline We develop a hybrid Monte-Carlo irreducibility test, a Monte-Carlo imprimitivity detector producing explicit certificates, and a warm-start for factorization. 2. Algorithms and Complexity 2.1. Standard Monte-Carlo irreducibility Reduce f modulo primes and stop when f\bmod p is irreducible, certifying irreducibility over \mathbb{Q} . 2.2. The PPR-based irreducibility test Intersect subset-sum sets S_{p} across primes; under genericity assumptions the expected number of primes is O(\log n) [ 3 ] . 2.3. Hybrid algorithm Run PPR for O(\log n) primes; if inconclusive, fall back to the standard test. 2.4. Bit complexity and choice of primes Modular factorization uses \tilde{O}(n^{2}) field operations [ 1 , 2 , 4 ] ; PPR permits using much smaller primes, reducing \log p factors. 3. Arithmetic Imprimitivity Detection A transitive action of \mathrm{Gal}(f/\mathbb{Q}) on the roots is imprimitive if it preserves a nontrivial block system. Equivalently, if K=\mathbb{Q}(\alpha) is the root field, imprimitivity is equivalent to the existence of a proper intermediate field \mathbb{Q}\subsetneq M\subsetneq K . 3.1. Monte-Carlo detector We use failure of the subset-sum test (when irreducibility is nevertheless certified) as a structure flag, and then search for nontrivial subfields of K . Whenever a subfield is found, it yields a constructive certificate. 3.2. Worked example Let P(u)=u^{8}-u-1 and Q(u,x)=x^{3}+\left(-\tfrac{1}{2}u-\tfrac{3}{2}\right)x^{2}+\left(\tfrac{1}{2}u-\tfrac{3}{2}\right)x+1. Form F(x)=\operatorname{Res}_{u}(P(u),Q(u,x)) , which has degree 24 . Subfield extraction in K=\mathbb{Q}(\alpha) with F(\alpha)=0 detects a degree-8 subfield generated by a root of y^{8}+24y^{7}+252y^{6}+1512y^{5}+5670y^{4}+13608y^{3}+20412y^{2}-256296y+846369, and a relative cubic equation for \alpha over this field: x^{3}+\left(-\tfrac{1}{2}y-\tfrac{3}{2}\right)x^{2}+\left(\tfrac{1}{2}y-\tfrac{3}{2}\right)x+1=0. 4. Warm-start factorization When the subset-sum intersection does not collapse, the surviving degrees give a small candidate set D for rational factor degrees. Restricting factor searches to d\in D provides a warm start for Hensel lifting and recombination methods [ 5 , 4 ] . This reduces the degree ambiguity from \{1,\dots,n-1\} to a much smaller set and can substantially accelerate practical factorization. 5. Examples and adversarial constructions We construct imprimitive families via resultants F(x)=\operatorname{Res}_{u}(P(u),Q(u,x)) . We also construct adversarial “evil twins” by perturbing coefficients by multiples of M=\prod_{p