Finite-field factorization: defer the new backend, test exact audit integration

9 October 2026. The first product recommendation remains the Facility Plan Auditor. This review narrows opportunity 016 to a low-confidence specialist integration and adds a conventional bounded checker. No source theorem or competitive backend advantage was established.

What the selected source actually requires

Family 142 takes a prime p in binary and a nonzero dense polynomial of degree n over Fp. It claims a deterministic complete factorization with monic irreducible factors and positive multiplicities in O(((n+1)L)^(10^12)) bit operations, L=ceil(log2 p). Constants return their leading coefficient and an empty factor list. This is polynomial factorization over a field, not integer factorization.

The driver fixes B=20+(n+1)(L+1). At p<=B^200000 it uses an older Berlekamp-algebra scalar search. The new auxiliary-prime/geometric branch only applies beyond that inequality. Exact guard arithmetic finds the first possible upper-endpoint crossing for n=2 at L=4,753,080: 2^4,753,079 is still at most its corresponding B^200000, while 2^4,753,080 exceeds its corresponding bound. Because 2^L is an even endpoint, this is a necessary eligibility boundary, not construction of an eligible prime. Larger degree increases B. Every prime of at most 4,096 bits remains in the old branch for n>=2.

For each prime q<=n the new branch needs a prime ell not in {2,3,p,q}, with ell=1 mod 12q and p^((ell-1)/q) unequal to 1 mod ell. The algebraic reduction is polynomial in the numeric largest auxiliary prime E, not merely its bit length. The paper gives O(B^500000+B^100 E^20), and an auxiliary bound ell<=c0 B^20000000 with an unselected absolute constant c0. Substitution yields exponent 400000100 before the looser headline bound. These upper bounds do not establish a runtime lower bound, nor show that every run consumes them. They supply no demonstrated practical advantage.

The table is assembled in increasing q: factoring Phi_q only requires degrees q-1 and earlier entries. This is the paper's claimed way to avoid a circular factorization oracle. Large divisor coefficients are stored in binary and principal functions in circuits; their numerical magnitudes must not automatically be treated as loop counts. The norm/divisor construction and its geometric correctness were not fully reviewed or implemented.

The analytic dependency is stronger than infinitude of primitive roots

The exact input is companion family 029, Theorem 1.2 of Primitive roots for every admissible integer base. It claims a zero-free strip Re(s)>1-10^-6 for every finite-order Hecke character over every cyclotomic field containing mu_12, including principal characters with their pole at one permitted. The width has no conductor or height cutoff. The introductory discussion distinguishes field-dependent constants/starting points from the shared numerical saving. Neither an all-base primitive-root infinitude statement nor an ordinary shrinking zero-free region supplies this exact input.

The factorization paper applies the strip to K=Q(mu_12q) and K(p^(1/q)), bounds discriminant/degree terms by B^3, and chooses x=T B^20000000. The relative error has the form O(T^-delta B^-17), delta=10^-6. A sufficiently large fixed T produces the asserted auxiliary-prime bound; no numerical T was selected here. The primitive-root paper in turn cites a Quasi-Riemann companion as context for mechanisms and develops its own extension. We inspected selected statement/setup sections only. The source presents its claim as unconditional; our acceptance of that dependency and the full proof remains open. Assuming the appropriate GRH would supply the required strip condition, but no conditional or unconditional source backend was executed.

A practical, conventional capability

finite_field_factorization_audit.py verifies submitted factor lists using exact modular arithmetic, deterministic prime checking, multiplication with multiplicities, and the classical Rabin irreducibility criterion. For a degree-d factor it checks x^(p^d)=x modulo the factor and gcd(x^(p^(d/q))-x,f)=1 for each prime q dividing d. Exponentiation uses repeated Frobenius steps and binary modular powering.

The accepted JSON contract uses canonical integer residues in ascending degree order, nonzero input polynomial, distinct monic positive-degree factors, positive multiplicities and the original leading coefficient. Constants use an empty factor list. Duplicate factors must be combined. The deliberately bounded implementation accepts primes at most 2^31-1, degree at most 64, at most one MiB of input, and two million charged scalar operations. These are reference limits, not customer-scale performance promises. Exhaustion returns unknown. Operation charges do not constitute a wall-clock or memory guarantee. The output hashes input bytes and checker code; hashes do not authenticate a user or prove the program correct.

A concrete false-confidence case submits x^2+3x+2 as its own supposed irreducible factor over F5. Multiplication matches perfectly; irreducibility fails. A valid nonmonic repeated-factor example accepts 2(x+1)^2 over F5. Characteristic-p repeated inputs and constants are covered by tests.

The second mode illustrates source driver Step 5 with a supplied nonscalar Frobenius-fixed separator, after checking those prerequisites and square-freeness. For (x-(p-2))(x-(p-1)) and b=x, the first successful scalar is p-2. Recorded p=101 and p=1009 cases use 100 and 1,008 trials. At p=65537, a 256-trial cap returns unknown. The source does not require every implementation to choose b=x; this is one lawful choice illustrating a scan's possible cost, not a lower bound for all algorithms. A verified divisor is not reported as a complete irreducible factorization.

Existing software and measured scope

SymPy's official documentation already describes finite-field factorization, square-free decomposition, Berlekamp, Cantor-Zassenhaus, Shoup methods and irreducibility checks. The installed SymPy 1.13.1 factored all three scan examples, with each of three recorded runs per case taking approximately 0.11-0.28 milliseconds; each output passed our separate checker. These tiny local measurements are not a general benchmark or an independent implementation of the source's new method. Saved comparisons.

FLINT's official univariate modular-polynomial documentation documents an existing algebra surface and notes that many field operations assume, without checking, a prime modulus. Explicit input validation and portable evidence can be useful integration requirements, but this does not establish a missing commercial product. The separate factorization-document URL returned 403 during review, so it supplied no additional evidence.

Validation, reading extent and business decision

456 passing controls include all 401 monic polynomials of degrees 1-6 over F2, 1-4 over F3 and 1-3 over F5. A separately implemented exhaustive monic-divisor oracle checks irreducibility and SymPy supplies complete factorizations that the new checker verifies. Additional controls cover multiplicities, constants, false factors, duplicate/noncanonical inputs, malformed JSON, resource/scan exhaustion, exact branch arithmetic and fresh-output preservation. Finite testing is not formal correctness proof.

Reading: the complete tracked factorization introduction, auxiliary table, driver, complexity and analytic-implication TeX sections; visual PDF pages 1,38,41,45. Companion reading: introduction lines 1-180, zero-detection section lines 1-160, visual PDF page 3, and both bibliographic READMEs. No full-paper review, Lean/kernel execution or source algorithm run occurred. The source-location supplement records tracked build/ TeX omitted by the preserved initial metadata. Source/file hashes and ledger preserve exact extents.

Defer a direct port of the new backend. A specialist reproducibility adapter could preserve a CAS result and rerun a separate verifier, but existing libraries already cover the mathematics. The earlier AUD 5,000-20,000 pilot range was speculative and has no supporting buyer evidence. Do not build a standalone subscription until a real team shows recurring failures, valuable evidence requirements and willingness to pay. This module can share the wider evidence platform; it is not an additional forecast customer or revenue stream.