# bitserial-modmul — learned modular multiplication

Submission for the SAIR Modular Arithmetic Challenge. One shared, p-conditioned
recurrent cell applied in a fixed bit-serial (Horner) loop computes `(a * b) mod p`.
The cell learns the per-step transition `s' = (2*s + d*x) mod p`, including the modular
wrap; the loop only sequences bits. Answers are emitted as base-2 digits and the
harness decoder reconstructs the integer.

## Local evaluation

`modchallenge evaluate`, 1100 problems, secret-seed unseen primes (tiers 2+):

- Tiers 1-7: exact-match 1.00 each.
- highest_tier_above_90 = 7, overall_accuracy = 0.706.
- Identical on two independent seeds.

## Provenance

The capability is in the trained parameters: randomizing the weights collapses every
solved tier to 0.00 (overall 0.006). No symbolic-math libraries, no big-integer modular
arithmetic in Python, no lookup tables. The reduction and the multiplication are
performed by the trained cell; the Python loop performs no arithmetic (only bit
indexing and feeding the cell). The static-analysis check passes. Each preprocessing
hook sees only its own argument.

The cell is a ~471K-parameter bidirectional GRU. It was trained from random
initialization on one-step modular transitions (modulus bit-length stratified,
wrap-boundary cases oversampled), with lr warmup + cosine decay. A single L=256 cell
covers tiers 1-7. See `manifest.json` for the full architecture and training summary.

## Interface

- `entry_class`: `model.BitSerialReducer`
- `output_base`: 2
- Files: `model.py`, `manifest.json`, `weights.pt`.

## Limitation (honest)

This model passes the random-operand benchmark but is not exact. On structured inputs (powers of two and other long doubling chains) the per-step reduction drifts for some primes beyond about 500 steps, reproducing the Neural GPU limitation (Price, Zaremba, Sutskever 2016). The benchmark tiers reflect average-case accuracy on the official scorer's random-operand distribution, not worst-case exactness of the underlying modular-multiplication operator.