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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

// This trait resresents prime field

use core::{
    fmt::Debug,
    ops::{Add, AddAssign, BitAnd, BitXor, Mul, MulAssign, Sub, SubAssign},
};

use super::{
    algebra::Field,
    comp::{Basic, ParityCmp},
};
use crate::arithmetic::utils::{Bits, Nafs};

// TODO: should be right place
pub trait RefOps:
    for<'a> Add<&'a Self, Output = Self>
    + for<'b> Add<&'b Self, Output = Self>
    + for<'a, 'b> Add<&'b Self, Output = Self>
    + for<'a> AddAssign<&'a Self>
    + for<'b> AddAssign<&'b Self>
    + for<'a, 'b> AddAssign<&'b Self>
    + for<'a> Sub<&'a Self, Output = Self>
    + for<'b> Sub<&'b Self, Output = Self>
    + for<'a, 'b> Sub<&'b Self, Output = Self>
    + for<'a> SubAssign<&'a Self>
    + for<'b> SubAssign<&'b Self>
    + for<'a, 'b> SubAssign<&'b Self>
    + for<'a> Mul<&'a Self, Output = Self>
    + for<'b> Mul<&'b Self, Output = Self>
    + for<'a, 'b> Mul<&'b Self, Output = Self>
    + for<'a> MulAssign<&'a Self>
    + for<'b> MulAssign<&'b Self>
    + for<'a, 'b> MulAssign<&'b Self>
{
}

/// This is prime field trait
pub trait PrimeField: Field + Basic + ParityCmp + From<u64> + RefOps {
    // prime order of this field
    const MODULUS: Self;

    // mongomery reduction inverse
    const INV: u64;

    fn is_zero(self) -> bool;

    fn to_bits(self) -> Bits;

    fn to_nafs(self) -> Nafs;

    fn double(self) -> Self;

    fn square(self) -> Self;

    fn double_assign(&mut self);

    fn square_assign(&mut self);
}

pub trait FieldRepr: Debug + BitAnd + BitXor + Sized {
    const LIMBS_LENGTH: usize;

    // map from montgomery to normal form
    fn montgomery_reduce(self) -> Self;
}