## modular_math

A simple modular arithmetic crate for U256

### 7 releases

 0.1.6 May 11, 2024 May 6, 2024

#305 in Cryptography

37KB
748 lines

# Modular Arithmetic Library

`modular_math` is a Rust library designed for high-performance modular arithmetic operations on 256-bit integers (`U256`). This library provides robust functionalities such as

• Modular Arithmetic
• subtraction
• multiplication
• exponentiation
• inverse
• divide
• square
• square root (tonelli shanks algorithm)
• equivalent (congruent)
• Elliptical Curves
• Point doubling
• Scalar multiplication
• Scalar multiplication with Generator Point
• BN128 Curve
• Secp256k1 Curve
• Galois Fields (Work in Progress)
• Polynomial

under a specified modulus, specifically optimized for cryptographic and zero knowledge applications where such operations are frequently required.

## Features

• Comprehensive Modular Arithmetic and Elliptical Curves: Offers all the necessary modular arithmetic operations on `U256` and BN128 and Secp256k1 elliptic curves.
• Safe Overflow Management: Utilizes `U512` for intermediate results to prevent overflows.
• Flexible Type Support: Features `IntoU256` trait to convert various integer and string types to `U256`.
• High Performance: Optimized for performance without compromising on accuracy, especially suitable for cryptographic and zero knowledge applications.
• Ease of Use Macros : Provides macros for easy usage of number under a modulus.

## Structure

The workspace is organized as follows:

• src/curves/: Contains the implementation of elliptic curves and points on the curve.
• src/galois_field/: Contains the implementation of Galois fields, which are used in the elliptic curve operations.
• src/mod_math/: Contains modular arithmetic functions.
• src/num_mod/: Contains the implementation of a number modulo some modulus.

## Usage

First, add this to your `Cargo.toml`:

``````[dependencies]
modular_math = "0.1.6"
``````
##### ModMath
``````use modular_math::ModMath;
use primitive_types::U256;

let modulus = "101";
let mod_math = ModMath::new(modulus);

assert_eq!(sum, U256::from(3));

// Subtraction
let sub = mod_math.sub(8, 12);
assert_eq!(sub, U256::from(97));

// Multiplication
let mul = mod_math.mul(8, 12);
assert_eq!(mul, U256::from(96));

// Multiplicative Inverse
let inv = mod_math.inv(8);
assert_eq!(inv, U256::from(77));

// Exponentiation
let exp = mod_math.exp(8, 12);
assert_eq!(exp, U256::from(64));

// FromStr
let mod_math = ModMath::new("115792089237316195423570985008687907852837564279074904382605163141518161494337");
let div = mod_math.div("32670510020758816978083085130507043184471273380659243275938904335757337482424" , "55066263022277343669578718895168534326250603453777594175500187360389116729240");
assert_eq!(div, U256::from_dec_str("13499648161236477938760301359943791721062504425530739546045302818736391397630"));
``````
##### Elliptic Curves

Create an Elliptic Curve

``````use primitive_types::U256;
use modular_math::elliptical_curve::{Curve, ECPoint};

fn BN128() -> Curve {
let a = U256::zero();
let b = U256::from(3);
let field_modulus = U256::from_dec_str("21888242871839275222246405745257275088696311157297823662689037894645226208583").unwrap();
let curve_order = U256::from_dec_str("21888242871839275222246405745257275088548364400416034343698204186575808495617").unwrap();
let G = ECPoint::new(U256::from(1), U256::from(2));

let bn128 = Curve::new(a, b, field_modulus, curve_order, G);

bn128
}

``````

BN128 Usage

``````use modular_math::curves::BN128;
use primitive_types::U256;

let bn128 = BN128();
let G = bn128.G;

// Scalar Multiplication
let double_G = bn128.point_multiplication_scalar(2, &G);

// Point Doubling

``````
##### Number Under Modulus
``````use modular_math::number_mod::NumberUnderMod as NM;
use primitive_types::U256;
use modular_math::num_mod;

let a = num_mod!(10, 13);
let b = num_mod!(6, 13);
let sum = a + b;
assert_eq!(sum, U256::from(3));

// Sub
let sub = a - b;
assert_eq!(sub, U256::from(4));

// Mul
let mul = a * b;
assert_eq!(mul, U256::from(8));

// Div
let div = a / b;
assert_eq!(div, U256::from(11));

// Neg
let neg = -a;
assert_eq!(neg, U256::from(3));

let c = num_mod!(10, 13);
assert!(a == c);
``````

## Todo

• Square root under modulus