binius_frontend/compiler/hints/
big_uint_mod_pow.rs

1// Copyright 2025 Irreducible Inc.
2//! BigUint mod pow hint implementation
3
4use binius_core::Word;
5
6use super::Hint;
7use crate::util::num_biguint_from_u64_limbs;
8
9pub struct BigUintModPowHint;
10
11impl BigUintModPowHint {
12	pub fn new() -> Self {
13		Self
14	}
15}
16
17impl Default for BigUintModPowHint {
18	fn default() -> Self {
19		Self::new()
20	}
21}
22
23impl Hint for BigUintModPowHint {
24	const NAME: &'static str = "binius.biguint_mod_pow";
25
26	fn shape(&self, dimensions: &[usize]) -> (usize, usize) {
27		let [n_base_limbs, n_exp_limbs, n_modulus_limbs] = dimensions else {
28			panic!("BigUintModPowHint requires 3 dimensions");
29		};
30		(*n_base_limbs + *n_exp_limbs + *n_modulus_limbs, *n_modulus_limbs)
31	}
32
33	fn execute(&self, dimensions: &[usize], inputs: &[Word], outputs: &mut [Word]) {
34		let [n_base_limbs, n_exp_limbs, n_modulus_limbs] = dimensions else {
35			panic!("BigUintModPowHint requires 3 dimensions");
36		};
37
38		assert_eq!(inputs.len(), *n_base_limbs + *n_exp_limbs + *n_modulus_limbs);
39		assert_eq!(outputs.len(), *n_modulus_limbs);
40
41		let (base_limbs, inputs) = inputs.split_at(*n_base_limbs);
42		let (exp_limbs, modulus_limbs) = inputs.split_at(*n_exp_limbs);
43
44		let base = num_biguint_from_u64_limbs(base_limbs.iter().map(|w| w.as_u64()));
45		let exp = num_biguint_from_u64_limbs(exp_limbs.iter().map(|w| w.as_u64()));
46		let modulus = num_biguint_from_u64_limbs(modulus_limbs.iter().map(|w| w.as_u64()));
47
48		let modpow = base.modpow(&exp, &modulus);
49
50		// Fill modpow limbs (first part of the output)
51		for (i, limb) in modpow.iter_u64_digits().enumerate() {
52			outputs[i] = Word::from_u64(limb);
53		}
54
55		for i in modpow.iter_u64_digits().len()..*n_modulus_limbs {
56			outputs[i] = Word::ZERO;
57		}
58	}
59}
binius_frontend/compiler/hints/big_uint_mod_pow.rs

binius_frontend/compiler/hints/
big_uint_mod_pow.rs
