decaf377/fields/fq/
arkworks.rs

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

decaf377/fields/fq/
arkworks.rs
