noether 0.3.0

use noether::{
    AdditiveAbelianGroup, AdditiveGroup, AdditiveMagma, AdditiveMonoid, AdditiveSemigroup,
    AssociativeAddition, AssociativeMultiplication, CommutativeAddition, CommutativeMultiplication,
    MultiplicativeAbelianGroup, MultiplicativeGroup, MultiplicativeMagma, MultiplicativeMonoid,
    MultiplicativeSemigroup,
};
use num_traits::{One, Zero};
use std::fmt::{Debug, Display};
use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Neg, Sub, SubAssign};

/// Implementation of a cyclic group.
///
/// A cyclic group is a group that can be generated by a single element,
/// meaning every element of the group can be written as a power (or multiple)
/// of a single element, called a generator.
///
/// This implementation provides both additive and multiplicative cyclic groups,
/// demonstrating Noether's traits for groups and their properties.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct CyclicGroup<const N: u32> {
    /// Value in the range [0, N-1]
    value: u32,
}

impl<const N: u32> CyclicGroup<N> {
    /// Creates a new element of the cyclic group of order N
    pub fn new(value: u32) -> Self {
        assert!(N > 0, "Group order must be positive");
        Self { value: value % N }
    }

    /// Gets the underlying value
    pub fn value(&self) -> u32 {
        self.value
    }

    /// Gets the order of the group
    pub fn order() -> u32 {
        N
    }

    /// Computes the additive order of this element
    pub fn additive_order(&self) -> u32 {
        if self.value == 0 {
            return 1; // Identity element has order 1
        }

        // Find the smallest k > 0 such that k * self = 0
        let mut result = *self;
        let mut order = 1;

        while result.value != 0 {
            result += Self::new(self.value);
            order += 1;
        }

        order
    }

    /// Computes the multiplicative order of this element
    pub fn multiplicative_order(&self) -> u32 {
        if self.value == 0 {
            return u32::MAX; // Not defined for zero
        }

        // Find the smallest k > 0 such that self^k = 1
        let mut result = *self;
        let mut order = 1;

        while result.value != 1 {
            result *= Self::new(self.value);
            order += 1;

            // Safety check for when N is not prime
            if order > N {
                return u32::MAX; // Element doesn't generate a subgroup
            }
        }

        order
    }

    /// Apply the group operation n times (additive notation)
    pub fn add_n(&self, n: u32) -> Self {
        if n == 0 {
            return Self::zero();
        }

        // Compute (self + self + ... + self) n times
        // Using modular arithmetic to stay within the group
        Self::new((self.value * n) % N)
    }

    /// Apply the group operation n times (multiplicative notation)
    pub fn pow(&self, n: u32) -> Self {
        if n == 0 {
            return Self::one();
        }

        // Compute (self * self * ... * self) n times using fast exponentiation
        let mut result = Self::one();
        let mut base = *self;
        let mut exp = n;

        while exp > 0 {
            if exp % 2 == 1 {
                result *= base;
            }

            base = base * base;
            exp /= 2;
        }

        result
    }

    /// Check if this element is a generator of the group
    pub fn is_generator(&self) -> bool {
        // An element is a generator if its order equals the group order
        if N == 1 {
            return self.value == 0; // Special case for trivial group
        }

        // For prime N, every non-zero element is a generator
        // For non-prime N, we need to check if gcd(value, N) = 1
        if self.value == 0 {
            return false;
        }

        // Simple check for coprime-ness (instead of full gcd)
        let mut a = self.value;
        let mut b = N;
        while b != 0 {
            let t = b;
            b = a % b;
            a = t;
        }

        // If gcd is 1, then the element is a generator
        a == 1
    }

    /// Find all generators of the group
    pub fn generators() -> Vec<Self> {
        let mut result = Vec::new();

        for i in 0..N {
            let elem = Self::new(i);
            if elem.is_generator() {
                result.push(elem);
            }
        }

        result
    }

    /// List all elements of the group
    pub fn all_elements() -> Vec<Self> {
        (0..N).map(Self::new).collect()
    }

    /// Verify that this type satisfies group axioms using the type system
    /// This is a compile-time check that demonstrates the use of Noether's traits
    pub fn verify_group_axioms<T>()
    where
        T: AdditiveAbelianGroup + MultiplicativeAbelianGroup,
    {
        // This function body doesn't need to do anything
        // The type constraints ensure that T satisfies all group axioms
        // If CyclicGroup<N> doesn't satisfy these constraints, the function won't compile
    }
}

