circuit

Efficient modular arithmetic computations using arithmetic circuits.

This module provides a type-safe way to perform modular arithmetic operations using arithmetic circuits. It is particularly useful for implementing cryptographic algorithms and other computations that require efficient modular arithmetic with large numbers.

Core Features

• Modular arithmetic operations (add, subtract, multiply, inverse)
• Support for numbers up to 384 bits
• Type-safe circuit construction
• Efficient evaluation of complex expressions

Examples

Basic Arithmetic

Here’s an example showing basic modular arithmetic operations:

use core::circuit::{
   CircuitElement, EvalCircuitTrait, CircuitOutputsTrait, CircuitInput, CircuitModulus,
   AddInputResultTrait, CircuitInputs, circuit_add, circuit_mul,
};

// Compute (a + b) * c mod p
let a = CircuitElement::<CircuitInput<0>> {};
let b = CircuitElement::<CircuitInput<1>> {};
let c = CircuitElement::<CircuitInput<2>> {};

let sum = circuit_add(a, b);
let result = circuit_mul(sum, c);

// Evaluate with inputs [3, 6, 2] modulo 7
let modulus = TryInto::<_, CircuitModulus>::try_into([7, 0, 0, 0]).unwrap();
let outputs = (result,)
    .new_inputs()
    .next([3, 0, 0, 0])
    .next([6, 0, 0, 0])
    .next([2, 0, 0, 0])
    .done()
    .eval(modulus)
    .unwrap();

// Result: (3 + 6) * 2 mod 7 = 4
assert!(outputs.get_output(result) == 4.into());

How It Works

The module uses a type-based approach to construct and evaluate arithmetic circuits:

1. Circuit elements are created using CircuitElement<T> where T defines their role (input or gate)
2. Basic operations combine elements into more complex expressions (chaining gates to create a circuit)
3. The final circuit is evaluated with specific input values and a modulus

Operations are performed using a multi-limb representation for large numbers, with each number represented as four 96-bit limbs allowing for values up to 384 bits.

Performance Considerations

• Circuit evaluation is optimized for large modular arithmetic operations
• The multi-limb representation allows efficient handling of large numbers
• Circuit construction has zero runtime overhead due to type-based approach

Errors

Circuit evaluation can fail when computing multiplicative inverses of non-invertible elements, in which case it returns an Error.

Note that a modulus of 0 or 1 is rejected at CircuitModulus construction (try_into returns None), so it never reaches evaluation.

Fully qualified path: core::circuit

Structs

Type aliases

Extern types