Verifying that an arithmetic circuit correctly computes multiplication requires reasoning about polynomials with coefficients that grow exponentially in the bit width. A 128-bit multiplier produces intermediate values with hundreds of digits. The verification is correct but computationally dominated by big-integer arithmetic — not by the logical structure of the proof, but by the size of the numbers in it.
Note (2026-11-13; read against the paper's full text, version 2 of May 2026): the paper does not say the hard step is done once. In its tool, circuit encoding, preprocessing and subcircuit extraction are done serially and shared across primes, but the guess, prove and repair steps (guessing linear relations from sampled assignments, proving them by SAT solving, and repairing them) are parallelised across the moduli, with each thread handling one prime; sampling is parallelised separately. In the rewriting it describes monomials as stored once, with each coefficient stored as a vector of residues, one per prime. The paper's own size example is that the specification of a 64-bit multiplier contains coefficients up to 2 to the power 127 (about 39 digits), not the 'hundreds of digits' for a 128-bit multiplier in the essay. It says the Chinese remainder theorem ensures correctness over the integers provided sufficiently many primes are used (its Theorem 2 gives the condition), and it describes homomorphic images as a classical tool in computer algebra whose use for this setting it believes to be new. Its claim in the abstract is that hybrid multimodular reasoning significantly improves on existing approaches on a suite of multiplier benchmarks, in the tool TalisMan2.0. The essay's reading that the bottleneck is arithmetic and not the logic of the proof is the essay's.
Hofstadler, Kaufmann, and Chen eliminate the big integers by working modulo small primes. Instead of one verification over enormous coefficients, they run many verifications in parallel, each modulo a different prime, where all arithmetic fits in machine words. The Chinese Remainder Theorem guarantees that if the verification succeeds modulo enough independent primes, it succeeds over the integers.
The technique — multimodular reasoning with homomorphic images — is classical in computer algebra. What makes it work here is the structure of circuit verification: the polynomial rewriting steps are the same regardless of the modulus, so the parallel computations share the proof skeleton and differ only in the arithmetic. The hard part (finding the right rewriting sequence) is done once; the expensive part (computing with large coefficients) is replaced by cheap parallel copies.
The through-claim: the bottleneck in formal verification of arithmetic circuits is not the formality or the verification but the arithmetic. The logical structure of the proof is manageable; the numerical bookkeeping is what explodes. Modular decomposition separates these concerns — do the logic once, do the arithmetic in parallel on small numbers, and reconstruct the result. The proof doesn't get simpler; the numbers do. Sometimes the obstacle to verifying a computation isn't understanding it but affording the numbers it produces.