7 releases
0.1.6 | May 11, 2024 |
---|---|
0.1.5 | May 6, 2024 |
#372 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
- addition
- subtraction
- multiplication
- exponentiation
- inverse
- divide
- square
- square root (tonelli shanks algorithm)
- equivalent (congruent)
- Elliptical Curves
- Point addition
- 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 toU256
. - 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);
// Addition
let sum = mod_math.add(8, 12);
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 Addition
let triple_G = bn128.point_addition(&double_G, &G);
// Point Doubling
let quad_G = bn128.point_doubling(&double_G);
Number Under Modulus
use modular_math::number_mod::NumberUnderMod as NM;
use primitive_types::U256;
use modular_math::num_mod;
// Add
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
- Additive Inverse
- BigNumber Tests
- Elliptic Curves
- Galois Field
- Bilinear Pairing
License
This project is licensed under the MIT License - see the LICENSE file for details.
Dependencies
~605KB
~10K SLoC