Modular arithmetic — fast exponentiation and Fermat primality pow_mod(base, exp, m) is a builtin doing square-and-multiply mod m
Fermat's little theorem: if p is prime then a^(p-1) ≡ 1 (mod p) for any a coprime to p. We use it as a probable-prime witness. modinv finds a^-1 via Fermat when the modulus is prime: a^(p-2) mod p.
A Soma program from the math part of the verified corpus: 54 lines, cells Modular, ModularTests. It passes soma check with soma 3.2.4.
How it is built
The cell Modular declares 3 signals in its face: fermat_witness(a: Int, p: Int) -> Bool, modinv(a: Int, p: Int) -> Int and run() -> Map. Handlers: fermat_witness (line 20), modinv (line 25) and run (line 30).
The file also holds 1 test cell (ModularTests) with 5 assertions, run by soma test.
The source
modular.cell
// ============================================================================
// Modular arithmetic — fast exponentiation and Fermat primality
// ============================================================================
//
// pow_mod(base, exp, m) is a builtin doing square-and-multiply mod m. Fermat's
// little theorem: if p is prime then a^(p-1) ≡ 1 (mod p) for any a coprime to
// p. We use it as a probable-prime witness. modinv finds a^-1 via Fermat when
// the modulus is prime: a^(p-2) mod p.
//
// soma run modular.cell run
// ============================================================================
cell Modular {
face {
signal fermat_witness(a: Int, p: Int) -> Bool
signal modinv(a: Int, p: Int) -> Int
signal run() -> Map
}
on fermat_witness(a: Int, p: Int) {
// probable prime if a^(p-1) == 1 mod p
return pow_mod(a, p - 1, p) == 1
}
on modinv(a: Int, p: Int) {
// inverse of a mod prime p is a^(p-2) by Fermat
return pow_mod(a, p - 2, p)
}
on run() {
return map(
"3pow100_mod7", pow_mod(3, 100, 7),
"fermat_13", fermat_witness(2, 13),
"fermat_15", fermat_witness(2, 15),
"inv_3_mod_11", modinv(3, 11)
)
}
}
cell test ModularTests {
rules {
// 3^100 mod 7: 3^6 = 1 mod 7, 100 = 6*16+4, 3^4 = 81 = 4 mod 7
assert pow_mod(3, 100, 7) == 4
// 13 is prime: base 2 is a witness
assert fermat_witness(2, 13)
// 15 is composite: base 2 exposes it
assert fermat_witness(2, 15) == false
// 3 * 4 = 12 = 1 mod 11, so inverse of 3 mod 11 is 4
assert modinv(3, 11) == 4
// verify the inverse round-trips
assert (3 * modinv(3, 11)) % 11 == 1
}
}What the toolchain says
$ soma check modular.cell
✓ All checks passed.$ soma test modular.cell
test ModularTests ...
✓ assert pow_mod(3, 100, 7) == 4
✓ assert fermat_witness(2, 13)
✓ assert fermat_witness(2, 15) == false
✓ assert modinv(3, 11) == 4
✓ assert (3 * modinv(3, 11)) % 11 == 1
5 tests: 5 passed, 0 failed$ soma verify modular.cell
Verifying modular.cell...
No state machine in this program: nothing to prove beyond `soma check` (invariants and lifecycles are what verify proves).
VERIFY OK (vacuous — no state machine)$ soma run modular.cell run
{"3pow100_mod7": 4, "fermat_13": true, "fermat_15": false, "inv_3_mod_11": 4}