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

nam_blstrs/
fp2.rs
