binius_core/protocols/gkr_exp/
mod.rs

1// Copyright 2025 Irreducible Inc.
2
3//! Exponentiation via GKR.
4//!
5
6//! Let's represent $A$ by its bits, i.e., for each $v \in B_\ell$ we have $A(v)= \sum_{i=0}^{n-1} 2^{i} \cdot b_{i}(v)$.
7//! Then, exponentiation can be split into cases, each with its own circuit.
8//!
9
10//! 1) Exponentiation of the generator by a chunk of bit-columns:
11//!
12//!     $V_0(X) = 1 - a_0(X) + a_0(X) \cdot g$
13//!  
14//!     $V_{1}(X) = \sum_{v \in B_\ell} \tilde{\mathbf{eq}}(v, X) \cdot V_{0}(v) \cdot \left(1 - a_{1}(v) + a_{1}(v) \cdot g^{2} \right)$
15//!
16//!     ...
17//!
18//!     $V_n(X) = \sum_{v \in B_\ell} \tilde{\mathbf{eq}}(v, X) \cdot V_{n-2}(v) \cdot \left(1 - a_{n-1}(v) + a_{n-1}(v) \cdot g^{2^{n-1}} \right)$
19//!
20
21//! 2) Exponentiation of the multilinear base by a chunk of bit-columns:
22//!
23//!     $W_0(X) = \sum_{v \in B_\ell} \tilde{\mathbf{eq}}(v, X) \cdot (1 - a_{n-1}(v) + a_{n-1}(v) \cdot V(v))$
24//!
25//!     $W_1(X) = \sum_{v \in B_\ell} \tilde{\mathbf{eq}}(v, X) \cdot (W_0(v))^2 \cdot (1 - a_{n-2}(v) + a_{n-2}(v) \cdot V(v))$
26//!
27//!     ...
28//!
29//!     $W_{n-1}(X) = \sum_{v \in B_\ell} \tilde{\mathbf{eq}}(v, X) \cdot (W_{n-2}(v))^2 \cdot (1 - a_0(v) + a_0(v) \cdot V(v)).$
30//!  
31
32//! You can read more information in [Integer Multiplication in Binius](https://www.irreducible.com/posts/integer-multiplication-in-binius).
33
34mod batch_prove;
35mod batch_verify;
36mod common;
37mod compositions;
38mod error;
39mod provers;
40mod utils;
41mod verifiers;
42mod witness;
43
44pub use batch_prove::batch_prove;
45pub use batch_verify::batch_verify;
46pub use common::{BaseExpReductionOutput, ExpClaim};
47pub use witness::BaseExpWitness;
48
49#[cfg(test)]
50mod tests;
binius_core/protocols/gkr_exp/mod.rs

binius_core/protocols/gkr_exp/
mod.rs
