decaf377/fields/fp/
arkworks.rs

1use super::Fp;
2use ark_ff::{BigInt, Field, PrimeField, SqrtPrecomputation};
3use ark_ff::{BigInteger, FftField};
4use ark_serialize::{
5    CanonicalDeserialize, CanonicalDeserializeWithFlags, CanonicalSerialize,
6    CanonicalSerializeWithFlags, Compress, EmptyFlags, Flags, SerializationError, Valid, Validate,
7};
8use ark_std::{rand, str::FromStr, string::ToString, One, Zero};
9use core::convert::TryInto;
10use core::{
11    fmt::{Display, Formatter},
12    iter,
13};
14
15impl PrimeField for Fp {
16    /// A `BigInteger` type that can represent elements of this field.
17    type BigInt = BigInt<6>;
18
19    /// The BLS12-377 base field modulus `p` = 0x1ae3a4617c510eac63b05c06ca1493b1a22d9f300f5138f1ef3622fba094800170b5d44300000008508c0000000000
20    const MODULUS: Self::BigInt = ark_ff::BigInt(Self::MODULUS_LIMBS);
21
22    /// The value `(p - 1)/ 2`.
23    const MODULUS_MINUS_ONE_DIV_TWO: Self::BigInt = BigInt(Self::MODULUS_MINUS_ONE_DIV_TWO_LIMBS);
24
25    /// The size of the modulus in bits.
26    const MODULUS_BIT_SIZE: u32 = Self::MODULUS_BIT_SIZE;
27
28    /// The trace of the field is defined as the smallest integer `t` such that by
29    /// `2^s * t = p - 1`, and `t` is coprime to 2.
30    const TRACE: Self::BigInt = BigInt(Self::TRACE_LIMBS);
31
32    /// The value `(t - 1)/ 2`.
33    const TRACE_MINUS_ONE_DIV_TWO: Self::BigInt = BigInt(Self::TRACE_MINUS_ONE_DIV_TWO_LIMBS);
34
35    fn from_bigint(repr: Self::BigInt) -> Option<Self> {
36        if repr >= Fp::MODULUS {
37            None
38        } else {
39            // Assuming BigInt is little endian
40            Some(Self::from_le_limbs(repr.0))
41        }
42    }
43
44    fn into_bigint(self) -> Self::BigInt {
45        BigInt(self.to_le_limbs())
46    }
47
48    fn from_be_bytes_mod_order(bytes: &[u8]) -> Self {
49        let mut bytes_copy = bytes.to_vec();
50        bytes_copy.reverse();
51        Self::from_le_bytes_mod_order(&bytes_copy)
52    }
53
54    fn from_le_bytes_mod_order(bytes: &[u8]) -> Self {
55        Self::from_le_bytes_mod_order(bytes)
56    }
57}
58
59impl Field for Fp {
60    type BasePrimeField = Self;
61    type BasePrimeFieldIter = iter::Once<Self::BasePrimeField>;
62
63    const SQRT_PRECOMP: Option<SqrtPrecomputation<Self>> =
64        Some(SqrtPrecomputation::TonelliShanks {
65            two_adicity: Self::TWO_ADICITY,
66            quadratic_nonresidue_to_trace: Self::QUADRATIC_NON_RESIDUE_TO_TRACE,
67            trace_of_modulus_minus_one_div_two: &Self::TRACE_MINUS_ONE_DIV_TWO_LIMBS,
68        });
69
70    const ZERO: Self = Self::ZERO;
71
72    // Montomgery representation of one
73    const ONE: Self = Self::ONE;
74
75    fn extension_degree() -> u64 {
76        1
77    }
78
79    fn to_base_prime_field_elements(&self) -> Self::BasePrimeFieldIter {
80        iter::once(*self)
81    }
82
83    fn from_base_prime_field_elems(elems: &[Self::BasePrimeField]) -> Option<Self> {
84        if elems.len() != (Self::extension_degree() as usize) {
85            return None;
86        }
87        Some(elems[0])
88    }
89
90    fn from_base_prime_field(elem: Self::BasePrimeField) -> Self {
91        elem
92    }
93
94    fn double(&self) -> Self {
95        self.add(self)
96    }
97
98    fn double_in_place(&mut self) -> &mut Self {
99        *self = self.add(self);
100        self
101    }
102
103    fn neg_in_place(&mut self) -> &mut Self {
104        *self = Self::ZERO.sub(self);
105        self
106    }
107
108    fn from_random_bytes_with_flags<F: ark_serialize::Flags>(bytes: &[u8]) -> Option<(Self, F)> {
109        Some((Self::from_le_bytes_mod_order(bytes), F::default()))
110    }
111
112    fn legendre(&self) -> ark_ff::LegendreSymbol {
113        use ark_ff::LegendreSymbol::*;
114
115        if self.is_zero() {
116            return Zero;
117        }
118        if self.pow(&Self::MODULUS_MINUS_ONE_DIV_TWO.0).is_one() {
119            return QuadraticResidue;
120        }
121        return QuadraticNonResidue;
122    }
123
124    fn square(&self) -> Self {
125        self.square()
126    }
127
128    fn square_in_place(&mut self) -> &mut Self {
129        *self = self.square();
130        self
131    }
132
133    fn inverse(&self) -> Option<Self> {
134        self.inverse()
135    }
136
137    fn inverse_in_place(&mut self) -> Option<&mut Self> {
138        if let Some(inverse) = self.inverse() {
139            *self = inverse;
140            Some(self)
141        } else {
142            None
143        }
144    }
145
146    fn frobenius_map_in_place(&mut self, _power: usize) {
147        // Because this is a prime field, we don't need to do anything,
148        // the automorphism is trivial.
149    }
150
151    fn characteristic() -> &'static [u64] {
152        &Self::MODULUS_LIMBS
153    }
154}
155
156impl FftField for Fp {
157    const GENERATOR: Self = Self::MULTIPLICATIVE_GENERATOR;
158    const TWO_ADICITY: u32 = Self::TWO_ADICITY;
159    const TWO_ADIC_ROOT_OF_UNITY: Self = Self::TWO_ADIC_ROOT_OF_UNITY;
160    const SMALL_SUBGROUP_BASE: Option<u32> = None;
161    const SMALL_SUBGROUP_BASE_ADICITY: Option<u32> = None;
162    const LARGE_SUBGROUP_ROOT_OF_UNITY: Option<Self> = None;
163}
164
165impl Zero for Fp {
166    #[inline]
167    fn zero() -> Self {
168        Fp::ZERO
169    }
170
171    #[inline]
172    fn is_zero(&self) -> bool {
173        *self == Fp::ZERO
174    }
175}
176
177impl One for Fp {
178    #[inline]
179    fn one() -> Self {
180        Fp::ONE
181    }
182
183    #[inline]
184    fn is_one(&self) -> bool {
185        *self == Fp::ONE
186    }
187}
188
189impl CanonicalDeserializeWithFlags for Fp {
190    fn deserialize_with_flags<R: ark_std::io::Read, F: Flags>(
191        mut reader: R,
192    ) -> Result<(Self, F), SerializationError> {
193        // Enough for the field element + 8 bits of flags. The last byte may or may not contain flags.
194        let mut bytes = [0u8; (Self::MODULUS_BIT_SIZE as usize + 7) / 8];
195        let expected_len = (Self::MODULUS_BIT_SIZE as usize + F::BIT_SIZE + 7) / 8;
196        reader.read_exact(&mut bytes[..expected_len])?;
197        let flags = F::from_u8_remove_flags(&mut bytes[bytes.len() - 1])
198            .ok_or(SerializationError::UnexpectedFlags)?;
199        // Then, convert the bytes to limbs, to benefit from the canonical check we have for
200        // bigint.
201        let mut limbs = [0u64; 6];
202        for (limb, chunk) in limbs.iter_mut().zip(bytes[..48].chunks_exact(8)) {
203            *limb = u64::from_le_bytes(chunk.try_into().expect("chunk will have the right size"));
204        }
205        let out = Self::from_bigint(BigInt(limbs)).ok_or(SerializationError::InvalidData)?;
206        Ok((out, flags))
207    }
208}
209
210impl Valid for Fp {
211    fn check(&self) -> Result<(), SerializationError> {
212        Ok(())
213    }
214}
215
216impl CanonicalDeserialize for Fp {
217    fn deserialize_with_mode<R: ark_std::io::Read>(
218        reader: R,
219        _compress: Compress,
220        validate: Validate,
221    ) -> Result<Self, SerializationError> {
222        let (out, _) = Self::deserialize_with_flags::<R, EmptyFlags>(reader)?;
223        match validate {
224            Validate::Yes => out.check(),
225            Validate::No => Ok(()),
226        }?;
227        Ok(out)
228    }
229}
230
231impl CanonicalSerialize for Fp {
232    #[inline]
233    fn serialize_with_mode<W: ark_std::io::Write>(
234        &self,
235        writer: W,
236        _compress: Compress,
237    ) -> Result<(), SerializationError> {
238        self.serialize_with_flags(writer, EmptyFlags)
239    }
240
241    #[inline]
242    fn serialized_size(&self, _compress: Compress) -> usize {
243        self.serialized_size_with_flags::<EmptyFlags>()
244    }
245}
246
247impl CanonicalSerializeWithFlags for Fp {
248    fn serialize_with_flags<W: ark_std::io::Write, F: Flags>(
249        &self,
250        mut writer: W,
251        flags: F,
252    ) -> Result<(), SerializationError> {
253        // Arkworks imposes this constraint
254        if F::BIT_SIZE > 8 {
255            return Err(SerializationError::NotEnoughSpace);
256        }
257
258        // We can't just write the bytes out, because the last byte might be masked by flags.
259        let mut bytes = self.to_bytes_le();
260        // Either the flags fit into the last byte...
261        if bytes.len() == self.serialized_size_with_flags::<F>() {
262            // In which case we have to mask the last byte
263            bytes[bytes.len() - 1] |= flags.u8_bitmask();
264            writer.write_all(&bytes)?;
265        } else {
266            // Or else we create a new byte
267            writer.write_all(&bytes)?;
268            writer.write_all(&[flags.u8_bitmask()])?;
269        }
270        Ok(())
271    }
272
273    fn serialized_size_with_flags<F: Flags>(&self) -> usize {
274        (Self::MODULUS_BIT_SIZE as usize + F::BIT_SIZE + 7) / 8
275    }
276}
277
278impl ark_std::rand::distributions::Distribution<Fp> for ark_std::rand::distributions::Standard {
279    fn sample<R: rand::prelude::Rng + ?Sized>(&self, rng: &mut R) -> Fp {
280        loop {
281            let mut repr: [u64; 6] = rng.sample(ark_std::rand::distributions::Standard);
282            let shave_bits = 64 * 6 - (Fp::MODULUS_BIT_SIZE as usize);
283            // Mask away the unused bits at the beginning.
284            let mask = if shave_bits == 64 {
285                0
286            } else {
287                u64::MAX >> shave_bits
288            };
289
290            if let Some(val) = repr.last_mut() {
291                *val &= mask
292            }
293
294            if let Some(small_enough) = Fp::from_bigint(BigInt(repr)) {
295                return small_enough;
296            }
297        }
298    }
299}
300
301impl FromStr for Fp {
302    type Err = ();
303
304    fn from_str(s: &str) -> Result<Self, Self::Err> {
305        // CANDO: a more efficient method accumulating into 64 bits first.
306        let mut acc = Self::zero();
307
308        let ten = Self::from(10u8);
309
310        for c in s.chars() {
311            match c.to_digit(10) {
312                Some(c) => {
313                    acc = ten * acc + Self::from(u64::from(c));
314                }
315                None => {
316                    return Err(());
317                }
318            }
319        }
320        Ok(acc)
321    }
322}
323
324impl From<num_bigint::BigUint> for Fp {
325    #[inline]
326    fn from(val: num_bigint::BigUint) -> Fp {
327        Fp::from_le_bytes_mod_order(&val.to_bytes_le())
328    }
329}
330
331impl From<Fp> for num_bigint::BigUint {
332    #[inline(always)]
333    fn from(other: Fp) -> Self {
334        other.into_bigint().into()
335    }
336}
337
338impl From<Fp> for BigInt<6> {
339    #[inline(always)]
340    fn from(fp: Fp) -> Self {
341        fp.into_bigint()
342    }
343}
344
345impl From<BigInt<6>> for Fp {
346    /// Converts `Self::BigInteger` into `Self`
347    #[inline(always)]
348    fn from(int: BigInt<6>) -> Self {
349        Fp::from_le_bytes_mod_order(&int.to_bytes_le())
350    }
351}
352
353impl Display for Fp {
354    fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
355        let string = self.into_bigint().to_string();
356        write!(f, "{}", string.trim_start_matches('0'))
357    }
358}
359
360#[cfg(test)]
361mod tests {
362    use super::*;
363    extern crate alloc;
364    use alloc::{format, vec::Vec};
365    use ark_bls12_377::Fq as ArkFp;
366    use proptest::prelude::*;
367
368    prop_compose! {
369        // Technically this might overflow, but we won't miss any values,
370        // just return 0 if you overflow when consuming.
371        fn arb_fp_limbs()(
372            z0 in 0..u64::MAX,
373            z1 in 0..u64::MAX,
374            z2 in 0..u64::MAX,
375            z3 in 0..u64::MAX,
376            z4 in 0..u64::MAX,
377            z5 in 0..0x1ae3a4617c510eu64
378        ) -> [u64; 6] {
379            [z0, z1, z2, z3, z4, z5]
380        }
381    }
382
383    prop_compose! {
384        fn arb_fp()(a in arb_fp_limbs()) -> Fp {
385            // Will be fine because of the bounds in the arb_fp_limbs
386            Fp::from_bigint(BigInt(a)).unwrap_or(Fp::ZERO)
387        }
388    }
389
390    prop_compose! {
391        fn arb_nonzero_fp()(a in arb_fp()) -> Fp {
392            if a == Fp::ZERO { Fp::ONE } else { a }
393        }
394    }
395
396    proptest! {
397        #[test]
398        fn test_addition_commutative(a in arb_fp(), b in arb_fp()) {
399            assert_eq!(a + b, b + a);
400        }
401    }
402
403    proptest! {
404        #[test]
405        fn test_addition_associative(a in arb_fp(), b in arb_fp(), c in arb_fp()) {
406            assert_eq!(a + (b + c), (a + b) + c);
407        }
408    }
409
410    proptest! {
411        #[test]
412        fn test_add_zero_identity(a in arb_fp()) {
413            let zero = Fp::ZERO;
414
415            assert_eq!(a + zero, a);
416            assert_eq!(zero + a, a);
417        }
418    }
419
420    proptest! {
421        #[test]
422        fn test_subtract_self_is_zero(a in arb_fp()) {
423            let zero = Fp::ZERO;
424
425            assert_eq!(a - a, zero);
426        }
427    }
428
429    proptest! {
430        #[test]
431        fn test_doubling_is_just_addition(a in arb_fp()) {
432            let two = Fp::from(2u64);
433
434            assert_eq!(two * a, a + a);
435            assert_eq!(a.double(), a + a);
436            assert_eq!(*(a.clone().double_in_place()), a + a);
437        }
438    }
439
440    proptest! {
441        #[test]
442        fn test_adding_negation(a in arb_fp()) {
443            assert_eq!(a + -a, Fp::ZERO)
444        }
445    }
446
447    proptest! {
448        #[test]
449        fn test_multiplication_commutative(a in arb_fp(), b in arb_fp()) {
450            assert_eq!(a * b, b * a);
451        }
452    }
453
454    proptest! {
455        #[test]
456        fn test_multiplication_associative(a in arb_fp(), b in arb_fp(), c in arb_fp()) {
457            assert_eq!(a * (b * c), (a * b) * c);
458        }
459    }
460
461    proptest! {
462        #[test]
463        fn test_multiplication_distributive(a in arb_fp(), b in arb_fp(), c in arb_fp()) {
464            assert_eq!(a * (b + c), a * b + a * c);
465        }
466    }
467
468    proptest! {
469        #[test]
470        fn test_multiply_one_identity(a in arb_fp()) {
471            assert_eq!(a * Fp::ONE, a);
472            assert_eq!(Fp::ONE * a, a);
473        }
474    }
475
476    proptest! {
477        #[test]
478        fn test_multiply_minus_one_is_negation(a in arb_fp()) {
479            let minus_one = -Fp::ONE;
480
481            assert_eq!(a * minus_one, a.neg());
482        }
483    }
484
485    proptest! {
486        #[test]
487        fn test_square_is_multiply(a in arb_fp()) {
488            assert_eq!(a.square(), a * a);
489            assert_eq!(*(a.clone().square_in_place()), a * a);
490        }
491    }
492
493    proptest! {
494        #[test]
495        fn test_inverse(a in arb_nonzero_fp()) {
496            assert_eq!(a * a.inverse().unwrap(), Fp::ONE);
497            assert_eq!(a * *(a.clone().inverse_in_place().unwrap()), Fp::ONE);
498        }
499    }
500
501    fn naive_inverse(a: Fp) -> Fp {
502        a.pow(&(-Fp::from(2u64)).into_bigint().0)
503    }
504
505    proptest! {
506        #[test]
507        fn test_inverse_vs_naive_inverse(a in arb_nonzero_fp()) {
508            assert_eq!(a.inverse().unwrap(), naive_inverse(a));
509        }
510    }
511
512    proptest! {
513        #[test]
514        fn test_sqrt(a in arb_fp()) {
515            match a.sqrt() {
516                Some(x) => assert_eq!(x * x, a),
517                None => {}
518            }
519        }
520    }
521
522    proptest! {
523        #[test]
524        fn test_into_bigint_monomorphism(a in arb_fp()) {
525            let as_bigint = a.into_bigint();
526            let roundtrip = Fp::from_bigint(as_bigint);
527
528            assert_eq!(Some(a), roundtrip);
529        }
530    }
531
532    proptest! {
533        #[test]
534        fn test_conversion_to_bytes_via_bigint(a in arb_fp()) {
535            let way1 = a.to_bytes_le();
536            let way2 = a.into_bigint().to_bytes_le();
537            assert_eq!(way1.as_slice(), way2.as_slice());
538        }
539    }
540
541    proptest! {
542        #[test]
543        fn test_legendre_symbol(a in arb_nonzero_fp()) {
544            assert_eq!((a * a).legendre(), ark_ff::LegendreSymbol::QuadraticResidue);
545        }
546    }
547
548    proptest! {
549        #[test]
550        fn test_canonical_serialize_monomorphism(a in arb_fp()) {
551            let mut bytes: Vec<u8> = Vec::new();
552            let roundtrip = a.serialize_compressed(&mut bytes).and_then(|_| Fp::deserialize_compressed(&*bytes));
553            assert!(roundtrip.is_ok());
554            assert_eq!(*roundtrip.as_ref().clone().unwrap(), a);
555        }
556    }
557
558    proptest! {
559        #[test]
560        fn test_serialize_matches_arkworks(a in arb_fp_limbs()) {
561            let our_value: Fp = BigInt(a).into();
562            let their_value: ArkFp = BigInt(a).into();
563
564            let mut our_bytes: Vec<u8> = Vec::new();
565            assert!(our_value.serialize_compressed(&mut our_bytes).is_ok());
566
567            let mut their_bytes: Vec<u8> = Vec::new();
568            assert!(their_value.serialize_compressed(&mut their_bytes).is_ok());
569
570            assert_eq!(our_bytes, their_bytes);
571        }
572    }
573
574    fn naive_from_le_bytes_mod_order(bytes: &[u8]) -> Fp {
575        let mut acc = Fp::zero();
576        let mut insert = Fp::one();
577        for byte in bytes {
578            for i in 0..8 {
579                if (byte >> i) & 1 == 1 {
580                    acc += insert;
581                }
582                insert.double_in_place();
583            }
584        }
585        acc
586    }
587
588    proptest! {
589        #[test]
590        fn test_from_le_bytes_mod_order_vs_naive(bytes in any::<[u8; 128]>()) {
591            let way1 = Fp::from_le_bytes_mod_order(&bytes);
592            let way2 = naive_from_le_bytes_mod_order(&bytes);
593            assert_eq!(way1, way2);
594        }
595    }
596
597    proptest! {
598        #[test]
599        fn test_from_str(a in arb_fp()) {
600            let x = <Fp as PrimeField>::BigInt::from(a);
601            assert_eq!(Ok(a), Fp::from_str(&format!("{}", x)));
602        }
603    }
604
605    #[test]
606    fn test_from_le_bytes_mod_order_examples() {
607        let p_plus_1_bytes: [u8; 48] = [
608            2, 0, 0, 0, 0, 192, 8, 133, 0, 0, 0, 48, 68, 93, 11, 23, 0, 72, 9, 186, 47, 98, 243,
609            30, 143, 19, 245, 0, 243, 217, 34, 26, 59, 73, 161, 108, 192, 5, 59, 198, 234, 16, 197,
610            23, 70, 58, 174, 1,
611        ];
612        let bytes_for_1 = {
613            let mut out = [0u8; 48];
614            out[0] = 1;
615            out
616        };
617
618        assert_eq!(Fp::from_le_bytes_mod_order(&p_plus_1_bytes), Fp::one());
619        assert_eq!(
620            Fp::from_le_bytes_mod_order(&p_plus_1_bytes).to_bytes_le(),
621            bytes_for_1
622        );
623    }
624
625    #[test]
626    fn test_addition_examples() {
627        let z1: Fp = BigInt([1, 1, 1, 1, 1, 1]).into();
628        let z2: Fp = BigInt([2, 2, 2, 2, 2, 2]).into();
629        let z3: Fp = BigInt([3, 3, 3, 3, 3, 3]).into();
630
631        assert_eq!(z3, z1 + z2);
632    }
633
634    #[test]
635    fn test_subtraction_examples() {
636        let mut z1: Fp = BigInt([1, 1, 1, 1, 1, 1]).into();
637        z1 -= z1;
638
639        assert_eq!(z1, Fp::ZERO);
640    }
641
642    #[test]
643    fn test_small_multiplication_examples() {
644        let z1: Fp = BigInt([1, 0, 0, 0, 0, 0]).into();
645        let z2: Fp = BigInt([2, 0, 0, 0, 0, 0]).into();
646        let z3: Fp = BigInt([3, 0, 0, 0, 0, 0]).into();
647
648        assert_eq!(z1 + z1, z1 * z2);
649        assert_eq!(z1 + z1 + z1, z1 * z3);
650    }
651
652    #[test]
653    fn test_2192_times_zero() {
654        let two192: Fp = BigInt([0, 0, 0, 0, 0, 1]).into();
655        assert_eq!(two192 * Fp::zero(), Fp::ZERO);
656    }
657
658    #[test]
659    fn test_minus_one_squared() {
660        let minus_one = Fp::zero() - Fp::one();
661        assert_eq!(minus_one.square(), Fp::ONE);
662    }
663
664    #[test]
665    fn test_modulus_from_le_bytes_mod_order() {
666        // Field modulus - 1 in non-montgomery form that satisfies the fiat-crypto preconditions (< m)
667        let modulus_minus_one: Fp = BigInt([
668            9586122913090633728,
669            1660523435060625408,
670            2230234197602682880,
671            1883307231910630287,
672            14284016967150029115,
673            121098312706494698,
674        ])
675        .into();
676
677        assert_eq!(modulus_minus_one, -Fp::one());
678    }
679}
decaf377/fields/fp/arkworks.rs

decaf377/fields/fp/
arkworks.rs
