binius_circuits/bignum/
big_uint_mod_pow.rs

1// Copyright 2025 Irreducible Inc.
2//! BigUint mod pow hint implementation
3
4use binius_core::Word;
5use binius_frontend::{CircuitBuilder, Wire, hints::Hint};
6
7use super::num_biguint_from_u64_limbs;
8
9pub struct BigUintModPowHint;
10
11impl BigUintModPowHint {
12	pub const fn new() -> Self {
13		Self
14	}
15
16	/// Modular exponentiation.
17	///
18	/// Computes `(base^exp) % modulus`.
19	/// This is a hint - a deterministic computation that happens only on the prover side.
20	/// The result should be additionally constrained using bignum circuits.
21	pub fn call(
22		builder: &CircuitBuilder,
23		base: &[Wire],
24		exp: &[Wire],
25		modulus: &[Wire],
26	) -> Vec<Wire> {
27		let inputs: Vec<Wire> = base.iter().chain(exp).chain(modulus).copied().collect();
28		builder.call_hint(Self::new(), &[base.len(), exp.len(), modulus.len()], &inputs)
29	}
30}
31
32impl Default for BigUintModPowHint {
33	fn default() -> Self {
34		Self::new()
35	}
36}
37
38impl Hint for BigUintModPowHint {
39	const NAME: &'static str = "binius.biguint_mod_pow";
40
41	fn shape(&self, dimensions: &[usize]) -> (usize, usize) {
42		let [n_base_limbs, n_exp_limbs, n_modulus_limbs] = dimensions else {
43			panic!("BigUintModPowHint requires 3 dimensions");
44		};
45		(*n_base_limbs + *n_exp_limbs + *n_modulus_limbs, *n_modulus_limbs)
46	}
47
48	fn execute(&self, dimensions: &[usize], inputs: &[Word], outputs: &mut [Word]) {
49		let [n_base_limbs, n_exp_limbs, n_modulus_limbs] = dimensions else {
50			panic!("BigUintModPowHint requires 3 dimensions");
51		};
52
53		assert_eq!(inputs.len(), *n_base_limbs + *n_exp_limbs + *n_modulus_limbs);
54		assert_eq!(outputs.len(), *n_modulus_limbs);
55
56		let (base_limbs, inputs) = inputs.split_at(*n_base_limbs);
57		let (exp_limbs, modulus_limbs) = inputs.split_at(*n_exp_limbs);
58
59		let base = num_biguint_from_u64_limbs(base_limbs.iter().map(|w| w.as_u64()));
60		let exp = num_biguint_from_u64_limbs(exp_limbs.iter().map(|w| w.as_u64()));
61		let modulus = num_biguint_from_u64_limbs(modulus_limbs.iter().map(|w| w.as_u64()));
62
63		let modpow = base.modpow(&exp, &modulus);
64
65		// Fill modpow limbs (first part of the output)
66		for (i, limb) in modpow.iter_u64_digits().enumerate() {
67			outputs[i] = Word::from_u64(limb);
68		}
69
70		for i in modpow.iter_u64_digits().len()..*n_modulus_limbs {
71			outputs[i] = Word::ZERO;
72		}
73	}
74}
75
76#[cfg(test)]
77mod tests {
78	use super::*;
79
80	#[test]
81	fn test_mod_pow_hint() {
82		let builder = CircuitBuilder::new();
83
84		let c = builder.add_constant_64(0x123456789abcdef0);
85		let modpow = BigUintModPowHint::call(&builder, &[c], &[c, c], &[c, c, c]);
86
87		// A hint emits no constraint of its own, so pinning alone leaves these uncommitted.
88		// Promoting them to public outputs is what the test needs to read them back.
89		for &wire in &modpow {
90			builder.mark_inout(wire);
91		}
92
93		let circuit = builder.build();
94		let mut w = circuit.new_witness_filler();
95		circuit.populate_wire_witness(&mut w).unwrap();
96
97		assert_eq!(modpow.len(), 3);
98		assert_eq!(w[modpow[0]], Word(0x6f151e00d2c39f30));
99		assert_eq!(w[modpow[1]], Word(0xfef75acc27ead52f));
100		assert_eq!(w[modpow[2]], Word(0x00443adf222ea27));
101	}
102}
binius_circuits/bignum/big_uint_mod_pow.rs

binius_circuits/bignum/
big_uint_mod_pow.rs