// Implement core operations

impl<const N: u32> Add for CyclicGroup<N> {
    type Output = Self;

    fn add(self, rhs: Self) -> Self::Output {
        Self::new(self.value + rhs.value)
    }
}

impl<const N: u32> AddAssign for CyclicGroup<N> {
    fn add_assign(&mut self, rhs: Self) {
        *self = *self + rhs;
    }
}

impl<const N: u32> Neg for CyclicGroup<N> {
    type Output = Self;

    fn neg(self) -> Self::Output {
        if self.value == 0 {
            self // -0 = 0
        } else {
            Self::new(N - self.value)
        }
    }
}

impl<const N: u32> Sub for CyclicGroup<N> {
    type Output = Self;

    fn sub(self, rhs: Self) -> Self::Output {
        self + (-rhs)
    }
}

impl<const N: u32> SubAssign for CyclicGroup<N> {
    fn sub_assign(&mut self, rhs: Self) {
        *self = *self - rhs;
    }
}

impl<const N: u32> Zero for CyclicGroup<N> {
    fn zero() -> Self {
        Self::new(0)
    }

    fn is_zero(&self) -> bool {
        self.value == 0
    }
}

impl<const N: u32> Mul for CyclicGroup<N> {
    type Output = Self;

    fn mul(self, rhs: Self) -> Self::Output {
        Self::new((self.value * rhs.value) % N)
    }
}

impl<const N: u32> MulAssign for CyclicGroup<N> {
    fn mul_assign(&mut self, rhs: Self) {
        *self = *self * rhs;
    }
}

impl<const N: u32> One for CyclicGroup<N> {
    fn one() -> Self {
        Self::new(1)
    }
}

impl<const N: u32> Div for CyclicGroup<N> {
    type Output = Self;

    fn div(self, rhs: Self) -> Self::Output {
        if rhs.value == 0 {
            panic!("Division by zero in cyclic group");
        }

        // Find multiplicative inverse of rhs
        for i in 1..N {
            if (rhs.value * i) % N == 1 {
                return Self::new((self.value * i) % N);
            }
        }

        panic!("No multiplicative inverse exists");
    }
}

impl<const N: u32> DivAssign for CyclicGroup<N> {
    fn div_assign(&mut self, rhs: Self) {
        *self = *self / rhs;
    }
}

// Implement Display
impl<const N: u32> Display for CyclicGroup<N> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.value)
    }
}

// Implement num_traits::Inv for multiplicative inverse
impl<const N: u32> num_traits::Inv for CyclicGroup<N> {
    type Output = Self;

    fn inv(self) -> Self::Output {
        if self.value == 0 {
            panic!("Attempt to invert zero in cyclic group");
        }

        // Find multiplicative inverse
        for i in 1..N {
            if (self.value * i) % N == 1 {
                return Self::new(i);
            }
        }

        panic!("No multiplicative inverse exists");
    }
}

// Implement Noether's group marker traits
impl<const N: u32> CommutativeAddition for CyclicGroup<N> {}
impl<const N: u32> AssociativeAddition for CyclicGroup<N> {}
impl<const N: u32> CommutativeMultiplication for CyclicGroup<N> {}
impl<const N: u32> AssociativeMultiplication for CyclicGroup<N> {}

// Now CyclicGroup<N> satisfies all the requirements for the group trait hierarchy
// due to Noether's blanket implementations.
// We can demonstrate this by explicitly using the trait bounds:

/// Static assertion that CyclicGroup<N> satisfies the additive group hierarchy
fn _static_assert_additive_group_traits<const N: u32>()
where
    CyclicGroup<N>:
        AdditiveMagma + AdditiveSemigroup + AdditiveMonoid + AdditiveGroup + AdditiveAbelianGroup,
{
    // The function body is empty - the type bounds are what matters
    // If CyclicGroup<N> doesn't satisfy these bounds, this function won't compile
}

/// Static assertion that CyclicGroup<N> satisfies the multiplicative group hierarchy
/// Note: In a real world scenario, we'd need to restrict N to prime values for this to work
/// For all N values, not all elements will have multiplicative inverses
fn _static_assert_multiplicative_group_traits<const N: u32>()
where
    CyclicGroup<N>: MultiplicativeMagma
        + MultiplicativeSemigroup
        + MultiplicativeMonoid
        + MultiplicativeGroup
        + MultiplicativeAbelianGroup,
{
    // The function body is empty - the type bounds are what matters
    // If CyclicGroup<N> doesn't satisfy these bounds, this function won't compile
}

