Crates.io | noether |
lib.rs | noether |
version | |
source | src |
created_at | 2024-07-15 02:36:38.86893 |
updated_at | 2024-07-15 02:36:38.86893 |
description | Abstract algebraic structures for Rust |
homepage | https://github.com/warlock-labs/noether |
repository | https://github.com/warlock-labs/noether |
max_upload_size | |
id | 1303389 |
size | 0 |
Noether provides traits and blanket implementations for algebraic structures, from basic ones like magmas to more complex ones like fields. It leans heavily on the basic traits available in std::ops and num_traits.
Named after Emmy Noether, a pioneering mathematician in abstract algebra, this library aims to bridge the gap between abstract mathematics and practical programming in Rust. It enables developers to work with mathematical concepts in a type-safe, efficient, and expressive manner.
The goal is to provide a common interface for working with algebraic structures in Rust. Interestingly, these traits can be used to categorize implementations of various structs based on the properties they satisfy, and be applied in most cases for anything from scalar values to n-dimensional arrays.
Noether draws inspiration from several existing libraries and projects in the field of computational algebra:
simba: A Rust crate for SIMD-accelerated algebra.
alga: A Rust library for abstract algebra, providing solid mathematical abstractions for algebra-focused applications. alga defines and organizes basic building blocks of general algebraic structures through trait inheritance.
algebra: A Rust library for abstract algebra that organizes a wide range of structures into a logically consistent framework. It aims to create composable libraries and APIs based on algebraic classifications.
These libraries demonstrate the power and utility of representing algebraic structures in programming languages. Noether builds upon their ideas, aiming to provide a comprehensive and ergonomic framework for working with algebraic structures in Rust.
Other notable inspirations from different programming languages include:
Noether also draws insights from academic papers in the field:
Noether aims to bring the best ideas from these libraries and research to the Rust ecosystem, while taking advantage of Rust's unique features like zero-cost abstractions and powerful type system.
Add this to your Cargo.toml
:
[dependencies]
noether = "0.1.0"
Here is a rough example of Z₅ (integers modulo 5) using Noether:
use noether::{Field};
use std::ops::{Add, Sub, Mul, Div, Neg};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Z5(u8);
impl Z5 {
fn new(n: u8) -> Self {
Z5(n % 5)
}
}
impl Add for Z5 {
type Output = Self;
fn add(self, rhs: Self) -> Self {
Z5((self.0 + rhs.0) % 5)
}
}
impl Sub for Z5 {
type Output = Self;
fn sub(self, rhs: Self) -> Self {
self + (-rhs)
}
}
impl Mul for Z5 {
type Output = Self;
fn mul(self, rhs: Self) -> Self {
Z5((self.0 * rhs.0) % 5)
}
}
impl Div for Z5 {
type Output = Self;
fn div(self, rhs: Self) -> Self {
if rhs.0 == 0 {
panic!("Division by zero in Z5");
}
self * rhs.multiplicative_inverse().unwrap()
}
}
impl Neg for Z5 {
type Output = Self;
fn neg(self) -> Self {
Z5((5 - self.0) % 5)
}
}
impl Field for Z5 {
fn multiplicative_inverse(&self) -> Option<Self> {
match self.0 {
0 => None,
1 | 4 => Some(*self),
2 => Some(Z5(3)),
3 => Some(Z5(2)),
_ => unreachable!(),
}
}
}
This example shows how to construct a well factored finite field using Noether, leveraging Rust's native operators and traits.
Associative
and Commutative
for compile-time property checks. ┌─────┐
│ Set │
└──┬──┘
│
┌──▼──┐
│Magma│
└──┬──┘
┌────────────────┼────────────────┐
│ │ │
┌─────▼─────┐ ┌─────▼─────┐ ┌─────▼─────┐
│Quasigroup │ │ Semigroup │ │Semilattice│
└─────┬─────┘ └─────┬─────┘ └───────────┘
│ │
┌───▼───┐ ┌───▼───┐
│ Loop │ │Monoid │
└───┬───┘ └───┬───┘
│ │
└────────┐ ┌─────┘
│ │
┌──▼─▼──┐
│ Group │
└───┬───┘
│
┌────────▼────────┐
│ Abelian Group │
└────────┬────────┘
│
┌────▼────┐
│Semiring │
└────┬────┘
│
┌────▼────┐
│ Ring │
└────┬────┘
┌───────────────────────┐
│ │
┌─────▼─────┐ ┌─────▼─────┐
│ Module │ │Commutative│
└───────────┘ │ Ring │
└─────┬─────┘
│
┌────────▼────────┐
│ Integral Domain │
└────────┬────────┘
│
┌─────────────▼─────────────┐
│Unique Factorization Domain│
└─────────────┬─────────────┘
│
┌───────────▼───────────┐
│Principal Ideal Domain │
└───────────┬───────────┘
│
┌────────▼────────┐
│Euclidean Domain │
└────────┬────────┘
│
┌───▼───┐
│ Field │────────────────────────┐
└───┬───┘ │
┌─────────┴──────────┐ │
│ │ │
┌─────▼─────┐ ┌─────▼─────┐ ┌─────▼─────┐
│ Finite │ │ Infinite │ │ Vector │
│ Field │ │ Field │ │ Space │
└─────┬─────┘ └───────────┘ └───────────┘
│
┌─────▼─────┐
│ Field │
│ Extension │
└─────┬─────┘
│
┌─────▼─────┐
│ Extension │
│ Tower │
└───────────┘
This module defines traits for various operators and their properties, providing a foundation for implementing algebraic structures in Rust.
An algebraic structure consists of a set with one or more binary operations. Let $S$ be a set (Self) and $\bullet$ be a binary operation on $S$. Here are the key properties a binary operation may possess, organized from simplest to most complex:
Additional properties to be implemented:
The traits and blanket implementations provided serve several important purposes:
Closure: All Closed*
traits ensure that operations on a type always produce a result of the same type. This is
crucial for defining algebraic structures.
Reference Operations: The *Ref
variants of traits allow for more efficient operations when the right-hand side can
be borrowed, which is common in many algorithms.
Marker Traits: Traits like Commutative
, Associative
, etc., allow types to declare which algebraic properties they
satisfy. This can be used for compile-time checks and to enable more generic implementations of algorithms.
Extensibility: New types that implement the standard traits (like Add
, Sub
, etc.) will automatically get the
closed trait implementations, making the system more extensible and future-proof.
Type Safety: These traits help in catching type-related errors at compile-time, ensuring that operations maintain closure within the same type.
Generic Programming: These traits enable more expressive generic programming, allowing functions and structs to be generic over types that are closed under certain operations or satisfy certain algebraic properties.
Noether provides traits for various algebraic structures, including:
Magma
: Set with a binary operationSemigroup
: Associative magmaMonoid
: Semigroup with identity elementGroup
: Monoid where every element has an inverseRing
: Set with two operations (addition and multiplication) satisfying certain axiomsField
: Commutative ring where every non-zero element has a multiplicative inverseVectorSpace
: An abelian group with scalar multiplication over a fieldModule
: Similar to a vector space, but over a ring instead of a fieldPolynomial
: Represents polynomials over a fieldFieldExtension
: Represents field extensionsEach trait comes with methods defining the operations and properties of the respective algebraic structure. For a complete list of traits and their methods, please refer to the API documentation.
Noether's power lies in its ability to express complex mathematical concepts and algorithms generically. Here's an
example of a function that works with any type implementing the Field
trait:
use noether::Field;
fn polynomial_evaluation<F: Field>(coefficients: &[F], x: F) -> F {
coefficients.iter().rev().fold(F::zero(), |acc, &c| acc * x + c)
}
// This function works for any type implementing the Field trait
You can use this function with any type that implements the Field
trait, whether it's a built-in numeric type or a
custom type like our Z5
from the earlier example.
Noether is designed with performance in mind, leveraging Rust's zero-cost abstractions. The use of trait-based polymorphism allows for efficient, monomorphized code when used with concrete types.
However, as with any abstract library, be aware that extensive use of dynamic dispatch (e.g., through trait objects) may incur some runtime cost. In most cases, the compiler can optimize away the abstractions, resulting in performance equivalent to hand-written implementations.
Future plans for Noether include:
Contributions are welcome! Please feel free to submit issues, feature requests, or pull requests on the GitHub repository.
This project is licensed under the MIT License - see the LICENSE file for details.
We hope that Noether will be a valuable tool for cryptographers, mathematicians, scientists, and developers working with algebraic structures in Rust. If you have any questions, suggestions, or feedback, please don't hesitate to open an issue on our GitHub repository or contact the maintainers.
Happy coding with Noether!