nam_blstrs/
fp2.rs

1//! This module implements arithmetic over the quadratic extension field Fp2.
2
3use blst::*;
4
5use core::{
6    cmp::{Ord, Ordering, PartialOrd},
7    fmt,
8    ops::{Add, AddAssign, Mul, MulAssign, Neg, Sub, SubAssign},
9};
10use ff::Field;
11use rand_core::RngCore;
12use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
13use zeroize::Zeroize;
14
15use crate::fp::{FROBENIUS_COEFF_FP2_C1, Fp};
16
17#[derive(Copy, Clone, Zeroize)]
18#[cfg_attr(feature = "arbitrary", derive(arbitrary::Arbitrary))]
19#[repr(transparent)]
20pub struct Fp2(pub(crate) blst_fp2);
21
22impl fmt::Debug for Fp2 {
23    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
24        f.debug_struct("Fp2")
25            .field("c0", &self.c0())
26            .field("c1", &self.c1())
27            .finish()
28    }
29}
30
31impl fmt::Display for Fp2 {
32    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
33        write!(f, "Fq2({:?} + {:?} * u)", self.c0(), self.c1())
34    }
35}
36
37impl From<Fp> for Fp2 {
38    fn from(f: Fp) -> Fp2 {
39        Fp2::new(f, Fp::ZERO)
40    }
41}
42
43impl From<blst_fp2> for Fp2 {
44    fn from(val: blst_fp2) -> Fp2 {
45        Fp2(val)
46    }
47}
48
49impl From<Fp2> for blst_fp2 {
50    fn from(val: Fp2) -> blst_fp2 {
51        val.0
52    }
53}
54
55impl From<u64> for Fp2 {
56    fn from(val: u64) -> Fp2 {
57        Fp2::new(Fp::from(val), Fp::ZERO)
58    }
59}
60
61impl Default for Fp2 {
62    fn default() -> Self {
63        Fp2::ZERO
64    }
65}
66
67/// `Fq2` elements are ordered lexicographically.
68impl Ord for Fp2 {
69    #[inline(always)]
70    fn cmp(&self, other: &Fp2) -> Ordering {
71        match self.c1().cmp(&other.c1()) {
72            Ordering::Greater => Ordering::Greater,
73            Ordering::Less => Ordering::Less,
74            Ordering::Equal => self.c0().cmp(&other.c0()),
75        }
76    }
77}
78
79impl PartialOrd for Fp2 {
80    #[inline(always)]
81    fn partial_cmp(&self, other: &Fp2) -> Option<Ordering> {
82        Some(self.cmp(other))
83    }
84}
85
86impl Eq for Fp2 {}
87
88impl PartialEq for Fp2 {
89    #[inline]
90    fn eq(&self, other: &Self) -> bool {
91        self.0.fp == other.0.fp
92    }
93}
94
95impl ConstantTimeEq for Fp2 {
96    fn ct_eq(&self, other: &Self) -> Choice {
97        self.c0().ct_eq(&other.c0()) & self.c1().ct_eq(&other.c1())
98    }
99}
100
101impl ConditionallySelectable for Fp2 {
102    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
103        Fp2(blst_fp2 {
104            fp: [
105                Fp::conditional_select(&a.c0(), &b.c0(), choice).0,
106                Fp::conditional_select(&a.c1(), &b.c1(), choice).0,
107            ],
108        })
109    }
110}
111
112impl Neg for &Fp2 {
113    type Output = Fp2;
114
115    #[inline]
116    fn neg(self) -> Fp2 {
117        -*self
118    }
119}
120
121impl Neg for Fp2 {
122    type Output = Fp2;
123
124    #[inline]
125    fn neg(mut self) -> Fp2 {
126        unsafe { blst_fp2_cneg(&mut self.0, &self.0, true) };
127        self
128    }
129}
130
131impl Add<&Fp2> for &Fp2 {
132    type Output = Fp2;
133
134    #[inline]
135    fn add(self, rhs: &Fp2) -> Fp2 {
136        let mut out = *self;
137        out += rhs;
138        out
139    }
140}
141
142impl Sub<&Fp2> for &Fp2 {
143    type Output = Fp2;
144
145    #[inline]
146    fn sub(self, rhs: &Fp2) -> Fp2 {
147        let mut out = *self;
148        out -= rhs;
149        out
150    }
151}
152
153impl Mul<&Fp2> for &Fp2 {
154    type Output = Fp2;
155
156    #[inline]
157    fn mul(self, rhs: &Fp2) -> Fp2 {
158        let mut out = *self;
159        out *= rhs;
160        out
161    }
162}
163
164impl AddAssign<&Fp2> for Fp2 {
165    #[inline]
166    fn add_assign(&mut self, rhs: &Fp2) {
167        unsafe { blst_fp2_add(&mut self.0, &self.0, &rhs.0) };
168    }
169}
170
171impl SubAssign<&Fp2> for Fp2 {
172    #[inline]
173    fn sub_assign(&mut self, rhs: &Fp2) {
174        unsafe { blst_fp2_sub(&mut self.0, &self.0, &rhs.0) };
175    }
176}
177
178impl MulAssign<&Fp2> for Fp2 {
179    #[inline]
180    fn mul_assign(&mut self, rhs: &Fp2) {
181        unsafe { blst_fp2_mul(&mut self.0, &self.0, &rhs.0) };
182    }
183}
184
185impl_add_sub!(Fp2);
186impl_add_sub_assign!(Fp2);
187impl_mul!(Fp2);
188impl_mul_assign!(Fp2);
189impl_sum!(Fp2);
190impl_product!(Fp2);
191
192impl Fp2 {
193    /// Constructs an element of `Fp2`.
194    pub const fn new(c0: Fp, c1: Fp) -> Fp2 {
195        Fp2(blst_fp2 { fp: [c0.0, c1.0] })
196    }
197
198    /// Multiplies `self` with `3`, returning the result.
199    pub fn mul3(&self) -> Self {
200        let mut out = *self;
201        unsafe { blst_fp2_mul_by_3(&mut out.0, &self.0) };
202        out
203    }
204
205    /// Multiplies `self` with `8`, returning the result.
206    pub fn mul8(&self) -> Self {
207        let mut out = *self;
208        unsafe { blst_fp2_mul_by_8(&mut out.0, &self.0) };
209        out
210    }
211
212    /// Left shift `self` by `count`, returning the result.
213    pub fn shl(&self, count: usize) -> Self {
214        let mut out = *self;
215        unsafe { blst_fp2_lshift(&mut out.0, &self.0, count) };
216        out
217    }
218
219    pub fn c0(&self) -> Fp {
220        Fp(self.0.fp[0])
221    }
222
223    pub fn c1(&self) -> Fp {
224        Fp(self.0.fp[1])
225    }
226
227    /// Multiply this element by the cubic and quadratic nonresidue 1 + u.
228    pub fn mul_by_nonresidue(&mut self) {
229        let t0 = self.c0();
230        let c0 = self.c0() - self.c1();
231        let c1 = self.c1() + t0;
232
233        self.0.fp[0] = c0.0;
234        self.0.fp[1] = c1.0;
235    }
236
237    /// Norm of Fq2 as extension field in i over Fq
238    pub fn norm(&self) -> Fp {
239        self.c0().square() + self.c1().square()
240    }
241
242    pub fn frobenius_map(&mut self, power: usize) {
243        let mut c1 = self.c1();
244        c1 *= &FROBENIUS_COEFF_FP2_C1[power % 2];
245        self.0.fp[1] = c1.0;
246    }
247
248    pub fn is_quad_res(&self) -> bool {
249        self.sqrt().is_some().into()
250    }
251}
252
253impl Field for Fp2 {
254    fn random(mut rng: impl RngCore) -> Self {
255        Fp2::new(Fp::random(&mut rng), Fp::random(&mut rng))
256    }
257
258    const ZERO: Self = Fp2(blst_fp2 {
259        fp: [Fp::ZERO.0, Fp::ZERO.0],
260    });
261
262    const ONE: Self = Fp2(blst_fp2 {
263        fp: [Fp::ONE.0, Fp::ZERO.0],
264    });
265
266    fn is_zero(&self) -> Choice {
267        self.c0().is_zero() & self.c1().is_zero()
268    }
269
270    fn square(&self) -> Self {
271        let mut sq = *self;
272        unsafe { blst_fp2_sqr(&mut sq.0, &self.0) }
273        sq
274    }
275
276    fn double(&self) -> Self {
277        let mut out = *self;
278        out += self;
279        out
280    }
281
282    fn invert(&self) -> CtOption<Self> {
283        let is_zero = self.is_zero();
284        let mut out = *self;
285        unsafe { blst_fp2_eucl_inverse(&mut out.0, &self.0) };
286        CtOption::new(out, !is_zero)
287    }
288
289    fn sqrt(&self) -> CtOption<Self> {
290        let mut out = Self::default();
291        let is_quad_res = unsafe { blst_fp2_sqrt(&mut out.0, &self.0) };
292        CtOption::new(out, Choice::from(is_quad_res as u8))
293    }
294
295    fn sqrt_ratio(_num: &Self, _div: &Self) -> (Choice, Self) {
296        // ff::helpers::sqrt_ratio_generic(num, div)
297        unimplemented!()
298    }
299}
300
301#[cfg(feature = "gpu")]
302impl ec_gpu::GpuName for Fp2 {
303    fn name() -> String {
304        ec_gpu::name!()
305    }
306}
307
308// Use `one`, `r2` and `modulus` from the sub-field.
309#[cfg(feature = "gpu")]
310impl ec_gpu::GpuField for Fp2 {
311    fn one() -> Vec<u32> {
312        <Fp as ec_gpu::GpuField>::one()
313    }
314
315    fn r2() -> Vec<u32> {
316        Fp::r2()
317    }
318
319    fn modulus() -> Vec<u32> {
320        Fp::modulus()
321    }
322
323    fn sub_field_name() -> Option<String> {
324        use ec_gpu::GpuName;
325        Some(Fp::name())
326    }
327}
328
329#[cfg(test)]
330mod tests {
331    use super::*;
332
333    use rand_core::SeedableRng;
334    use rand_xorshift::XorShiftRng;
335
336    #[test]
337    fn test_fp2_ordering() {
338        let mut a = Fp2::new(Fp::ZERO, Fp::ZERO);
339        let mut b = a;
340
341        assert!(a.cmp(&b) == Ordering::Equal);
342        b.0.fp[0] = (b.c0() + Fp::ONE).0;
343        assert!(a.cmp(&b) == Ordering::Less);
344        a.0.fp[0] = (a.c0() + Fp::ONE).0;
345        assert!(a.cmp(&b) == Ordering::Equal);
346        b.0.fp[1] = (b.c1() + Fp::ONE).0;
347        assert!(a.cmp(&b) == Ordering::Less);
348        a.0.fp[0] = (a.c0() + Fp::ONE).0;
349        assert!(a.cmp(&b) == Ordering::Less);
350        a.0.fp[1] = (a.c1() + Fp::ONE).0;
351        assert!(a.cmp(&b) == Ordering::Greater);
352        b.0.fp[0] = (b.c0() + Fp::ONE).0;
353        assert!(a.cmp(&b) == Ordering::Equal);
354    }
355
356    #[test]
357    fn test_fp2_basics() {
358        assert_eq!(Fp2::new(Fp::ZERO, Fp::ZERO), Fp2::ZERO);
359        assert_eq!(Fp2::new(Fp::ONE, Fp::ZERO), Fp2::ONE);
360        assert!(bool::from(Fp2::ZERO.is_zero()));
361        assert!(!bool::from(Fp2::ONE.is_zero()));
362        assert!(!bool::from(Fp2::new(Fp::ZERO, Fp::ONE,).is_zero()));
363    }
364
365    #[test]
366    fn test_fp2_squaring() {
367        let a = Fp2::new(Fp::ONE, Fp::ONE); // u + 1
368        let a_sq = a.square();
369        assert_eq!(a_sq, Fp2::new(Fp::ZERO, Fp::from(2))); // 2u
370
371        let a = Fp2::new(Fp::ZERO, Fp::ONE); // u
372        let a_sq = a.square();
373        assert_eq!(a_sq, Fp2::new(-Fp::ONE, Fp::ZERO)); // -1
374
375        let a = Fp2::new(
376            Fp::from_u64s_le(&[
377                0x9c2c6309bbf8b598,
378                0x4eef5c946536f602,
379                0x90e34aab6fb6a6bd,
380                0xf7f295a94e58ae7c,
381                0x41b76dcc1c3fbe5e,
382                0x7080c5fa1d8e042,
383            ])
384            .unwrap(),
385            Fp::from_u64s_le(&[
386                0x38f473b3c870a4ab,
387                0x6ad3291177c8c7e5,
388                0xdac5a4c911a4353e,
389                0xbfb99020604137a0,
390                0xfc58a7b7be815407,
391                0x10d1615e75250a21,
392            ])
393            .unwrap(),
394        );
395        let a_sq = a.square();
396        assert_eq!(
397            a_sq,
398            Fp2::new(
399                Fp::from_u64s_le(&[
400                    0xf262c28c538bcf68,
401                    0xb9f2a66eae1073ba,
402                    0xdc46ab8fad67ae0,
403                    0xcb674157618da176,
404                    0x4cf17b5893c3d327,
405                    0x7eac81369c43361
406                ])
407                .unwrap(),
408                Fp::from_u64s_le(&[
409                    0xc1579cf58e980cf8,
410                    0xa23eb7e12dd54d98,
411                    0xe75138bce4cec7aa,
412                    0x38d0d7275a9689e1,
413                    0x739c983042779a65,
414                    0x1542a61c8a8db994
415                ])
416                .unwrap(),
417            )
418        );
419    }
420
421    #[test]
422    fn test_fp2_mul() {
423        let mut a = Fp2::new(
424            Fp::from_u64s_le(&[
425                0x85c9f989e1461f03,
426                0xa2e33c333449a1d6,
427                0x41e461154a7354a3,
428                0x9ee53e7e84d7532e,
429                0x1c202d8ed97afb45,
430                0x51d3f9253e2516f,
431            ])
432            .unwrap(),
433            Fp::from_u64s_le(&[
434                0xa7348a8b511aedcf,
435                0x143c215d8176b319,
436                0x4cc48081c09b8903,
437                0x9533e4a9a5158be,
438                0x7a5e1ecb676d65f9,
439                0x180c3ee46656b008,
440            ])
441            .unwrap(),
442        );
443        a *= &Fp2::new(
444            Fp::from_u64s_le(&[
445                0xe21f9169805f537e,
446                0xfc87e62e179c285d,
447                0x27ece175be07a531,
448                0xcd460f9f0c23e430,
449                0x6c9110292bfa409,
450                0x2c93a72eb8af83e,
451            ])
452            .unwrap(),
453            Fp::from_u64s_le(&[
454                0x4b1c3f936d8992d4,
455                0x1d2a72916dba4c8a,
456                0x8871c508658d1e5f,
457                0x57a06d3135a752ae,
458                0x634cd3c6c565096d,
459                0x19e17334d4e93558,
460            ])
461            .unwrap(),
462        );
463        assert_eq!(
464            a,
465            Fp2::new(
466                Fp::from_u64s_le(&[
467                    0x95b5127e6360c7e4,
468                    0xde29c31a19a6937e,
469                    0xf61a96dacf5a39bc,
470                    0x5511fe4d84ee5f78,
471                    0x5310a202d92f9963,
472                    0x1751afbe166e5399
473                ])
474                .unwrap(),
475                Fp::from_u64s_le(&[
476                    0x84af0e1bd630117a,
477                    0x6c63cd4da2c2aa7,
478                    0x5ba6e5430e883d40,
479                    0xc975106579c275ee,
480                    0x33a9ac82ce4c5083,
481                    0x1ef1a36c201589d
482                ])
483                .unwrap(),
484            )
485        );
486    }
487
488    #[test]
489    fn test_fp2_inverse() {
490        assert_eq!(Fp2::ZERO.invert().is_none().unwrap_u8(), 1);
491
492        let a = Fp2::new(
493            Fp::from_u64s_le(&[
494                0x85c9f989e1461f03,
495                0xa2e33c333449a1d6,
496                0x41e461154a7354a3,
497                0x9ee53e7e84d7532e,
498                0x1c202d8ed97afb45,
499                0x51d3f9253e2516f,
500            ])
501            .unwrap(),
502            Fp::from_u64s_le(&[
503                0xa7348a8b511aedcf,
504                0x143c215d8176b319,
505                0x4cc48081c09b8903,
506                0x9533e4a9a5158be,
507                0x7a5e1ecb676d65f9,
508                0x180c3ee46656b008,
509            ])
510            .unwrap(),
511        );
512        let a = a.invert().unwrap();
513        assert_eq!(
514            a,
515            Fp2::new(
516                Fp::from_u64s_le(&[
517                    0x70300f9bcb9e594,
518                    0xe5ecda5fdafddbb2,
519                    0x64bef617d2915a8f,
520                    0xdfba703293941c30,
521                    0xa6c3d8f9586f2636,
522                    0x1351ef01941b70c4
523                ])
524                .unwrap(),
525                Fp::from_u64s_le(&[
526                    0x8c39fd76a8312cb4,
527                    0x15d7b6b95defbff0,
528                    0x947143f89faedee9,
529                    0xcbf651a0f367afb2,
530                    0xdf4e54f0d3ef15a6,
531                    0x103bdf241afb0019
532                ])
533                .unwrap(),
534            )
535        );
536    }
537
538    #[test]
539    fn test_fp2_addition() {
540        let mut a = Fp2::new(
541            Fp::from_u64s_le(&[
542                0x2d0078036923ffc7,
543                0x11e59ea221a3b6d2,
544                0x8b1a52e0a90f59ed,
545                0xb966ce3bc2108b13,
546                0xccc649c4b9532bf3,
547                0xf8d295b2ded9dc,
548            ])
549            .unwrap(),
550            Fp::from_u64s_le(&[
551                0x977df6efcdaee0db,
552                0x946ae52d684fa7ed,
553                0xbe203411c66fb3a5,
554                0xb3f8afc0ee248cad,
555                0x4e464dea5bcfd41e,
556                0x12d1137b8a6a837,
557            ])
558            .unwrap(),
559        );
560        a += &Fp2::new(
561            Fp::from_u64s_le(&[
562                0x619a02d78dc70ef2,
563                0xb93adfc9119e33e8,
564                0x4bf0b99a9f0dca12,
565                0x3b88899a42a6318f,
566                0x986a4a62fa82a49d,
567                0x13ce433fa26027f5,
568            ])
569            .unwrap(),
570            Fp::from_u64s_le(&[
571                0x66323bf80b58b9b9,
572                0xa1379b6facf6e596,
573                0x402aef1fb797e32f,
574                0x2236f55246d0d44d,
575                0x4c8c1800eb104566,
576                0x11d6e20e986c2085,
577            ])
578            .unwrap(),
579        );
580        assert_eq!(
581            a,
582            Fp2::new(
583                Fp::from_u64s_le(&[
584                    0x8e9a7adaf6eb0eb9,
585                    0xcb207e6b3341eaba,
586                    0xd70b0c7b481d23ff,
587                    0xf4ef57d604b6bca2,
588                    0x65309427b3d5d090,
589                    0x14c715d5553f01d2
590                ])
591                .unwrap(),
592                Fp::from_u64s_le(&[
593                    0xfdb032e7d9079a94,
594                    0x35a2809d15468d83,
595                    0xfe4b23317e0796d5,
596                    0xd62fa51334f560fa,
597                    0x9ad265eb46e01984,
598                    0x1303f3465112c8bc
599                ])
600                .unwrap(),
601            )
602        );
603    }
604
605    #[test]
606    fn test_fp2_subtraction() {
607        let mut a = Fp2::new(
608            Fp::from_u64s_le(&[
609                0x2d0078036923ffc7,
610                0x11e59ea221a3b6d2,
611                0x8b1a52e0a90f59ed,
612                0xb966ce3bc2108b13,
613                0xccc649c4b9532bf3,
614                0xf8d295b2ded9dc,
615            ])
616            .unwrap(),
617            Fp::from_u64s_le(&[
618                0x977df6efcdaee0db,
619                0x946ae52d684fa7ed,
620                0xbe203411c66fb3a5,
621                0xb3f8afc0ee248cad,
622                0x4e464dea5bcfd41e,
623                0x12d1137b8a6a837,
624            ])
625            .unwrap(),
626        );
627        a -= &Fp2::new(
628            Fp::from_u64s_le(&[
629                0x619a02d78dc70ef2,
630                0xb93adfc9119e33e8,
631                0x4bf0b99a9f0dca12,
632                0x3b88899a42a6318f,
633                0x986a4a62fa82a49d,
634                0x13ce433fa26027f5,
635            ])
636            .unwrap(),
637            Fp::from_u64s_le(&[
638                0x66323bf80b58b9b9,
639                0xa1379b6facf6e596,
640                0x402aef1fb797e32f,
641                0x2236f55246d0d44d,
642                0x4c8c1800eb104566,
643                0x11d6e20e986c2085,
644            ])
645            .unwrap(),
646        );
647        assert_eq!(
648            a,
649            Fp2::new(
650                Fp::from_u64s_le(&[
651                    0x8565752bdb5c9b80,
652                    0x7756bed7c15982e9,
653                    0xa65a6be700b285fe,
654                    0xe255902672ef6c43,
655                    0x7f77a718021c342d,
656                    0x72ba14049fe9881
657                ])
658                .unwrap(),
659                Fp::from_u64s_le(&[
660                    0xeb4abaf7c255d1cd,
661                    0x11df49bc6cacc256,
662                    0xe52617930588c69a,
663                    0xf63905f39ad8cb1f,
664                    0x4cd5dd9fb40b3b8f,
665                    0x957411359ba6e4c
666                ])
667                .unwrap(),
668            )
669        );
670    }
671
672    #[test]
673    fn test_fp2_negaton() {
674        let a = Fp2::new(
675            Fp::from_u64s_le(&[
676                0x2d0078036923ffc7,
677                0x11e59ea221a3b6d2,
678                0x8b1a52e0a90f59ed,
679                0xb966ce3bc2108b13,
680                0xccc649c4b9532bf3,
681                0xf8d295b2ded9dc,
682            ])
683            .unwrap(),
684            Fp::from_u64s_le(&[
685                0x977df6efcdaee0db,
686                0x946ae52d684fa7ed,
687                0xbe203411c66fb3a5,
688                0xb3f8afc0ee248cad,
689                0x4e464dea5bcfd41e,
690                0x12d1137b8a6a837,
691            ])
692            .unwrap(),
693        );
694        assert_eq!(
695            -a,
696            Fp2::new(
697                Fp::from_u64s_le(&[
698                    0x8cfe87fc96dbaae4,
699                    0xcc6615c8fb0492d,
700                    0xdc167fc04da19c37,
701                    0xab107d49317487ab,
702                    0x7e555df189f880e3,
703                    0x19083f5486a10cbd
704                ])
705                .unwrap(),
706                Fp::from_u64s_le(&[
707                    0x228109103250c9d0,
708                    0x8a411ad149045812,
709                    0xa9109e8f3041427e,
710                    0xb07e9bc405608611,
711                    0xfcd559cbe77bd8b8,
712                    0x18d400b280d93e62
713                ])
714                .unwrap(),
715            )
716        );
717    }
718
719    #[test]
720    fn test_fp2_doubling() {
721        let a = Fp2::new(
722            Fp::from_u64s_le(&[
723                0x2d0078036923ffc7,
724                0x11e59ea221a3b6d2,
725                0x8b1a52e0a90f59ed,
726                0xb966ce3bc2108b13,
727                0xccc649c4b9532bf3,
728                0xf8d295b2ded9dc,
729            ])
730            .unwrap(),
731            Fp::from_u64s_le(&[
732                0x977df6efcdaee0db,
733                0x946ae52d684fa7ed,
734                0xbe203411c66fb3a5,
735                0xb3f8afc0ee248cad,
736                0x4e464dea5bcfd41e,
737                0x12d1137b8a6a837,
738            ])
739            .unwrap(),
740        );
741        assert_eq!(
742            a.double(),
743            Fp2::new(
744                Fp::from_u64s_le(&[
745                    0x5a00f006d247ff8e,
746                    0x23cb3d4443476da4,
747                    0x1634a5c1521eb3da,
748                    0x72cd9c7784211627,
749                    0x998c938972a657e7,
750                    0x1f1a52b65bdb3b9
751                ])
752                .unwrap(),
753                Fp::from_u64s_le(&[
754                    0x2efbeddf9b5dc1b6,
755                    0x28d5ca5ad09f4fdb,
756                    0x7c4068238cdf674b,
757                    0x67f15f81dc49195b,
758                    0x9c8c9bd4b79fa83d,
759                    0x25a226f714d506e
760                ])
761                .unwrap(),
762            )
763        );
764    }
765
766    #[test]
767    fn test_fp2_frobenius_map() {
768        let mut a = Fp2::new(
769            Fp::from_u64s_le(&[
770                0x2d0078036923ffc7,
771                0x11e59ea221a3b6d2,
772                0x8b1a52e0a90f59ed,
773                0xb966ce3bc2108b13,
774                0xccc649c4b9532bf3,
775                0xf8d295b2ded9dc,
776            ])
777            .unwrap(),
778            Fp::from_u64s_le(&[
779                0x977df6efcdaee0db,
780                0x946ae52d684fa7ed,
781                0xbe203411c66fb3a5,
782                0xb3f8afc0ee248cad,
783                0x4e464dea5bcfd41e,
784                0x12d1137b8a6a837,
785            ])
786            .unwrap(),
787        );
788        a.frobenius_map(0);
789        assert_eq!(
790            a,
791            Fp2::new(
792                Fp::from_u64s_le(&[
793                    0x2d0078036923ffc7,
794                    0x11e59ea221a3b6d2,
795                    0x8b1a52e0a90f59ed,
796                    0xb966ce3bc2108b13,
797                    0xccc649c4b9532bf3,
798                    0xf8d295b2ded9dc
799                ])
800                .unwrap(),
801                Fp::from_u64s_le(&[
802                    0x977df6efcdaee0db,
803                    0x946ae52d684fa7ed,
804                    0xbe203411c66fb3a5,
805                    0xb3f8afc0ee248cad,
806                    0x4e464dea5bcfd41e,
807                    0x12d1137b8a6a837
808                ])
809                .unwrap(),
810            )
811        );
812        a.frobenius_map(1);
813        assert_eq!(
814            a,
815            Fp2::new(
816                Fp::from_u64s_le(&[
817                    0x2d0078036923ffc7,
818                    0x11e59ea221a3b6d2,
819                    0x8b1a52e0a90f59ed,
820                    0xb966ce3bc2108b13,
821                    0xccc649c4b9532bf3,
822                    0xf8d295b2ded9dc
823                ])
824                .unwrap(),
825                Fp::from_u64s_le(&[
826                    0x228109103250c9d0,
827                    0x8a411ad149045812,
828                    0xa9109e8f3041427e,
829                    0xb07e9bc405608611,
830                    0xfcd559cbe77bd8b8,
831                    0x18d400b280d93e62
832                ])
833                .unwrap(),
834            )
835        );
836        a.frobenius_map(1);
837        assert_eq!(
838            a,
839            Fp2::new(
840                Fp::from_u64s_le(&[
841                    0x2d0078036923ffc7,
842                    0x11e59ea221a3b6d2,
843                    0x8b1a52e0a90f59ed,
844                    0xb966ce3bc2108b13,
845                    0xccc649c4b9532bf3,
846                    0xf8d295b2ded9dc
847                ])
848                .unwrap(),
849                Fp::from_u64s_le(&[
850                    0x977df6efcdaee0db,
851                    0x946ae52d684fa7ed,
852                    0xbe203411c66fb3a5,
853                    0xb3f8afc0ee248cad,
854                    0x4e464dea5bcfd41e,
855                    0x12d1137b8a6a837
856                ])
857                .unwrap(),
858            )
859        );
860        a.frobenius_map(2);
861        assert_eq!(
862            a,
863            Fp2::new(
864                Fp::from_u64s_le(&[
865                    0x2d0078036923ffc7,
866                    0x11e59ea221a3b6d2,
867                    0x8b1a52e0a90f59ed,
868                    0xb966ce3bc2108b13,
869                    0xccc649c4b9532bf3,
870                    0xf8d295b2ded9dc
871                ])
872                .unwrap(),
873                Fp::from_u64s_le(&[
874                    0x977df6efcdaee0db,
875                    0x946ae52d684fa7ed,
876                    0xbe203411c66fb3a5,
877                    0xb3f8afc0ee248cad,
878                    0x4e464dea5bcfd41e,
879                    0x12d1137b8a6a837
880                ])
881                .unwrap(),
882            )
883        );
884    }
885
886    #[test]
887    fn test_fp2_sqrt_2() {
888        // a = 1488924004771393321054797166853618474668089414631333405711627789629391903630694737978065425271543178763948256226639*u + 784063022264861764559335808165825052288770346101304131934508881646553551234697082295473567906267937225174620141295
889        let a = Fp2::new(
890            Fp::from_raw_unchecked([
891                0x2bee_d146_27d7_f9e9,
892                0xb661_4e06_660e_5dce,
893                0x06c4_cc7c_2f91_d42c,
894                0x996d_7847_4b7a_63cc,
895                0xebae_bc4c_820d_574e,
896                0x1886_5e12_d93f_d845,
897            ]),
898            Fp::from_raw_unchecked([
899                0x7d82_8664_baf4_f566,
900                0xd17e_6639_96ec_7339,
901                0x679e_ad55_cb40_78d0,
902                0xfe3b_2260_e001_ec28,
903                0x3059_93d0_43d9_1b68,
904                0x0626_f03c_0489_b72d,
905            ]),
906        );
907
908        assert_eq!(a.sqrt().unwrap().square(), a);
909
910        // b = 5, which is a generator of the p - 1 order
911        // multiplicative subgroup
912        let b = Fp2::new(
913            Fp::from_raw_unchecked([
914                0x6631_0000_0010_5545,
915                0x2114_0040_0eec_000d,
916                0x3fa7_af30_c820_e316,
917                0xc52a_8b8d_6387_695d,
918                0x9fb4_e61d_1e83_eac5,
919                0x005c_b922_afe8_4dc7,
920            ]),
921            Fp::ZERO,
922        );
923
924        assert_eq!(b.sqrt().unwrap().square(), b);
925
926        // c = 25, which is a generator of the (p - 1) / 2 order
927        // multiplicative subgroup
928        let c = Fp2::new(
929            Fp::from_raw_unchecked([
930                0x44f6_0000_0051_ffae,
931                0x86b8_0141_9948_0043,
932                0xd715_9952_f1f3_794a,
933                0x755d_6e3d_fe1f_fc12,
934                0xd36c_d6db_5547_e905,
935                0x02f8_c8ec_bf18_67bb,
936            ]),
937            Fp::ZERO,
938        );
939
940        assert_eq!(c.sqrt().unwrap().square(), c);
941
942        // 2155129644831861015726826462986972654175647013268275306775721078997042729172900466542651176384766902407257452753362*u + 2796889544896299244102912275102369318775038861758288697415827248356648685135290329705805931514906495247464901062529
943        // is nonsquare.
944        assert!(bool::from(
945            Fp2::new(
946                Fp::from_raw_unchecked([
947                    0xc5fa_1bc8_fd00_d7f6,
948                    0x3830_ca45_4606_003b,
949                    0x2b28_7f11_04b1_02da,
950                    0xa7fb_30f2_8230_f23e,
951                    0x339c_db9e_e953_dbf0,
952                    0x0d78_ec51_d989_fc57,
953                ]),
954                Fp::from_raw_unchecked([
955                    0x27ec_4898_cf87_f613,
956                    0x9de1_394e_1abb_05a5,
957                    0x0947_f85d_c170_fc14,
958                    0x586f_bc69_6b61_14b7,
959                    0x2b34_75a4_077d_7169,
960                    0x13e1_c895_cc4b_6c22,
961                ])
962            )
963            .sqrt()
964            .is_none()
965        ));
966    }
967
968    #[test]
969    fn test_fp2_sqrt() {
970        assert_eq!(
971            Fp2::new(
972                Fp::from_u64s_le(&[
973                    0x476b4c309720e227,
974                    0x34c2d04faffdab6,
975                    0xa57e6fc1bab51fd9,
976                    0xdb4a116b5bf74aa1,
977                    0x1e58b2159dfe10e2,
978                    0x7ca7da1f13606ac
979                ])
980                .unwrap(),
981                Fp::from_u64s_le(&[
982                    0xfa8de88b7516d2c3,
983                    0x371a75ed14f41629,
984                    0x4cec2dca577a3eb6,
985                    0x212611bca4e99121,
986                    0x8ee5394d77afb3d,
987                    0xec92336650e49d5
988                ])
989                .unwrap()
990            )
991            .sqrt()
992            .unwrap(),
993            Fp2::new(
994                Fp::from_u64s_le(&[
995                    0x40b299b2704258c5,
996                    0x6ef7de92e8c68b63,
997                    0x6d2ddbe552203e82,
998                    0x8d7f1f723d02c1d3,
999                    0x881b3e01b611c070,
1000                    0x10f6963bbad2ebc5
1001                ])
1002                .unwrap(),
1003                Fp::from_u64s_le(&[
1004                    0xc099534fc209e752,
1005                    0x7670594665676447,
1006                    0x28a20faed211efe7,
1007                    0x6b852aeaf2afcb1b,
1008                    0xa4c93b08105d71a9,
1009                    0x8d7cfff94216330
1010                ])
1011                .unwrap()
1012            )
1013            .neg()
1014        );
1015
1016        assert_eq!(
1017            Fp2::new(
1018                Fp::from_u64s_le(&[
1019                    0xb9f78429d1517a6b,
1020                    0x1eabfffeb153ffff,
1021                    0x6730d2a0f6b0f624,
1022                    0x64774b84f38512bf,
1023                    0x4b1ba7b6434bacd7,
1024                    0x1a0111ea397fe69a
1025                ])
1026                .unwrap(),
1027                Fp::ZERO,
1028            )
1029            .sqrt()
1030            .unwrap(),
1031            Fp2::new(
1032                Fp::ZERO,
1033                Fp::from_u64s_le(&[
1034                    0xb9fefffffd4357a3,
1035                    0x1eabfffeb153ffff,
1036                    0x6730d2a0f6b0f624,
1037                    0x64774b84f38512bf,
1038                    0x4b1ba7b6434bacd7,
1039                    0x1a0111ea397fe69a
1040                ])
1041                .unwrap()
1042            )
1043        );
1044    }
1045
1046    #[test]
1047    fn test_fp2_legendre() {
1048        assert_eq!(Fp2::ZERO.sqrt().unwrap(), Fp2::ZERO);
1049        // i^2 = -1
1050        let mut a = -Fp2::ONE;
1051        assert!(a.is_quad_res());
1052        a.mul_by_nonresidue();
1053        assert!(!a.is_quad_res());
1054    }
1055
1056    #[test]
1057    fn test_fp2_mul_nonresidue() {
1058        let mut rng = XorShiftRng::from_seed([
1059            0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06,
1060            0xbc, 0xe5,
1061        ]);
1062
1063        let nqr = Fp2::new(Fp::ONE, Fp::ONE);
1064
1065        for _ in 0..1000 {
1066            let mut a = Fp2::random(&mut rng);
1067            let mut b = a;
1068            a.mul_by_nonresidue();
1069            b *= &nqr;
1070
1071            assert_eq!(a, b);
1072        }
1073    }
1074
1075    #[test]
1076    fn fp2_field_tests() {
1077        crate::tests::field::random_field_tests::<Fp2>();
1078        crate::tests::field::random_sqrt_tests::<Fp2>();
1079    }
1080
1081    #[test]
1082    fn test_fp2_frobenius() {
1083        use std::convert::TryFrom;
1084
1085        let mut rng = XorShiftRng::from_seed([
1086            0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06,
1087            0xbc, 0xe5,
1088        ]);
1089
1090        let characteristic: Vec<u64> = Fp::char()
1091            .chunks(8)
1092            .map(|chunk| u64::from_le_bytes(<[u8; 8]>::try_from(chunk).unwrap()))
1093            .collect();
1094
1095        let maxpower = 13;
1096
1097        for _ in 0..100 {
1098            for i in 0..(maxpower + 1) {
1099                let mut a = Fp2::random(&mut rng);
1100                let mut b = a;
1101
1102                for _ in 0..i {
1103                    a = a.pow_vartime(&characteristic);
1104                }
1105                b.frobenius_map(i);
1106
1107                assert_eq!(a, b);
1108            }
1109        }
1110    }
1111}
nam_blstrs/fp2.rs

nam_blstrs/
fp2.rs
