js-mlkem-negacyclic-ntt-montgomery-reduction
Done. I diagnosed the problem class, built and ran a fully verified implementation, and wrote the solution to ~/SOLUTION.md with the runnable code at ~/mlkem_ntt.js (exit 0, 22/22 checks pass).
Five root causes account for essentially every bug in an ML-KEM NTT port:
Zeta table — must be ZETA[i] = 17^{BitRev7(i)} mod 3329 (first values 1,1729,2580,3289,…,848). The requested failure mode, ZETA[7], is 17^{112}=848, not 17^7=2804; corrupting it breaks round-trip at index 32.
Montgomery REDC yields a signed representative — for 0 ≤ a < q·R, (a − t·q)/R ∈ (−q, q). I verified REDC(1) = −3160 ≡ 169. The fix is if (u<0) u+=q, and an arithmetic >> (never >>>) because the intermediate is negative.
Overflow near 2³¹ — an unreduced coefficient can reach N(q−1)=851968, and 851968·(q−1)=2835349504 > 2³¹. A lazy version wraps (Math.imul → −1459617792) and diverges from the BigInt reference. Fix: reduce to [0,q) at every butterfly (keeps Montgomery domain a < q·R).
Inverse normalization is 3303, i.e. 128⁻¹ = 2·256⁻¹, because the FIPS butterfly pair leaves a factor of 128. The naive 256⁻¹ = 3316 leaves the result scaled by 2.
NTT-domain multiplication is the base case, not componentwise: the 7-level NTT splits X²⁵⁶+1 into 128 quadratics, so MultiplyNTTs with γ_i = 17^{2·BitRev7(i)+1} is required.
The verification section includes the FIPS constants, the independent BigInt reference, schoolbook negacyclic convolution, and deliberately-falsifying tests for all five bug classes.
# Evidence - Problem class: js-mlkem-negacyclic-ntt-montgomery-reduction - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-12T23:01:22.286Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement the FIPS 203 (ML-KEM/Kyber) negacyclic number-theoretic transform over Z_3329: generate the zeta table from a primitive 256th root of unity, do an in-place Cooley-Tukey butterfly with Montgomery and Barrett reduction in 32-bit integer arithmetic, and the inverse NTT with the n^-1 scaling factor. Verify round-trip identity and that NTT-domain pointwise multiplication of two degree-256 polynomials equals schoolbook negacyclic convolution modulo x^256+1 for randomized coefficients, then show the failure mode when the 7th power of the root is wrong (also check for negative-representative and overflow bugs near 2^31).", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "js-mlkem-negacyclic-ntt-montgomery-reduction", "provider": "openrouter", "solved_at": "2026-09-12T23:01:22.287Z", "version": "20"}Done. I diagnosed the problem class, built and ran a fully verified implementation, and wrote the solution to ~/SOLUTION.md with the runnable code at ~/mlkem_ntt.js (exit 0, 22/22 checks pass).
Five root causes account for essentially every bug in an ML-KEM NTT port:
Zeta table — must be ZETA[i] = 17^{BitRev7(i)} mod 3329 (first values 1,1729,2580,3289,…,848). The requested failure mode, ZETA[7], is 17^{112}=848, not 17^7=2804; corrupting it breaks round-trip at index 32.
Montgomery REDC yields a signed representative — for 0 ≤ a < q·R, (a − t·q)/R ∈ (−q, q). I verified REDC(1) = −3160 ≡ 169. The fix is if (u<0) u+=q, and an arithmetic >> (never >>>) because the intermediate is negative.
Overflow near 2³¹ — an unreduced coefficient can reach N(q−1)=851968, and 851968·(q−1)=2835349504 > 2³¹. A lazy version wraps (Math.imul → −1459617792) and diverges from the BigInt reference. Fix: reduce to [0,q) at every butterfly (keeps Montgomery domain a < q·R).
Inverse normalization is 3303, i.e. 128⁻¹ = 2·256⁻¹, because the FIPS butterfly pair leaves a factor of 128. The naive 256⁻¹ = 3316 leaves the result scaled by 2.
NTT-domain multiplication is the base case, not componentwise: the 7-level NTT splits X²⁵⁶+1 into 128 quadratics, so MultiplyNTTs with γ_i = 17^{2·BitRev7(i)+1} is required.
The verification section includes the FIPS constants, the independent BigInt reference, schoolbook negacyclic convolution, and deliberately-falsifying tests for all five bug classes.
# Evidence - Problem class: js-mlkem-negacyclic-ntt-montgomery-reduction - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-09-12T23:01:22.286Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Implement the FIPS 203 (ML-KEM/Kyber) negacyclic number-theoretic transform over Z_3329: generate the zeta table from a primitive 256th root of unity, do an in-place Cooley-Tukey butterfly with Montgomery and Barrett reduction in 32-bit integer arithmetic, and the inverse NTT with the n^-1 scaling factor. Verify round-trip identity and that NTT-domain pointwise multiplication of two degree-256 polynomials equals schoolbook negacyclic convolution modulo x^256+1 for randomized coefficients, then show the failure mode when the 7th power of the root is wrong (also check for negative-representative and overflow bugs near 2^31).", "environment": "node20", "language": "js", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "js-mlkem-negacyclic-ntt-montgomery-reduction", "provider": "openrouter", "solved_at": "2026-09-12T23:01:22.287Z", "version": "20"}