/// Generate the addition table for the cyclic group
fn print_addition_table<const N: u32>() {
    println!("\nAddition Table for Cyclic Group of Order {}:", N);

    // Print header row
    print!("+ | ");
    for i in 0..N {
        print!("{:2} ", i);
    }
    println!("\n--+-{}", "-".repeat(3 * N as usize));

    // Print table rows
    for i in 0..N {
        print!("{:1} | ", i);
        for j in 0..N {
            let sum = CyclicGroup::<N>::new(i) + CyclicGroup::<N>::new(j);
            print!("{:2} ", sum.value());
        }
        println!();
    }
}

/// Generate the multiplication table for the cyclic group
fn print_multiplication_table<const N: u32>() {
    println!("\nMultiplication Table for Cyclic Group of Order {}:", N);

    // Print header row
    print!("× | ");
    for i in 0..N {
        print!("{:2} ", i);
    }
    println!("\n--+-{}", "-".repeat(3 * N as usize));

    // Print table rows
    for i in 0..N {
        print!("{:1} | ", i);
        for j in 0..N {
            let product = CyclicGroup::<N>::new(i) * CyclicGroup::<N>::new(j);
            print!("{:2} ", product.value());
        }
        println!();
    }
}

/// Demonstrate key properties of cyclic groups
fn demonstrate_cyclic_group<const N: u32>() {
    println!("=== Cyclic Group of Order {} Example ===", N);

    // Verify at compile time that our type satisfies group axioms
    // This doesn't run any code, it just verifies type constraints
    CyclicGroup::<N>::verify_group_axioms::<CyclicGroup<N>>();

    // Show group elements
    let elements = CyclicGroup::<N>::all_elements();
    print!("Group elements: ");
    for (i, e) in elements.iter().enumerate() {
        if i > 0 {
            print!(", ");
        }
        print!("{}", e);
    }
    println!();

    // Find generators
    let generators = CyclicGroup::<N>::generators();
    print!("Generators: ");
    for (i, g) in generators.iter().enumerate() {
        if i > 0 {
            print!(", ");
        }
        print!("{}", g);
    }
    println!();

    // Demonstrate group operations
    println!("\nDemonstrating group operations:");

    // Additive identity (0)
    let zero = CyclicGroup::<N>::zero();
    println!("Additive identity: {}", zero);

    // Multiplicative identity (1)
    let one = CyclicGroup::<N>::one();
    println!("Multiplicative identity: {}", one);

    // Group operations with a generator
    if !generators.is_empty() {
        let g = generators[0];
        println!("\nUsing generator g = {}:", g);

        // Show additive subgroup
        println!("Additive subgroup generated by g:");
        for i in 0..N {
            print!("{}g = {}, ", i, g.add_n(i));
        }
        println!();

        // Show inverse
        let neg_g = -g;
        println!("Additive inverse: -g = {}", neg_g);
        println!("g + (-g) = {}", g + neg_g);

        // Show multiplicative subgroup
        if g.value != 0 {
            // Skip if g is 0
            println!("\nMultiplicative subgroup generated by g:");
            for i in 0..N {
                print!("g^{} = {}, ", i, g.pow(i));
            }
            println!();

            // Show division/inverse
            let inv_g = one / g;
            println!("Multiplicative inverse: 1/g = {}", inv_g);
            println!("g * (1/g) = {}", g * inv_g);
        }
    }

    // Show operation tables
    print_addition_table::<N>();
    print_multiplication_table::<N>();
}

fn main() {
    // Demonstrate cyclic groups of different orders
    demonstrate_cyclic_group::<5>(); // Prime order - Z₅

    println!("\n\n");

    demonstrate_cyclic_group::<6>(); // Composite order - Z₆

    println!("\n\n=== Applications of Cyclic Groups ===");
    println!("1. Cryptography: Cyclic groups underpin many cryptographic protocols");
    println!("2. Error-correcting codes: Cyclic codes are based on cyclic groups");
    println!("3. Number theory: The multiplicative group (Z/nZ)* is important in number theory");
    println!("4. Group theory: Cyclic groups are the building blocks of abelian groups");

    println!("\nNoether's trait system for algebraic structures makes it possible to write");
    println!("generic algorithms that work with any type satisfying group or ring axioms.");
    println!("This example shows how cyclic groups implement both additive and multiplicative");
    println!("group structures, allowing them to be used with Noether's group traits.");
}