lambdaworks_math/field/fields/
u64_prime_field.rs

1use crate::cyclic_group::IsGroup;
2use crate::errors::ByteConversionError::{FromBEBytesError, FromLEBytesError};
3use crate::errors::CreationError;
4use crate::errors::DeserializationError;
5use crate::field::element::FieldElement;
6use crate::field::errors::FieldError;
7use crate::field::traits::{HasDefaultTranscript, IsFFTField, IsField, IsPrimeField};
8use crate::traits::{ByteConversion, Deserializable};
9
10/// Type representing prime fields over unsigned 64-bit integers.
11#[derive(Debug, Clone, PartialEq, Eq, Hash)]
12pub struct U64PrimeField<const MODULUS: u64>;
13pub type U64FieldElement<const MODULUS: u64> = FieldElement<U64PrimeField<MODULUS>>;
14
15pub type F17 = U64PrimeField<17>;
16pub type FE17 = U64FieldElement<17>;
17
18impl IsFFTField for F17 {
19    const TWO_ADICITY: u64 = 4;
20    const TWO_ADIC_PRIMITVE_ROOT_OF_UNITY: u64 = 3;
21}
22
23impl<const MODULUS: u64> IsField for U64PrimeField<MODULUS> {
24    type BaseType = u64;
25
26    fn add(a: &u64, b: &u64) -> u64 {
27        ((*a as u128 + *b as u128) % MODULUS as u128) as u64
28    }
29
30    fn sub(a: &u64, b: &u64) -> u64 {
31        (((*a as u128 + MODULUS as u128) - *b as u128) % MODULUS as u128) as u64
32    }
33
34    fn neg(a: &u64) -> u64 {
35        MODULUS - a
36    }
37
38    fn mul(a: &u64, b: &u64) -> u64 {
39        ((*a as u128 * *b as u128) % MODULUS as u128) as u64
40    }
41
42    fn div(a: &u64, b: &u64) -> Result<u64, FieldError> {
43        let b_inv = &Self::inv(b)?;
44        Ok(Self::mul(a, b_inv))
45    }
46
47    fn inv(a: &u64) -> Result<u64, FieldError> {
48        if *a == 0 {
49            return Err(FieldError::InvZeroError);
50        }
51        Ok(Self::pow(a, MODULUS - 2))
52    }
53
54    fn eq(a: &u64, b: &u64) -> bool {
55        Self::from_u64(*a) == Self::from_u64(*b)
56    }
57
58    fn zero() -> u64 {
59        0
60    }
61
62    fn one() -> u64 {
63        1
64    }
65
66    fn from_u64(x: u64) -> u64 {
67        x % MODULUS
68    }
69
70    fn from_base_type(x: u64) -> u64 {
71        Self::from_u64(x)
72    }
73}
74
75impl<const MODULUS: u64> Copy for U64FieldElement<MODULUS> {}
76
77impl<const MODULUS: u64> IsPrimeField for U64PrimeField<MODULUS> {
78    type RepresentativeType = u64;
79
80    fn representative(x: &u64) -> u64 {
81        *x
82    }
83
84    /// Returns how many bits do you need to represent the biggest field element
85    /// It expects the MODULUS to be a Prime
86    fn field_bit_size() -> usize {
87        ((MODULUS - 1).ilog2() + 1) as usize
88    }
89
90    fn from_hex(hex_string: &str) -> Result<Self::BaseType, CreationError> {
91        let mut hex_string = hex_string;
92        // Remove 0x if it's on the string
93        let mut char_iterator = hex_string.chars();
94        if hex_string.len() > 2
95            && char_iterator.next().unwrap() == '0'
96            && char_iterator.next().unwrap() == 'x'
97        {
98            hex_string = &hex_string[2..];
99        }
100
101        u64::from_str_radix(hex_string, 16).map_err(|_| CreationError::InvalidHexString)
102    }
103
104    #[cfg(feature = "std")]
105    fn to_hex(x: &u64) -> String {
106        format!("{x:X}")
107    }
108}
109
110/// Represents an element in Fp. (E.g: 0, 1, 2 are the elements of F3)
111impl<const MODULUS: u64> IsGroup for U64FieldElement<MODULUS> {
112    fn neutral_element() -> U64FieldElement<MODULUS> {
113        U64FieldElement::zero()
114    }
115
116    fn operate_with(&self, other: &Self) -> Self {
117        *self + *other
118    }
119
120    fn neg(&self) -> Self {
121        -self
122    }
123}
124
125impl<const MODULUS: u64> ByteConversion for U64FieldElement<MODULUS> {
126    #[cfg(feature = "alloc")]
127    fn to_bytes_be(&self) -> alloc::vec::Vec<u8> {
128        u64::to_be_bytes(*self.value()).into()
129    }
130
131    #[cfg(feature = "alloc")]
132    fn to_bytes_le(&self) -> alloc::vec::Vec<u8> {
133        u64::to_le_bytes(*self.value()).into()
134    }
135
136    fn from_bytes_be(bytes: &[u8]) -> Result<Self, crate::errors::ByteConversionError> {
137        let bytes: [u8; 8] = bytes[0..8].try_into().map_err(|_| FromBEBytesError)?;
138        Ok(Self::from(u64::from_be_bytes(bytes)))
139    }
140
141    fn from_bytes_le(bytes: &[u8]) -> Result<Self, crate::errors::ByteConversionError> {
142        let bytes: [u8; 8] = bytes[0..8].try_into().map_err(|_| FromLEBytesError)?;
143        Ok(Self::from(u64::from_le_bytes(bytes)))
144    }
145}
146
147impl<const MODULUS: u64> Deserializable for FieldElement<U64PrimeField<MODULUS>> {
148    fn deserialize(bytes: &[u8]) -> Result<Self, DeserializationError>
149    where
150        Self: Sized,
151    {
152        Self::from_bytes_be(bytes).map_err(|x| x.into())
153    }
154}
155
156impl<const MODULUS: u64> HasDefaultTranscript for U64PrimeField<MODULUS> {
157    fn get_random_field_element_from_rng(rng: &mut impl rand::Rng) -> FieldElement<Self> {
158        let mask = u64::MAX >> MODULUS.leading_zeros();
159        let mut sample = [0u8; 8];
160        let field;
161        loop {
162            rng.fill(&mut sample);
163            let int_sample = u64::from_be_bytes(sample) & mask;
164            if int_sample < MODULUS {
165                field = FieldElement::from(int_sample);
166                break;
167            }
168        }
169        field
170    }
171}
172
173#[cfg(test)]
174mod tests {
175    use super::*;
176    const MODULUS: u64 = 13;
177    type F = U64PrimeField<MODULUS>;
178    type FE = FieldElement<F>;
179
180    #[test]
181    fn from_hex_for_b_is_11() {
182        assert_eq!(F::from_hex("B").unwrap(), 11);
183    }
184
185    #[test]
186    fn from_hex_for_0x1_a_is_26() {
187        assert_eq!(F::from_hex("0x1a").unwrap(), 26);
188    }
189
190    #[cfg(feature = "std")]
191    #[test]
192    fn to_hex_test_works_1() {
193        let num = F::from_hex("B").unwrap();
194        assert_eq!(F::to_hex(&num), "B");
195    }
196
197    #[cfg(feature = "std")]
198    #[test]
199    fn to_hex_test_works_2() {
200        let num = F::from_hex("0x1a").unwrap();
201        assert_eq!(F::to_hex(&num), "1A");
202    }
203
204    #[test]
205    fn bit_size_of_mod_13_field_is_4() {
206        assert_eq!(
207            <U64PrimeField<MODULUS> as crate::field::traits::IsPrimeField>::field_bit_size(),
208            4
209        );
210    }
211
212    #[test]
213    fn bit_size_of_big_mod_field_is_64() {
214        const MODULUS: u64 = 10000000000000000000;
215        assert_eq!(
216            <U64PrimeField<MODULUS> as crate::field::traits::IsPrimeField>::field_bit_size(),
217            64
218        );
219    }
220
221    #[test]
222    fn bit_size_of_63_bit_mod_field_is_63() {
223        const MODULUS: u64 = 9000000000000000000;
224        assert_eq!(
225            <U64PrimeField<MODULUS> as crate::field::traits::IsPrimeField>::field_bit_size(),
226            63
227        );
228    }
229
230    #[test]
231    fn two_plus_one_is_three() {
232        assert_eq!(FE::new(2) + FE::new(1), FE::new(3));
233    }
234
235    #[test]
236    fn max_order_plus_1_is_0() {
237        assert_eq!(FE::new(MODULUS - 1) + FE::new(1), FE::new(0));
238    }
239
240    #[test]
241    fn when_comparing_13_and_13_they_are_equal() {
242        let a: FE = FE::new(13);
243        let b: FE = FE::new(13);
244        assert_eq!(a, b);
245    }
246
247    #[test]
248    fn when_comparing_13_and_8_they_are_different() {
249        let a: FE = FE::new(13);
250        let b: FE = FE::new(8);
251        assert_ne!(a, b);
252    }
253
254    #[test]
255    fn mul_neutral_element() {
256        let a: FE = FE::new(1);
257        let b: FE = FE::new(2);
258        assert_eq!(a * b, FE::new(2));
259    }
260
261    #[test]
262    fn mul_2_3_is_6() {
263        let a: FE = FE::new(2);
264        let b: FE = FE::new(3);
265        assert_eq!(a * b, FE::new(6));
266    }
267
268    #[test]
269    fn mul_order_minus_1() {
270        let a: FE = FE::new(MODULUS - 1);
271        let b: FE = FE::new(MODULUS - 1);
272        assert_eq!(a * b, FE::new(1));
273    }
274
275    #[test]
276    fn inv_0_error() {
277        let result = FE::new(0).inv();
278        assert!(matches!(result, Err(FieldError::InvZeroError)));
279    }
280
281    #[test]
282    fn inv_2() {
283        let a: FE = FE::new(2);
284        assert_eq!(a * a.inv().unwrap(), FE::new(1));
285    }
286
287    #[test]
288    fn pow_2_3() {
289        assert_eq!(FE::new(2).pow(3_u64), FE::new(8))
290    }
291
292    #[test]
293    fn pow_p_minus_1() {
294        assert_eq!(FE::new(2).pow(MODULUS - 1), FE::new(1))
295    }
296
297    #[test]
298    fn div_1() {
299        assert_eq!(FE::new(2) * FE::new(1).inv().unwrap(), FE::new(2))
300    }
301
302    #[test]
303    fn div_4_2() {
304        assert_eq!(FE::new(4) * FE::new(2).inv().unwrap(), FE::new(2))
305    }
306
307    #[test]
308    fn div_4_3() {
309        assert_eq!(
310            FE::new(4) * FE::new(3).inv().unwrap() * FE::new(3),
311            FE::new(4)
312        )
313    }
314
315    #[test]
316    fn two_plus_its_additive_inv_is_0() {
317        let two = FE::new(2);
318
319        assert_eq!(two + (-two), FE::new(0))
320    }
321
322    #[test]
323    fn four_minus_three_is_1() {
324        let four = FE::new(4);
325        let three = FE::new(3);
326
327        assert_eq!(four - three, FE::new(1))
328    }
329
330    #[test]
331    fn zero_minus_1_is_order_minus_1() {
332        let zero = FE::new(0);
333        let one = FE::new(1);
334
335        assert_eq!(zero - one, FE::new(MODULUS - 1))
336    }
337
338    #[test]
339    fn neg_zero_is_zero() {
340        let zero = FE::new(0);
341
342        assert_eq!(-zero, zero);
343    }
344
345    #[test]
346    fn zero_constructor_returns_zero() {
347        assert_eq!(FE::new(0), FE::new(0));
348    }
349
350    #[test]
351    fn field_element_as_group_element_multiplication_by_scalar_works_as_multiplication_in_finite_fields(
352    ) {
353        let a = FE::new(3);
354        let b = FE::new(12);
355        assert_eq!(a * b, a.operate_with_self(12_u16));
356    }
357
358    #[test]
359    #[cfg(feature = "alloc")]
360    fn to_bytes_from_bytes_be_is_the_identity() {
361        let x = FE::new(12345);
362        assert_eq!(FE::from_bytes_be(&x.to_bytes_be()).unwrap(), x);
363    }
364
365    #[test]
366    #[cfg(feature = "alloc")]
367    fn from_bytes_to_bytes_be_is_the_identity_for_one() {
368        let bytes = [0, 0, 0, 0, 0, 0, 0, 1];
369        assert_eq!(FE::from_bytes_be(&bytes).unwrap().to_bytes_be(), bytes);
370    }
371
372    #[test]
373    #[cfg(feature = "alloc")]
374    fn to_bytes_from_bytes_le_is_the_identity() {
375        let x = FE::new(12345);
376        assert_eq!(FE::from_bytes_le(&x.to_bytes_le()).unwrap(), x);
377    }
378
379    #[test]
380    #[cfg(feature = "alloc")]
381    fn from_bytes_to_bytes_le_is_the_identity_for_one() {
382        let bytes = [1, 0, 0, 0, 0, 0, 0, 0];
383        assert_eq!(FE::from_bytes_le(&bytes).unwrap().to_bytes_le(), bytes);
384    }
385
386    #[test]
387    fn creating_a_field_element_from_its_representative_returns_the_same_element_1() {
388        let change = 1;
389        let f1 = FE::new(MODULUS + change);
390        let f2 = FE::new(f1.representative());
391        assert_eq!(f1, f2);
392    }
393
394    #[test]
395    fn creating_a_field_element_from_its_representative_returns_the_same_element_2() {
396        let change = 8;
397        let f1 = FE::new(MODULUS + change);
398        let f2 = FE::new(f1.representative());
399        assert_eq!(f1, f2);
400    }
401}
lambdaworks_math/field/fields/u64_prime_field.rs

lambdaworks_math/field/fields/
u64_prime_field.rs
