// ============================================================================
// 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
    }
}