pairing_plus/bls12_381/
fq2.rs

1use super::fq::{Fq, FROBENIUS_COEFF_FQ2_C1, NEGATIVE_ONE};
2use digest::generic_array::{
3    typenum::{U128, U64},
4    GenericArray,
5};
6use ff::{Field, SqrtField};
7use hash_to_field::{BaseFromRO, FromRO};
8use signum::{Sgn0Result, Signum0};
9use std::cmp::Ordering;
10
11/// An element of Fq2, represented by c0 + c1 * u.
12#[derive(Copy, Clone, Debug, Eq, PartialEq, Zeroize)]
13pub struct Fq2 {
14    pub c0: Fq,
15    pub c1: Fq,
16}
17
18impl ::std::fmt::Display for Fq2 {
19    fn fmt(&self, f: &mut ::std::fmt::Formatter) -> ::std::fmt::Result {
20        write!(f, "Fq2({} + {} * u)", self.c0, self.c1)
21    }
22}
23
24/// `Fq2` elements are ordered lexicographically.
25impl Ord for Fq2 {
26    #[inline(always)]
27    fn cmp(&self, other: &Fq2) -> Ordering {
28        match self.c1.cmp(&other.c1) {
29            Ordering::Greater => Ordering::Greater,
30            Ordering::Less => Ordering::Less,
31            Ordering::Equal => self.c0.cmp(&other.c0),
32        }
33    }
34}
35
36impl PartialOrd for Fq2 {
37    #[inline(always)]
38    fn partial_cmp(&self, other: &Fq2) -> Option<Ordering> {
39        Some(self.cmp(other))
40    }
41}
42
43impl Fq2 {
44    /// Multiply this element by the cubic and quadratic nonresidue 1 + u.
45    pub fn mul_by_nonresidue(&mut self) {
46        let t0 = self.c0;
47        self.c0.sub_assign(&self.c1);
48        self.c1.add_assign(&t0);
49    }
50
51    /// Norm of Fq2 as extension field in i over Fq
52    pub fn norm(&self) -> Fq {
53        let mut t0 = self.c0;
54        let mut t1 = self.c1;
55        t0.square();
56        t1.square();
57        t1.add_assign(&t0);
58
59        t1
60    }
61}
62
63impl Field for Fq2 {
64    fn random<R: rand_core::RngCore + ?std::marker::Sized>(rng: &mut R) -> Self {
65        Fq2 {
66            c0: Fq::random(rng),
67            c1: Fq::random(rng),
68        }
69    }
70    fn zero() -> Self {
71        Fq2 {
72            c0: Fq::zero(),
73            c1: Fq::zero(),
74        }
75    }
76
77    fn one() -> Self {
78        Fq2 {
79            c0: Fq::one(),
80            c1: Fq::zero(),
81        }
82    }
83
84    fn is_zero(&self) -> bool {
85        self.c0.is_zero() && self.c1.is_zero()
86    }
87
88    fn square(&mut self) {
89        let mut ab = self.c0;
90        ab.mul_assign(&self.c1);
91        let mut c0c1 = self.c0;
92        c0c1.add_assign(&self.c1);
93        let mut c0 = self.c1;
94        c0.negate();
95        c0.add_assign(&self.c0);
96        c0.mul_assign(&c0c1);
97        c0.sub_assign(&ab);
98        self.c1 = ab;
99        self.c1.add_assign(&ab);
100        c0.add_assign(&ab);
101        self.c0 = c0;
102    }
103
104    fn double(&mut self) {
105        self.c0.double();
106        self.c1.double();
107    }
108
109    fn negate(&mut self) {
110        self.c0.negate();
111        self.c1.negate();
112    }
113
114    fn add_assign(&mut self, other: &Self) {
115        self.c0.add_assign(&other.c0);
116        self.c1.add_assign(&other.c1);
117    }
118
119    fn sub_assign(&mut self, other: &Self) {
120        self.c0.sub_assign(&other.c0);
121        self.c1.sub_assign(&other.c1);
122    }
123
124    fn mul_assign(&mut self, other: &Self) {
125        let mut aa = self.c0;
126        aa.mul_assign(&other.c0);
127        let mut bb = self.c1;
128        bb.mul_assign(&other.c1);
129        let mut o = other.c0;
130        o.add_assign(&other.c1);
131        self.c1.add_assign(&self.c0);
132        self.c1.mul_assign(&o);
133        self.c1.sub_assign(&aa);
134        self.c1.sub_assign(&bb);
135        self.c0 = aa;
136        self.c0.sub_assign(&bb);
137    }
138
139    fn inverse(&self) -> Option<Self> {
140        let mut t1 = self.c1;
141        t1.square();
142        let mut t0 = self.c0;
143        t0.square();
144        t0.add_assign(&t1);
145        t0.inverse().map(|t| {
146            let mut tmp = Fq2 {
147                c0: self.c0,
148                c1: self.c1,
149            };
150            tmp.c0.mul_assign(&t);
151            tmp.c1.mul_assign(&t);
152            tmp.c1.negate();
153
154            tmp
155        })
156    }
157
158    fn frobenius_map(&mut self, power: usize) {
159        self.c1.mul_assign(&FROBENIUS_COEFF_FQ2_C1[power % 2]);
160    }
161}
162
163impl SqrtField for Fq2 {
164    fn legendre(&self) -> ::ff::LegendreSymbol {
165        self.norm().legendre()
166    }
167
168    fn sqrt(&self) -> Option<Self> {
169        // Algorithm 9, https://eprint.iacr.org/2012/685.pdf
170
171        if self.is_zero() {
172            Some(Self::zero())
173        } else {
174            // a1 = self^((q - 3) / 4)
175            let mut a1 = self.pow([
176                0xee7fbfffffffeaaa,
177                0x7aaffffac54ffff,
178                0xd9cc34a83dac3d89,
179                0xd91dd2e13ce144af,
180                0x92c6e9ed90d2eb35,
181                0x680447a8e5ff9a6,
182            ]);
183            let mut alpha = a1;
184            alpha.square();
185            alpha.mul_assign(self);
186            let mut a0 = alpha;
187            a0.frobenius_map(1);
188            a0.mul_assign(&alpha);
189
190            let neg1 = Fq2 {
191                c0: NEGATIVE_ONE,
192                c1: Fq::zero(),
193            };
194
195            if a0 == neg1 {
196                None
197            } else {
198                a1.mul_assign(self);
199
200                if alpha == neg1 {
201                    a1.mul_assign(&Fq2 {
202                        c0: Fq::zero(),
203                        c1: Fq::one(),
204                    });
205                } else {
206                    alpha.add_assign(&Fq2::one());
207                    // alpha = alpha^((q - 1) / 2)
208                    alpha = alpha.pow([
209                        0xdcff7fffffffd555,
210                        0xf55ffff58a9ffff,
211                        0xb39869507b587b12,
212                        0xb23ba5c279c2895f,
213                        0x258dd3db21a5d66b,
214                        0xd0088f51cbff34d,
215                    ]);
216                    a1.mul_assign(&alpha);
217                }
218
219                Some(a1)
220            }
221        }
222    }
223}
224
225/// Fq2 implementation: hash to two elemnts of Fq and combine.
226impl FromRO for Fq2 {
227    type Length = U128;
228
229    fn from_ro(okm: &GenericArray<u8, U128>) -> Fq2 {
230        let c0 = Fq::from_okm(GenericArray::<u8, U64>::from_slice(&okm[..64]));
231        let c1 = Fq::from_okm(GenericArray::<u8, U64>::from_slice(&okm[64..]));
232        Fq2 { c0, c1 }
233    }
234}
235
236impl Signum0 for Fq2 {
237    fn sgn0(&self) -> Sgn0Result {
238        let Fq2 { c0, c1 } = self;
239        if c1.is_zero() {
240            c0.sgn0()
241        } else {
242            c1.sgn0()
243        }
244    }
245}
246
247#[test]
248fn test_fq2_ordering() {
249    let mut a = Fq2 {
250        c0: Fq::zero(),
251        c1: Fq::zero(),
252    };
253
254    let mut b = a;
255
256    assert!(a.cmp(&b) == Ordering::Equal);
257    b.c0.add_assign(&Fq::one());
258    assert!(a.cmp(&b) == Ordering::Less);
259    a.c0.add_assign(&Fq::one());
260    assert!(a.cmp(&b) == Ordering::Equal);
261    b.c1.add_assign(&Fq::one());
262    assert!(a.cmp(&b) == Ordering::Less);
263    a.c0.add_assign(&Fq::one());
264    assert!(a.cmp(&b) == Ordering::Less);
265    a.c1.add_assign(&Fq::one());
266    assert!(a.cmp(&b) == Ordering::Greater);
267    b.c0.add_assign(&Fq::one());
268    assert!(a.cmp(&b) == Ordering::Equal);
269}
270
271#[test]
272fn test_fq2_basics() {
273    assert_eq!(
274        Fq2 {
275            c0: Fq::zero(),
276            c1: Fq::zero(),
277        },
278        Fq2::zero()
279    );
280    assert_eq!(
281        Fq2 {
282            c0: Fq::one(),
283            c1: Fq::zero(),
284        },
285        Fq2::one()
286    );
287    assert!(Fq2::zero().is_zero());
288    assert!(!Fq2::one().is_zero());
289    assert!(!Fq2 {
290        c0: Fq::zero(),
291        c1: Fq::one(),
292    }
293    .is_zero());
294}
295
296#[test]
297fn test_fq2_squaring() {
298    use super::fq::FqRepr;
299    use ff::PrimeField;
300
301    let mut a = Fq2 {
302        c0: Fq::one(),
303        c1: Fq::one(),
304    }; // u + 1
305    a.square();
306    assert_eq!(
307        a,
308        Fq2 {
309            c0: Fq::zero(),
310            c1: Fq::from_repr(FqRepr::from(2)).unwrap(),
311        }
312    ); // 2u
313
314    let mut a = Fq2 {
315        c0: Fq::zero(),
316        c1: Fq::one(),
317    }; // u
318    a.square();
319    assert_eq!(a, {
320        let mut neg1 = Fq::one();
321        neg1.negate();
322        Fq2 {
323            c0: neg1,
324            c1: Fq::zero(),
325        }
326    }); // -1
327
328    let mut a = Fq2 {
329        c0: Fq::from_repr(FqRepr([
330            0x9c2c6309bbf8b598,
331            0x4eef5c946536f602,
332            0x90e34aab6fb6a6bd,
333            0xf7f295a94e58ae7c,
334            0x41b76dcc1c3fbe5e,
335            0x7080c5fa1d8e042,
336        ]))
337        .unwrap(),
338        c1: Fq::from_repr(FqRepr([
339            0x38f473b3c870a4ab,
340            0x6ad3291177c8c7e5,
341            0xdac5a4c911a4353e,
342            0xbfb99020604137a0,
343            0xfc58a7b7be815407,
344            0x10d1615e75250a21,
345        ]))
346        .unwrap(),
347    };
348    a.square();
349    assert_eq!(
350        a,
351        Fq2 {
352            c0: Fq::from_repr(FqRepr([
353                0xf262c28c538bcf68,
354                0xb9f2a66eae1073ba,
355                0xdc46ab8fad67ae0,
356                0xcb674157618da176,
357                0x4cf17b5893c3d327,
358                0x7eac81369c43361
359            ]))
360            .unwrap(),
361            c1: Fq::from_repr(FqRepr([
362                0xc1579cf58e980cf8,
363                0xa23eb7e12dd54d98,
364                0xe75138bce4cec7aa,
365                0x38d0d7275a9689e1,
366                0x739c983042779a65,
367                0x1542a61c8a8db994
368            ]))
369            .unwrap(),
370        }
371    );
372}
373
374#[test]
375fn test_fq2_mul() {
376    use super::fq::FqRepr;
377    use ff::PrimeField;
378
379    let mut a = Fq2 {
380        c0: Fq::from_repr(FqRepr([
381            0x85c9f989e1461f03,
382            0xa2e33c333449a1d6,
383            0x41e461154a7354a3,
384            0x9ee53e7e84d7532e,
385            0x1c202d8ed97afb45,
386            0x51d3f9253e2516f,
387        ]))
388        .unwrap(),
389        c1: Fq::from_repr(FqRepr([
390            0xa7348a8b511aedcf,
391            0x143c215d8176b319,
392            0x4cc48081c09b8903,
393            0x9533e4a9a5158be,
394            0x7a5e1ecb676d65f9,
395            0x180c3ee46656b008,
396        ]))
397        .unwrap(),
398    };
399    a.mul_assign(&Fq2 {
400        c0: Fq::from_repr(FqRepr([
401            0xe21f9169805f537e,
402            0xfc87e62e179c285d,
403            0x27ece175be07a531,
404            0xcd460f9f0c23e430,
405            0x6c9110292bfa409,
406            0x2c93a72eb8af83e,
407        ]))
408        .unwrap(),
409        c1: Fq::from_repr(FqRepr([
410            0x4b1c3f936d8992d4,
411            0x1d2a72916dba4c8a,
412            0x8871c508658d1e5f,
413            0x57a06d3135a752ae,
414            0x634cd3c6c565096d,
415            0x19e17334d4e93558,
416        ]))
417        .unwrap(),
418    });
419    assert_eq!(
420        a,
421        Fq2 {
422            c0: Fq::from_repr(FqRepr([
423                0x95b5127e6360c7e4,
424                0xde29c31a19a6937e,
425                0xf61a96dacf5a39bc,
426                0x5511fe4d84ee5f78,
427                0x5310a202d92f9963,
428                0x1751afbe166e5399
429            ]))
430            .unwrap(),
431            c1: Fq::from_repr(FqRepr([
432                0x84af0e1bd630117a,
433                0x6c63cd4da2c2aa7,
434                0x5ba6e5430e883d40,
435                0xc975106579c275ee,
436                0x33a9ac82ce4c5083,
437                0x1ef1a36c201589d
438            ]))
439            .unwrap(),
440        }
441    );
442}
443
444#[test]
445fn test_fq2_inverse() {
446    use super::fq::FqRepr;
447    use ff::PrimeField;
448
449    assert!(Fq2::zero().inverse().is_none());
450
451    let a = Fq2 {
452        c0: Fq::from_repr(FqRepr([
453            0x85c9f989e1461f03,
454            0xa2e33c333449a1d6,
455            0x41e461154a7354a3,
456            0x9ee53e7e84d7532e,
457            0x1c202d8ed97afb45,
458            0x51d3f9253e2516f,
459        ]))
460        .unwrap(),
461        c1: Fq::from_repr(FqRepr([
462            0xa7348a8b511aedcf,
463            0x143c215d8176b319,
464            0x4cc48081c09b8903,
465            0x9533e4a9a5158be,
466            0x7a5e1ecb676d65f9,
467            0x180c3ee46656b008,
468        ]))
469        .unwrap(),
470    };
471    let a = a.inverse().unwrap();
472    assert_eq!(
473        a,
474        Fq2 {
475            c0: Fq::from_repr(FqRepr([
476                0x70300f9bcb9e594,
477                0xe5ecda5fdafddbb2,
478                0x64bef617d2915a8f,
479                0xdfba703293941c30,
480                0xa6c3d8f9586f2636,
481                0x1351ef01941b70c4
482            ]))
483            .unwrap(),
484            c1: Fq::from_repr(FqRepr([
485                0x8c39fd76a8312cb4,
486                0x15d7b6b95defbff0,
487                0x947143f89faedee9,
488                0xcbf651a0f367afb2,
489                0xdf4e54f0d3ef15a6,
490                0x103bdf241afb0019
491            ]))
492            .unwrap(),
493        }
494    );
495}
496
497#[test]
498fn test_fq2_addition() {
499    use super::fq::FqRepr;
500    use ff::PrimeField;
501
502    let mut a = Fq2 {
503        c0: Fq::from_repr(FqRepr([
504            0x2d0078036923ffc7,
505            0x11e59ea221a3b6d2,
506            0x8b1a52e0a90f59ed,
507            0xb966ce3bc2108b13,
508            0xccc649c4b9532bf3,
509            0xf8d295b2ded9dc,
510        ]))
511        .unwrap(),
512        c1: Fq::from_repr(FqRepr([
513            0x977df6efcdaee0db,
514            0x946ae52d684fa7ed,
515            0xbe203411c66fb3a5,
516            0xb3f8afc0ee248cad,
517            0x4e464dea5bcfd41e,
518            0x12d1137b8a6a837,
519        ]))
520        .unwrap(),
521    };
522    a.add_assign(&Fq2 {
523        c0: Fq::from_repr(FqRepr([
524            0x619a02d78dc70ef2,
525            0xb93adfc9119e33e8,
526            0x4bf0b99a9f0dca12,
527            0x3b88899a42a6318f,
528            0x986a4a62fa82a49d,
529            0x13ce433fa26027f5,
530        ]))
531        .unwrap(),
532        c1: Fq::from_repr(FqRepr([
533            0x66323bf80b58b9b9,
534            0xa1379b6facf6e596,
535            0x402aef1fb797e32f,
536            0x2236f55246d0d44d,
537            0x4c8c1800eb104566,
538            0x11d6e20e986c2085,
539        ]))
540        .unwrap(),
541    });
542    assert_eq!(
543        a,
544        Fq2 {
545            c0: Fq::from_repr(FqRepr([
546                0x8e9a7adaf6eb0eb9,
547                0xcb207e6b3341eaba,
548                0xd70b0c7b481d23ff,
549                0xf4ef57d604b6bca2,
550                0x65309427b3d5d090,
551                0x14c715d5553f01d2
552            ]))
553            .unwrap(),
554            c1: Fq::from_repr(FqRepr([
555                0xfdb032e7d9079a94,
556                0x35a2809d15468d83,
557                0xfe4b23317e0796d5,
558                0xd62fa51334f560fa,
559                0x9ad265eb46e01984,
560                0x1303f3465112c8bc
561            ]))
562            .unwrap(),
563        }
564    );
565}
566
567#[test]
568fn test_fq2_subtraction() {
569    use super::fq::FqRepr;
570    use ff::PrimeField;
571
572    let mut a = Fq2 {
573        c0: Fq::from_repr(FqRepr([
574            0x2d0078036923ffc7,
575            0x11e59ea221a3b6d2,
576            0x8b1a52e0a90f59ed,
577            0xb966ce3bc2108b13,
578            0xccc649c4b9532bf3,
579            0xf8d295b2ded9dc,
580        ]))
581        .unwrap(),
582        c1: Fq::from_repr(FqRepr([
583            0x977df6efcdaee0db,
584            0x946ae52d684fa7ed,
585            0xbe203411c66fb3a5,
586            0xb3f8afc0ee248cad,
587            0x4e464dea5bcfd41e,
588            0x12d1137b8a6a837,
589        ]))
590        .unwrap(),
591    };
592    a.sub_assign(&Fq2 {
593        c0: Fq::from_repr(FqRepr([
594            0x619a02d78dc70ef2,
595            0xb93adfc9119e33e8,
596            0x4bf0b99a9f0dca12,
597            0x3b88899a42a6318f,
598            0x986a4a62fa82a49d,
599            0x13ce433fa26027f5,
600        ]))
601        .unwrap(),
602        c1: Fq::from_repr(FqRepr([
603            0x66323bf80b58b9b9,
604            0xa1379b6facf6e596,
605            0x402aef1fb797e32f,
606            0x2236f55246d0d44d,
607            0x4c8c1800eb104566,
608            0x11d6e20e986c2085,
609        ]))
610        .unwrap(),
611    });
612    assert_eq!(
613        a,
614        Fq2 {
615            c0: Fq::from_repr(FqRepr([
616                0x8565752bdb5c9b80,
617                0x7756bed7c15982e9,
618                0xa65a6be700b285fe,
619                0xe255902672ef6c43,
620                0x7f77a718021c342d,
621                0x72ba14049fe9881
622            ]))
623            .unwrap(),
624            c1: Fq::from_repr(FqRepr([
625                0xeb4abaf7c255d1cd,
626                0x11df49bc6cacc256,
627                0xe52617930588c69a,
628                0xf63905f39ad8cb1f,
629                0x4cd5dd9fb40b3b8f,
630                0x957411359ba6e4c
631            ]))
632            .unwrap(),
633        }
634    );
635}
636
637#[test]
638fn test_fq2_negation() {
639    use super::fq::FqRepr;
640    use ff::PrimeField;
641
642    let mut a = Fq2 {
643        c0: Fq::from_repr(FqRepr([
644            0x2d0078036923ffc7,
645            0x11e59ea221a3b6d2,
646            0x8b1a52e0a90f59ed,
647            0xb966ce3bc2108b13,
648            0xccc649c4b9532bf3,
649            0xf8d295b2ded9dc,
650        ]))
651        .unwrap(),
652        c1: Fq::from_repr(FqRepr([
653            0x977df6efcdaee0db,
654            0x946ae52d684fa7ed,
655            0xbe203411c66fb3a5,
656            0xb3f8afc0ee248cad,
657            0x4e464dea5bcfd41e,
658            0x12d1137b8a6a837,
659        ]))
660        .unwrap(),
661    };
662    a.negate();
663    assert_eq!(
664        a,
665        Fq2 {
666            c0: Fq::from_repr(FqRepr([
667                0x8cfe87fc96dbaae4,
668                0xcc6615c8fb0492d,
669                0xdc167fc04da19c37,
670                0xab107d49317487ab,
671                0x7e555df189f880e3,
672                0x19083f5486a10cbd
673            ]))
674            .unwrap(),
675            c1: Fq::from_repr(FqRepr([
676                0x228109103250c9d0,
677                0x8a411ad149045812,
678                0xa9109e8f3041427e,
679                0xb07e9bc405608611,
680                0xfcd559cbe77bd8b8,
681                0x18d400b280d93e62
682            ]))
683            .unwrap(),
684        }
685    );
686}
687
688#[test]
689fn test_fq2_doubling() {
690    use super::fq::FqRepr;
691    use ff::PrimeField;
692
693    let mut a = Fq2 {
694        c0: Fq::from_repr(FqRepr([
695            0x2d0078036923ffc7,
696            0x11e59ea221a3b6d2,
697            0x8b1a52e0a90f59ed,
698            0xb966ce3bc2108b13,
699            0xccc649c4b9532bf3,
700            0xf8d295b2ded9dc,
701        ]))
702        .unwrap(),
703        c1: Fq::from_repr(FqRepr([
704            0x977df6efcdaee0db,
705            0x946ae52d684fa7ed,
706            0xbe203411c66fb3a5,
707            0xb3f8afc0ee248cad,
708            0x4e464dea5bcfd41e,
709            0x12d1137b8a6a837,
710        ]))
711        .unwrap(),
712    };
713    a.double();
714    assert_eq!(
715        a,
716        Fq2 {
717            c0: Fq::from_repr(FqRepr([
718                0x5a00f006d247ff8e,
719                0x23cb3d4443476da4,
720                0x1634a5c1521eb3da,
721                0x72cd9c7784211627,
722                0x998c938972a657e7,
723                0x1f1a52b65bdb3b9
724            ]))
725            .unwrap(),
726            c1: Fq::from_repr(FqRepr([
727                0x2efbeddf9b5dc1b6,
728                0x28d5ca5ad09f4fdb,
729                0x7c4068238cdf674b,
730                0x67f15f81dc49195b,
731                0x9c8c9bd4b79fa83d,
732                0x25a226f714d506e
733            ]))
734            .unwrap(),
735        }
736    );
737}
738
739#[test]
740fn test_fq2_frobenius_map() {
741    use super::fq::FqRepr;
742    use ff::PrimeField;
743
744    let mut a = Fq2 {
745        c0: Fq::from_repr(FqRepr([
746            0x2d0078036923ffc7,
747            0x11e59ea221a3b6d2,
748            0x8b1a52e0a90f59ed,
749            0xb966ce3bc2108b13,
750            0xccc649c4b9532bf3,
751            0xf8d295b2ded9dc,
752        ]))
753        .unwrap(),
754        c1: Fq::from_repr(FqRepr([
755            0x977df6efcdaee0db,
756            0x946ae52d684fa7ed,
757            0xbe203411c66fb3a5,
758            0xb3f8afc0ee248cad,
759            0x4e464dea5bcfd41e,
760            0x12d1137b8a6a837,
761        ]))
762        .unwrap(),
763    };
764    a.frobenius_map(0);
765    assert_eq!(
766        a,
767        Fq2 {
768            c0: Fq::from_repr(FqRepr([
769                0x2d0078036923ffc7,
770                0x11e59ea221a3b6d2,
771                0x8b1a52e0a90f59ed,
772                0xb966ce3bc2108b13,
773                0xccc649c4b9532bf3,
774                0xf8d295b2ded9dc
775            ]))
776            .unwrap(),
777            c1: Fq::from_repr(FqRepr([
778                0x977df6efcdaee0db,
779                0x946ae52d684fa7ed,
780                0xbe203411c66fb3a5,
781                0xb3f8afc0ee248cad,
782                0x4e464dea5bcfd41e,
783                0x12d1137b8a6a837
784            ]))
785            .unwrap(),
786        }
787    );
788    a.frobenius_map(1);
789    assert_eq!(
790        a,
791        Fq2 {
792            c0: Fq::from_repr(FqRepr([
793                0x2d0078036923ffc7,
794                0x11e59ea221a3b6d2,
795                0x8b1a52e0a90f59ed,
796                0xb966ce3bc2108b13,
797                0xccc649c4b9532bf3,
798                0xf8d295b2ded9dc
799            ]))
800            .unwrap(),
801            c1: Fq::from_repr(FqRepr([
802                0x228109103250c9d0,
803                0x8a411ad149045812,
804                0xa9109e8f3041427e,
805                0xb07e9bc405608611,
806                0xfcd559cbe77bd8b8,
807                0x18d400b280d93e62
808            ]))
809            .unwrap(),
810        }
811    );
812    a.frobenius_map(1);
813    assert_eq!(
814        a,
815        Fq2 {
816            c0: Fq::from_repr(FqRepr([
817                0x2d0078036923ffc7,
818                0x11e59ea221a3b6d2,
819                0x8b1a52e0a90f59ed,
820                0xb966ce3bc2108b13,
821                0xccc649c4b9532bf3,
822                0xf8d295b2ded9dc
823            ]))
824            .unwrap(),
825            c1: Fq::from_repr(FqRepr([
826                0x977df6efcdaee0db,
827                0x946ae52d684fa7ed,
828                0xbe203411c66fb3a5,
829                0xb3f8afc0ee248cad,
830                0x4e464dea5bcfd41e,
831                0x12d1137b8a6a837
832            ]))
833            .unwrap(),
834        }
835    );
836    a.frobenius_map(2);
837    assert_eq!(
838        a,
839        Fq2 {
840            c0: Fq::from_repr(FqRepr([
841                0x2d0078036923ffc7,
842                0x11e59ea221a3b6d2,
843                0x8b1a52e0a90f59ed,
844                0xb966ce3bc2108b13,
845                0xccc649c4b9532bf3,
846                0xf8d295b2ded9dc
847            ]))
848            .unwrap(),
849            c1: Fq::from_repr(FqRepr([
850                0x977df6efcdaee0db,
851                0x946ae52d684fa7ed,
852                0xbe203411c66fb3a5,
853                0xb3f8afc0ee248cad,
854                0x4e464dea5bcfd41e,
855                0x12d1137b8a6a837
856            ]))
857            .unwrap(),
858        }
859    );
860}
861
862#[test]
863fn test_fq2_sqrt() {
864    use super::fq::FqRepr;
865    use ff::PrimeField;
866
867    assert_eq!(
868        Fq2 {
869            c0: Fq::from_repr(FqRepr([
870                0x476b4c309720e227,
871                0x34c2d04faffdab6,
872                0xa57e6fc1bab51fd9,
873                0xdb4a116b5bf74aa1,
874                0x1e58b2159dfe10e2,
875                0x7ca7da1f13606ac
876            ]))
877            .unwrap(),
878            c1: Fq::from_repr(FqRepr([
879                0xfa8de88b7516d2c3,
880                0x371a75ed14f41629,
881                0x4cec2dca577a3eb6,
882                0x212611bca4e99121,
883                0x8ee5394d77afb3d,
884                0xec92336650e49d5
885            ]))
886            .unwrap(),
887        }
888        .sqrt()
889        .unwrap(),
890        Fq2 {
891            c0: Fq::from_repr(FqRepr([
892                0x40b299b2704258c5,
893                0x6ef7de92e8c68b63,
894                0x6d2ddbe552203e82,
895                0x8d7f1f723d02c1d3,
896                0x881b3e01b611c070,
897                0x10f6963bbad2ebc5
898            ]))
899            .unwrap(),
900            c1: Fq::from_repr(FqRepr([
901                0xc099534fc209e752,
902                0x7670594665676447,
903                0x28a20faed211efe7,
904                0x6b852aeaf2afcb1b,
905                0xa4c93b08105d71a9,
906                0x8d7cfff94216330
907            ]))
908            .unwrap(),
909        }
910    );
911
912    assert_eq!(
913        Fq2 {
914            c0: Fq::from_repr(FqRepr([
915                0xb9f78429d1517a6b,
916                0x1eabfffeb153ffff,
917                0x6730d2a0f6b0f624,
918                0x64774b84f38512bf,
919                0x4b1ba7b6434bacd7,
920                0x1a0111ea397fe69a
921            ]))
922            .unwrap(),
923            c1: Fq::zero(),
924        }
925        .sqrt()
926        .unwrap(),
927        Fq2 {
928            c0: Fq::zero(),
929            c1: Fq::from_repr(FqRepr([
930                0xb9fefffffd4357a3,
931                0x1eabfffeb153ffff,
932                0x6730d2a0f6b0f624,
933                0x64774b84f38512bf,
934                0x4b1ba7b6434bacd7,
935                0x1a0111ea397fe69a
936            ]))
937            .unwrap(),
938        }
939    );
940}
941
942#[test]
943fn test_fq2_legendre() {
944    use ff::LegendreSymbol::*;
945
946    assert_eq!(Zero, Fq2::zero().legendre());
947    // i^2 = -1
948    let mut m1 = Fq2::one();
949    m1.negate();
950    assert_eq!(QuadraticResidue, m1.legendre());
951    m1.mul_by_nonresidue();
952    assert_eq!(QuadraticNonResidue, m1.legendre());
953}
954
955#[cfg(test)]
956use rand_core::SeedableRng;
957//use rand::{SeedableRng, XorShiftRng};
958
959#[test]
960fn test_fq2_mul_nonresidue() {
961    let mut rng = rand_xorshift::XorShiftRng::from_seed([
962        0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06, 0xbc,
963        0xe5,
964    ]);
965    let nqr = Fq2 {
966        c0: Fq::one(),
967        c1: Fq::one(),
968    };
969
970    for _ in 0..1000 {
971        let mut a = Fq2::random(&mut rng);
972        let mut b = a;
973        a.mul_by_nonresidue();
974        b.mul_assign(&nqr);
975
976        assert_eq!(a, b);
977    }
978}
979
980#[test]
981fn fq2_field_tests() {
982    use ff::PrimeField;
983
984    ::tests::field::random_field_tests::<Fq2>();
985    ::tests::field::random_sqrt_tests::<Fq2>();
986    ::tests::field::random_frobenius_tests::<Fq2, _>(super::fq::Fq::char(), 13);
987}
988
989#[test]
990fn test_fq2_hash_to_field_xof_shake128() {
991    use super::fq::FqRepr;
992    use ff::PrimeField;
993    use hash_to_field::{hash_to_field, ExpandMsgXof};
994    use sha3::Shake128;
995
996    let u = hash_to_field::<Fq2, ExpandMsgXof<Shake128>>(b"hello world", b"asdfqwerzxcv", 5);
997    let c0 = FqRepr([
998        0x83b44bd21d9176f9u64,
999        0x500e57bed444b495u64,
1000        0x99e7981c634e8dau64,
1001        0x534d01b15f9dfc5bu64,
1002        0xc28fdd7ba924fc24u64,
1003        0x149b57b053aba2f1u64,
1004    ]);
1005    let c1 = FqRepr([
1006        0x52a9e519f8d670u64,
1007        0x80836391c697e0f3u64,
1008        0xdef4327ec50c9e2fu64,
1009        0xfe1bd6918af282a6u64,
1010        0xdca9b63feb10ef5au64,
1011        0x2fe35c636602fc3u64,
1012    ]);
1013    let expect = Fq2 {
1014        c0: Fq::from_repr(c0).unwrap(),
1015        c1: Fq::from_repr(c1).unwrap(),
1016    };
1017    assert_eq!(u[0], expect);
1018    let c0 = FqRepr([
1019        0xc67cf203a4d5a146u64,
1020        0x71aa5c4048396b4u64,
1021        0x161a0f70a89fe76du64,
1022        0x480fc40ff5eb8cbau64,
1023        0xd137a2af45f88a31u64,
1024        0x18feaaf129abfb5cu64,
1025    ]);
1026    let c1 = FqRepr([
1027        0x5d269239a15f0beeu64,
1028        0x16515524243a806du64,
1029        0xaaf873bc4664cdf2u64,
1030        0xf31ca30fdde1a7dau64,
1031        0xbbc54a41017a7cd6u64,
1032        0x4774c213e3a6a7du64,
1033    ]);
1034    let expect = Fq2 {
1035        c0: Fq::from_repr(c0).unwrap(),
1036        c1: Fq::from_repr(c1).unwrap(),
1037    };
1038    assert_eq!(u[1], expect);
1039    let c0 = FqRepr([
1040        0xab6e3121ad020c5cu64,
1041        0x914a2813c62a0174u64,
1042        0x191f045dda39ef40u64,
1043        0x703fb6dd5708c2b7u64,
1044        0xf3b7e2d9c65aeb48u64,
1045        0x9a18b8b5a11e2beu64,
1046    ]);
1047    let c1 = FqRepr([
1048        0x99e3b69a05559fd3u64,
1049        0x5d634f8ea80270b1u64,
1050        0xcddc741e008d6f48u64,
1051        0xdc7cef61f00c12b1u64,
1052        0xc882bc3f8fa43794u64,
1053        0xdfe8ec63832446cu64,
1054    ]);
1055    let expect = Fq2 {
1056        c0: Fq::from_repr(c0).unwrap(),
1057        c1: Fq::from_repr(c1).unwrap(),
1058    };
1059    assert_eq!(u[2], expect);
1060    let c0 = FqRepr([
1061        0xbac4c5dd6b1e6cffu64,
1062        0x22a18330d743265eu64,
1063        0xd6e76b24b45ce456u64,
1064        0x5ddbe250869b02d9u64,
1065        0x70ba43cb49fa664cu64,
1066        0x11d12bfd064a9c07u64,
1067    ]);
1068    let c1 = FqRepr([
1069        0x46ab0b9ca2a026a8u64,
1070        0xe7c542debb3e8863u64,
1071        0x5beb58e25a0fba93u64,
1072        0xaac9366a1e124881u64,
1073        0xa17db74df34c6629u64,
1074        0x17d114628ff83e09u64,
1075    ]);
1076    let expect = Fq2 {
1077        c0: Fq::from_repr(c0).unwrap(),
1078        c1: Fq::from_repr(c1).unwrap(),
1079    };
1080    assert_eq!(u[3], expect);
1081    let c0 = FqRepr([
1082        0x4a02b77af5981d89u64,
1083        0x4691dce449e5475du64,
1084        0xf77a0e8e3982aaa6u64,
1085        0x2845134c4ca09dfbu64,
1086        0x28eb49d2df16aca4u64,
1087        0x117cfe69c07adc28u64,
1088    ]);
1089    let c1 = FqRepr([
1090        0x3f20eb109b30d170u64,
1091        0xf9db62febb5f6430u64,
1092        0xa8f532675eabfe7au64,
1093        0x553b99a8f101d00bu64,
1094        0x6707e210f918ccfbu64,
1095        0x17b968ebb357f7efu64,
1096    ]);
1097    let expect = Fq2 {
1098        c0: Fq::from_repr(c0).unwrap(),
1099        c1: Fq::from_repr(c1).unwrap(),
1100    };
1101    assert_eq!(u[4], expect);
1102}
1103
1104#[test]
1105fn test_fq2_hash_to_field_xmd_sha256() {
1106    use super::fq::FqRepr;
1107    use ff::PrimeField;
1108    use hash_to_field::{hash_to_field, ExpandMsgXmd};
1109    use sha2::Sha256;
1110
1111    let u = hash_to_field::<Fq2, ExpandMsgXmd<Sha256>>(b"hello world", b"asdfqwerzxcv", 5);
1112    let c0 = FqRepr([
1113        0x8013b8de1c730ccdu64,
1114        0xd19df445418e9f11u64,
1115        0xfae296c27ed04aceu64,
1116        0x1615a7c2e5dc8be4u64,
1117        0x69bc8b813ad8a2eeu64,
1118        0x621a916a3dd4ce7u64,
1119    ]);
1120    let c1 = FqRepr([
1121        0x2f21543bb7e13c15u64,
1122        0x79a2713c2a7471fbu64,
1123        0xccf4be18d3320ad2u64,
1124        0x63ff7b3318ee22a6u64,
1125        0x3a966c650ea0de7au64,
1126        0x6e92928bd785218u64,
1127    ]);
1128    let expect = Fq2 {
1129        c0: Fq::from_repr(c0).unwrap(),
1130        c1: Fq::from_repr(c1).unwrap(),
1131    };
1132    assert_eq!(u[0], expect);
1133    let c0 = FqRepr([
1134        0x4af5da7a38284cb9u64,
1135        0x49bdeb3e2d8c55a1u64,
1136        0x3cd8d0502207ae3du64,
1137        0x78b015530955cd51u64,
1138        0x1fdfd411fa9df1acu64,
1139        0x12b47d2dbfb8b7adu64,
1140    ]);
1141    let c1 = FqRepr([
1142        0xf0610ab9d30ace85u64,
1143        0x3cba524826095c26u64,
1144        0x2cca88714bd91543u64,
1145        0xb7809e759c9d0b96u64,
1146        0xb14c45e3c57e384u64,
1147        0x97bd219ee74f234u64,
1148    ]);
1149    let expect = Fq2 {
1150        c0: Fq::from_repr(c0).unwrap(),
1151        c1: Fq::from_repr(c1).unwrap(),
1152    };
1153    assert_eq!(u[1], expect);
1154    let c0 = FqRepr([
1155        0x1c9e390ec0ccfbd7u64,
1156        0xf9df7e6f2907332au64,
1157        0x135b4bcdbfc9b7bbu64,
1158        0x3aa60e647cc96fc8u64,
1159        0xa4c312e21e72f56cu64,
1160        0x145307a104618b9cu64,
1161    ]);
1162    let c1 = FqRepr([
1163        0x71e6f415f440a8ffu64,
1164        0x2e9636615390a691u64,
1165        0x3777508fadfae164u64,
1166        0x5bacbcfb0ee19ce3u64,
1167        0x203c81bd6ed27200u64,
1168        0xbc7bf3ad0854416u64,
1169    ]);
1170    let expect = Fq2 {
1171        c0: Fq::from_repr(c0).unwrap(),
1172        c1: Fq::from_repr(c1).unwrap(),
1173    };
1174    assert_eq!(u[2], expect);
1175    let c0 = FqRepr([
1176        0x4085662818b318fcu64,
1177        0xee1d6563dfc486b7u64,
1178        0x3f9294a50d8c8015u64,
1179        0xd4cbb000d6289d89u64,
1180        0x4fa081a472f02ddbu64,
1181        0x13f591c4a737afc2u64,
1182    ]);
1183    let c1 = FqRepr([
1184        0xb109a8ddbda9cdf7u64,
1185        0x4b37831e7daab6f2u64,
1186        0xec6dd9fe4bafa1f0u64,
1187        0x43d5ac76277b7584u64,
1188        0x17f548d1cd113567u64,
1189        0x12a35bed47708d4eu64,
1190    ]);
1191    let expect = Fq2 {
1192        c0: Fq::from_repr(c0).unwrap(),
1193        c1: Fq::from_repr(c1).unwrap(),
1194    };
1195    assert_eq!(u[3], expect);
1196    let c0 = FqRepr([
1197        0xa9c3b37df4203321u64,
1198        0x63a17215811a2de1u64,
1199        0xec72143f15671003u64,
1200        0x9f1e7c13ce8af1b9u64,
1201        0x1c164a2698a93988u64,
1202        0x160a417e29e70d97u64,
1203    ]);
1204    let c1 = FqRepr([
1205        0x3cd586733e0bab94u64,
1206        0xa335c8696e6af945u64,
1207        0xf9ab253161bc54e3u64,
1208        0xa53863e80553ccb8u64,
1209        0x43dca822001a0642u64,
1210        0x10b0a85bd661e512u64,
1211    ]);
1212    let expect = Fq2 {
1213        c0: Fq::from_repr(c0).unwrap(),
1214        c1: Fq::from_repr(c1).unwrap(),
1215    };
1216    assert_eq!(u[4], expect);
1217}
1218
1219#[test]
1220fn test_fq2_sgn0() {
1221    use super::fq::P_M1_OVER2;
1222
1223    assert_eq!(Fq2::zero().sgn0(), Sgn0Result::NonNegative);
1224    assert_eq!(Fq2::one().sgn0(), Sgn0Result::NonNegative);
1225    assert_eq!(
1226        Fq2 {
1227            c0: P_M1_OVER2,
1228            c1: Fq::zero()
1229        }
1230        .sgn0(),
1231        Sgn0Result::NonNegative
1232    );
1233    assert_eq!(
1234        Fq2 {
1235            c0: P_M1_OVER2,
1236            c1: Fq::one()
1237        }
1238        .sgn0(),
1239        Sgn0Result::NonNegative
1240    );
1241
1242    let p_p1_over2 = {
1243        let mut tmp = P_M1_OVER2;
1244        tmp.add_assign(&Fq::one());
1245        tmp
1246    };
1247    assert_eq!(
1248        Fq2 {
1249            c0: p_p1_over2,
1250            c1: Fq::zero()
1251        }
1252        .sgn0(),
1253        Sgn0Result::Negative
1254    );
1255    assert_eq!(
1256        Fq2 {
1257            c0: p_p1_over2,
1258            c1: Fq::one()
1259        }
1260        .sgn0(),
1261        Sgn0Result::NonNegative
1262    );
1263
1264    let m1 = {
1265        let mut tmp = Fq::one();
1266        tmp.negate();
1267        tmp
1268    };
1269    assert_eq!(
1270        Fq2 {
1271            c0: P_M1_OVER2,
1272            c1: m1
1273        }
1274        .sgn0(),
1275        Sgn0Result::Negative
1276    );
1277    assert_eq!(
1278        Fq2 {
1279            c0: p_p1_over2,
1280            c1: m1
1281        }
1282        .sgn0(),
1283        Sgn0Result::Negative
1284    );
1285    assert_eq!(
1286        Fq2 {
1287            c0: Fq::zero(),
1288            c1: m1
1289        }
1290        .sgn0(),
1291        Sgn0Result::Negative
1292    );
1293    assert_eq!(
1294        Fq2 {
1295            c0: P_M1_OVER2,
1296            c1: p_p1_over2
1297        }
1298        .sgn0(),
1299        Sgn0Result::Negative
1300    );
1301    assert_eq!(
1302        Fq2 {
1303            c0: p_p1_over2,
1304            c1: P_M1_OVER2
1305        }
1306        .sgn0(),
1307        Sgn0Result::NonNegative
1308    );
1309}
pairing_plus/bls12_381/fq2.rs

pairing_plus/bls12_381/
fq2.rs
