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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154

use crate::{
    errors::CreationError,
    field::{
        element::FieldElement,
        extensions::quadratic::QuadraticExtensionField,
        traits::{IsFFTField, IsField, IsPrimeField},
    },
    field::{errors::FieldError, extensions::quadratic::HasQuadraticNonResidue},
};

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct U64Field<const MODULUS: u64>;

impl<const MODULUS: u64> IsField for U64Field<MODULUS> {
    type BaseType = u64;

    fn add(a: &u64, b: &u64) -> u64 {
        ((*a as u128 + *b as u128) % MODULUS as u128) as u64
    }

    fn sub(a: &u64, b: &u64) -> u64 {
        (((*a as u128 + MODULUS as u128) - *b as u128) % MODULUS as u128) as u64
    }

    fn neg(a: &u64) -> u64 {
        MODULUS - a
    }

    fn mul(a: &u64, b: &u64) -> u64 {
        ((*a as u128 * *b as u128) % MODULUS as u128) as u64
    }

    fn div(a: &u64, b: &u64) -> u64 {
        Self::mul(a, &Self::inv(b).unwrap())
    }

    fn inv(a: &u64) -> Result<u64, FieldError> {
        if *a == 0 {
            return Err(FieldError::InvZeroError);
        }
        Ok(Self::pow(a, MODULUS - 2))
    }

    fn eq(a: &u64, b: &u64) -> bool {
        Self::from_u64(*a) == Self::from_u64(*b)
    }

    fn zero() -> u64 {
        0
    }

    fn one() -> u64 {
        1
    }

    fn from_u64(x: u64) -> u64 {
        x % MODULUS
    }

    fn from_base_type(x: u64) -> u64 {
        Self::from_u64(x)
    }
}

impl<const MODULUS: u64> IsPrimeField for U64Field<MODULUS> {
    type RepresentativeType = u64;

    fn representative(x: &u64) -> u64 {
        *x
    }

    /// Returns how many bits do you need to represent the biggest field element
    /// It expects the MODULUS to be a Prime
    fn field_bit_size() -> usize {
        ((MODULUS - 1).ilog2() + 1) as usize
    }

    fn from_hex(hex_string: &str) -> Result<Self::BaseType, crate::errors::CreationError> {
        let mut hex_string = hex_string;
        // Remove 0x if it's on the string
        let mut char_iterator = hex_string.chars();
        if hex_string.len() > 2
            && char_iterator.next().unwrap() == '0'
            && char_iterator.next().unwrap() == 'x'
        {
            hex_string = &hex_string[2..];
        }

        u64::from_str_radix(hex_string, 16).map_err(|_| CreationError::InvalidHexString)
    }

    #[cfg(feature = "std")]
    fn to_hex(x: &u64) -> String {
        format!("{:X}", x)
    }
}

pub type U64TestField = U64Field<18446744069414584321>;

// These params correspond to the 18446744069414584321 modulus.
impl IsFFTField for U64TestField {
    const TWO_ADICITY: u64 = 32;
    const TWO_ADIC_PRIMITVE_ROOT_OF_UNITY: u64 = 1753635133440165772;
}

#[derive(Clone, Debug)]
pub struct TestNonResidue;
impl HasQuadraticNonResidue<U64TestField> for TestNonResidue {
    fn residue() -> FieldElement<U64TestField> {
        FieldElement::from(7)
    }
}

pub type U64TestFieldExtension = QuadraticExtensionField<U64TestField, TestNonResidue>;

#[cfg(test)]
mod tests_u64_test_field {
    use crate::field::{
        element::FieldElement,
        test_fields::u64_test_field::{U64TestField, U64TestFieldExtension},
        traits::IsPrimeField,
    };

    #[test]
    fn from_hex_for_b_is_11() {
        assert_eq!(U64TestField::from_hex("B").unwrap(), 11);
    }

    #[test]
    fn bit_size_of_test_field_is_64() {
        assert_eq!(
            <U64TestField as crate::field::traits::IsPrimeField>::field_bit_size(),
            64
        );
    }

    #[cfg(feature = "alloc")]
    #[test]
    fn test_to_subfield_vec() {
        let a = FieldElement::<U64TestFieldExtension>::from(&[
            FieldElement::from(1),
            FieldElement::from(3),
        ]);
        let b = a.to_subfield_vec::<U64TestField>();
        assert_eq!(b, alloc::vec![FieldElement::from(1), FieldElement::from(3)]);
    }

    #[cfg(feature = "std")]
    #[test]
    fn to_hex_test() {
        let num = U64TestField::from_hex("B").unwrap();
        assert_eq!(U64TestField::to_hex(&num), "B");
    }
}