Crate finitelib

finitelib is a library for advanced maths over finite groups, fields, their extensions, multi precision operations and related things.

At the moment the library supports:

• Finite groups
• Finite fields (prime - GF(p), splitting - GF(p^m), binary - GF(2^m), Montgomery representation)
• Euclidean rings (including modular operations)
• Polynomials
• Multi precision operations over unsigned integers
  • Converting
  • Formatting
  • Basic operations: addition, subtraction, product, division, bitwise operations
  • Prime numbers: Fermat test, Miller-Rabin test, Legendre symbol, Tonelli–Shanks algorithm

Usage

Installation command:

cargo add finitelib

Basic example

use finitelib::prelude::*;
use finitelib::gf::prime::Prime as GF;

// Define 256-bit unsigned integer type
type U256 = bigi_of_bits!(256);

// Define an Euclidean ring over U256, that contains the correct basic
// math operations like addition, multiplication, Euclidean extended
// algorithm and so on.
let R256 = bigi_ring_for_bigi!(U256);

// Define a 256-bit prime number
let p = U256::from_decimal("67096435317933606252190858377894931905843553631817376158639971807689379094463");

// Define a finite field `GF(p)` with the prime characteristic `p`
let gf = GF::new(R256, p);

// Define two arbitrary numbers
let a = U256::from(3);
let b = U256::from(2);

// Perform division a / b inside the field
let c = gf.div(&a, &b).unwrap();

// Print the result as a decimal string
println!("{:?}", c.to_decimal());

// Perform multiplication
let d = gf.mul(&c, &b);

// Since multiplication is opposite to division `d` must be equal to `a`
assert_eq!(d, a);

Modules

bigi

A module for multi precision arithmetic.

common

Some common implementations for groups and fields over the standard integer and float data types.

field

A module that contains a trait for mathematical field objects.

gf

This module contains implementations of Galois fields such that prime field (GF(p)), splitting field (GF(p^m)), binary field (GF(2^m)).

group

A module that contains a trait for mathematical group objects.

polynomial

This module implements operations over polynomials over a field.

prelude

Default basic imports for traits.

ring

A module that contains a trait for Euclidean rings.

signed

Signed is a wrapper that attaches a sign bit to a type that is supposed to be unsigned originally.

utils

Additional functions and algorithms.

Macros

bigi_of_bits

A macros that generates a Bigi data type calculating the size of the inner array from given number of bits that should be multiple of 64 (bit size of u64 unit).

bigi_ring_for_bigi

Define BigiRing (a ring for Bigi numbers) from the type Bigi.

bigi_ring_of_bits

Define BigiRing (a ring for Bigi numbers) from the number of bits.

bigi_xor_ring_for_bigi

Define BigiXorRing (a ring for Bigi numbers) from the type Bigi.

bigi_xor_ring_of_bits

Define BigiXorRing (a ring for Bigi numbers) from the number of bits.