search

warlock-labs / noether

Modern, idiomatic, well documented abstract algebra for Rust
MIT License
47 stars 4 forks source link

readme

Logo

Nœther

License Crates.io Docs CI

Nœther 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.

Table of Contents

Background

Named after Emmy Nœther, 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.

Inspirations

Nœther draws inspiration from several existing libraries and projects in the field of computational algebra:

  1. simba: A Rust crate for SIMD-accelerated algebra.

  2. 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.

  3. 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. Nœther 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:

Nœther also draws insights from academic papers in the field:

Nœther 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.

Features

Installation

Add this to your Cargo.toml:

[dependencies]
noether = "0.1.0"

Usage

Here is a rough example of Z₅ (integers modulo 5) using Nœther:

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 Nœther, leveraging Rust's native operators and traits.

Core Concepts

  1. Algebraic Structures: Traits representing mathematical structures with specific properties and operations.
  2. Marker Traits: Traits like Associative and Commutative for compile-time property checks.
  3. Blanket Implementations: Automatic implementations of higher-level traits based on more fundamental ones.
  4. Zero-Cost Abstractions: Leveraging Rust's type system for efficiency without runtime overhead.
  5. Extensibility: The library is designed to be easily extended with new types and structures.
  6. Type Safety: Ensuring operations maintain closure within the same type and catching errors at compile-time.

Hierarchy of Algebraic Structures

                              ┌─────┐
                              │ 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   │
                  └───────────┘

Operator Traits for Algebraic Structures

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:

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. Type Safety: These traits help in catching type-related errors at compile-time, ensuring that operations maintain closure within the same type.

  6. 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.

API Overview

Nœther provides traits for various algebraic structures, including:

Each 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.

Advanced Usage

Nœther'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.

Performance

Nœther 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.

Roadmap

Future plans for Nœther include:

Contributing

Contributions are welcome! Please feel free to submit issues, feature requests, or pull requests on the GitHub repository.

License

This project is licensed under the MIT License - see the LICENSE file for details.

We hope that Nœther 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 Nœther!