1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

pub mod montgomery;
pub mod primefield;

use core::ops::Mul;

use crate::ring::Ring;

/// This is a trait for field, a field is constructed from
/// 
/// 1. A Abelian Group over add
/// 2. A ring over multiplication and addition
/// 3. Multiplication should be communicative
/// 4. There must exists multiplicative inverse
/// 5. There must exists multiplicative identity (**and different from additive identity**)
/// 
/// TODO: find a way to constraint a field has different multiplicative identity
/// and addition identity via type system.
pub trait Field: Ring + CommunicativeMul + MulIdentity + MulInverse { 
    /// calculate self / 2 in field
    /// 
    /// ```text
    /// if self.is_even 
    ///     return self >> 1
    /// else 
    ///     return (self + P) >> 1
    /// ```
    fn hlv(self) -> Self;

    /// check if self is zero
    fn is_zero(&self) -> bool;
}

/// # Safety
/// 
/// This trait is safe to implement only when the underlying type is guaranteed to
/// give the same result for any a * b and b * a
pub trait CommunicativeMul: Sized + Mul<Output = Self> { }

/// # Safety
/// 
/// This trait is safe only when for any a, a * MUL_IDENTITY = MUL_IDENTITY * a = a
pub trait MulIdentity: Sized + Mul<Output = Self> {
    const MUL_IDENTITY: Self;
    const ONE: Self = Self::MUL_IDENTITY;
}

pub trait MulInverse: MulIdentity {
    fn mul_inv(self) -> Self;
}