pairing_plus/bls12_381/
fq.rs

1use super::fq2::Fq2;
2use digest::generic_array::{typenum::U64, GenericArray};
3use ff::{Field, PrimeField, PrimeFieldDecodingError, PrimeFieldRepr};
4use hash_to_field::BaseFromRO;
5use signum::{Sgn0Result, Signum0};
6use std::cmp::Ordering;
7use std::io::{Cursor, Read};
8
9// B coefficient of BLS12-381 curve, 4.
10pub const B_COEFF: Fq = Fq(FqRepr([
11    0xaa270000000cfff3,
12    0x53cc0032fc34000a,
13    0x478fe97a6b0a807f,
14    0xb1d37ebee6ba24d7,
15    0x8ec9733bbf78ab2f,
16    0x9d645513d83de7e,
17]));
18
19// The generators of G1/G2 are computed by finding the lexicographically smallest valid x coordinate,
20// and its lexicographically smallest y coordinate and multiplying it by the cofactor such that the
21// result is nonzero.
22
23// Generator of G1
24// x = 3685416753713387016781088315183077757961620795782546409894578378688607592378376318836054947676345821548104185464507
25// y = 1339506544944476473020471379941921221584933875938349620426543736416511423956333506472724655353366534992391756441569
26pub const G1_GENERATOR_X: Fq = Fq(FqRepr([
27    0x5cb38790fd530c16,
28    0x7817fc679976fff5,
29    0x154f95c7143ba1c1,
30    0xf0ae6acdf3d0e747,
31    0xedce6ecc21dbf440,
32    0x120177419e0bfb75,
33]));
34pub const G1_GENERATOR_Y: Fq = Fq(FqRepr([
35    0xbaac93d50ce72271,
36    0x8c22631a7918fd8e,
37    0xdd595f13570725ce,
38    0x51ac582950405194,
39    0xe1c8c3fad0059c0,
40    0xbbc3efc5008a26a,
41]));
42
43// Generator of G2
44// x = 3059144344244213709971259814753781636986470325476647558659373206291635324768958432433509563104347017837885763365758*u + 352701069587466618187139116011060144890029952792775240219908644239793785735715026873347600343865175952761926303160
45// y = 927553665492332455747201965776037880757740193453592970025027978793976877002675564980949289727957565575433344219582*u + 1985150602287291935568054521177171638300868978215655730859378665066344726373823718423869104263333984641494340347905
46pub const G2_GENERATOR_X_C0: Fq = Fq(FqRepr([
47    0xf5f28fa202940a10,
48    0xb3f5fb2687b4961a,
49    0xa1a893b53e2ae580,
50    0x9894999d1a3caee9,
51    0x6f67b7631863366b,
52    0x58191924350bcd7,
53]));
54pub const G2_GENERATOR_X_C1: Fq = Fq(FqRepr([
55    0xa5a9c0759e23f606,
56    0xaaa0c59dbccd60c3,
57    0x3bb17e18e2867806,
58    0x1b1ab6cc8541b367,
59    0xc2b6ed0ef2158547,
60    0x11922a097360edf3,
61]));
62pub const G2_GENERATOR_Y_C0: Fq = Fq(FqRepr([
63    0x4c730af860494c4a,
64    0x597cfa1f5e369c5a,
65    0xe7e6856caa0a635a,
66    0xbbefb5e96e0d495f,
67    0x7d3a975f0ef25a2,
68    0x83fd8e7e80dae5,
69]));
70pub const G2_GENERATOR_Y_C1: Fq = Fq(FqRepr([
71    0xadc0fc92df64b05d,
72    0x18aa270a2b1461dc,
73    0x86adac6a3be4eba0,
74    0x79495c4ec93da33a,
75    0xe7175850a43ccaed,
76    0xb2bc2a163de1bf2,
77]));
78
79// Coefficients for the Frobenius automorphism.
80pub const FROBENIUS_COEFF_FQ2_C1: [Fq; 2] = [
81    // Fq(-1)**(((q^0) - 1) / 2)
82    Fq(FqRepr([
83        0x760900000002fffd,
84        0xebf4000bc40c0002,
85        0x5f48985753c758ba,
86        0x77ce585370525745,
87        0x5c071a97a256ec6d,
88        0x15f65ec3fa80e493,
89    ])),
90    // Fq(-1)**(((q^1) - 1) / 2)
91    Fq(FqRepr([
92        0x43f5fffffffcaaae,
93        0x32b7fff2ed47fffd,
94        0x7e83a49a2e99d69,
95        0xeca8f3318332bb7a,
96        0xef148d1ea0f4c069,
97        0x40ab3263eff0206,
98    ])),
99];
100
101pub const FROBENIUS_COEFF_FQ6_C1: [Fq2; 6] = [
102    // Fq2(u + 1)**(((q^0) - 1) / 3)
103    Fq2 {
104        c0: Fq(FqRepr([
105            0x760900000002fffd,
106            0xebf4000bc40c0002,
107            0x5f48985753c758ba,
108            0x77ce585370525745,
109            0x5c071a97a256ec6d,
110            0x15f65ec3fa80e493,
111        ])),
112        c1: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
113    },
114    // Fq2(u + 1)**(((q^1) - 1) / 3)
115    Fq2 {
116        c0: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
117        c1: Fq(FqRepr([
118            0xcd03c9e48671f071,
119            0x5dab22461fcda5d2,
120            0x587042afd3851b95,
121            0x8eb60ebe01bacb9e,
122            0x3f97d6e83d050d2,
123            0x18f0206554638741,
124        ])),
125    },
126    // Fq2(u + 1)**(((q^2) - 1) / 3)
127    Fq2 {
128        c0: Fq(FqRepr([
129            0x30f1361b798a64e8,
130            0xf3b8ddab7ece5a2a,
131            0x16a8ca3ac61577f7,
132            0xc26a2ff874fd029b,
133            0x3636b76660701c6e,
134            0x51ba4ab241b6160,
135        ])),
136        c1: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
137    },
138    // Fq2(u + 1)**(((q^3) - 1) / 3)
139    Fq2 {
140        c0: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
141        c1: Fq(FqRepr([
142            0x760900000002fffd,
143            0xebf4000bc40c0002,
144            0x5f48985753c758ba,
145            0x77ce585370525745,
146            0x5c071a97a256ec6d,
147            0x15f65ec3fa80e493,
148        ])),
149    },
150    // Fq2(u + 1)**(((q^4) - 1) / 3)
151    Fq2 {
152        c0: Fq(FqRepr([
153            0xcd03c9e48671f071,
154            0x5dab22461fcda5d2,
155            0x587042afd3851b95,
156            0x8eb60ebe01bacb9e,
157            0x3f97d6e83d050d2,
158            0x18f0206554638741,
159        ])),
160        c1: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
161    },
162    // Fq2(u + 1)**(((q^5) - 1) / 3)
163    Fq2 {
164        c0: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
165        c1: Fq(FqRepr([
166            0x30f1361b798a64e8,
167            0xf3b8ddab7ece5a2a,
168            0x16a8ca3ac61577f7,
169            0xc26a2ff874fd029b,
170            0x3636b76660701c6e,
171            0x51ba4ab241b6160,
172        ])),
173    },
174];
175
176pub const FROBENIUS_COEFF_FQ6_C2: [Fq2; 6] = [
177    // Fq2(u + 1)**(((2q^0) - 2) / 3)
178    Fq2 {
179        c0: Fq(FqRepr([
180            0x760900000002fffd,
181            0xebf4000bc40c0002,
182            0x5f48985753c758ba,
183            0x77ce585370525745,
184            0x5c071a97a256ec6d,
185            0x15f65ec3fa80e493,
186        ])),
187        c1: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
188    },
189    // Fq2(u + 1)**(((2q^1) - 2) / 3)
190    Fq2 {
191        c0: Fq(FqRepr([
192            0x890dc9e4867545c3,
193            0x2af322533285a5d5,
194            0x50880866309b7e2c,
195            0xa20d1b8c7e881024,
196            0x14e4f04fe2db9068,
197            0x14e56d3f1564853a,
198        ])),
199        c1: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
200    },
201    // Fq2(u + 1)**(((2q^2) - 2) / 3)
202    Fq2 {
203        c0: Fq(FqRepr([
204            0xcd03c9e48671f071,
205            0x5dab22461fcda5d2,
206            0x587042afd3851b95,
207            0x8eb60ebe01bacb9e,
208            0x3f97d6e83d050d2,
209            0x18f0206554638741,
210        ])),
211        c1: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
212    },
213    // Fq2(u + 1)**(((2q^3) - 2) / 3)
214    Fq2 {
215        c0: Fq(FqRepr([
216            0x43f5fffffffcaaae,
217            0x32b7fff2ed47fffd,
218            0x7e83a49a2e99d69,
219            0xeca8f3318332bb7a,
220            0xef148d1ea0f4c069,
221            0x40ab3263eff0206,
222        ])),
223        c1: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
224    },
225    // Fq2(u + 1)**(((2q^4) - 2) / 3)
226    Fq2 {
227        c0: Fq(FqRepr([
228            0x30f1361b798a64e8,
229            0xf3b8ddab7ece5a2a,
230            0x16a8ca3ac61577f7,
231            0xc26a2ff874fd029b,
232            0x3636b76660701c6e,
233            0x51ba4ab241b6160,
234        ])),
235        c1: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
236    },
237    // Fq2(u + 1)**(((2q^5) - 2) / 3)
238    Fq2 {
239        c0: Fq(FqRepr([
240            0xecfb361b798dba3a,
241            0xc100ddb891865a2c,
242            0xec08ff1232bda8e,
243            0xd5c13cc6f1ca4721,
244            0x47222a47bf7b5c04,
245            0x110f184e51c5f59,
246        ])),
247        c1: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
248    },
249];
250
251// non_residue^((modulus^i-1)/6) for i=0,...,11
252pub const FROBENIUS_COEFF_FQ12_C1: [Fq2; 12] = [
253    // Fq2(u + 1)**(((q^0) - 1) / 6)
254    Fq2 {
255        c0: Fq(FqRepr([
256            0x760900000002fffd,
257            0xebf4000bc40c0002,
258            0x5f48985753c758ba,
259            0x77ce585370525745,
260            0x5c071a97a256ec6d,
261            0x15f65ec3fa80e493,
262        ])),
263        c1: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
264    },
265    // Fq2(u + 1)**(((q^1) - 1) / 6)
266    Fq2 {
267        c0: Fq(FqRepr([
268            0x7089552b319d465,
269            0xc6695f92b50a8313,
270            0x97e83cccd117228f,
271            0xa35baecab2dc29ee,
272            0x1ce393ea5daace4d,
273            0x8f2220fb0fb66eb,
274        ])),
275        c1: Fq(FqRepr([
276            0xb2f66aad4ce5d646,
277            0x5842a06bfc497cec,
278            0xcf4895d42599d394,
279            0xc11b9cba40a8e8d0,
280            0x2e3813cbe5a0de89,
281            0x110eefda88847faf,
282        ])),
283    },
284    // Fq2(u + 1)**(((q^2) - 1) / 6)
285    Fq2 {
286        c0: Fq(FqRepr([
287            0xecfb361b798dba3a,
288            0xc100ddb891865a2c,
289            0xec08ff1232bda8e,
290            0xd5c13cc6f1ca4721,
291            0x47222a47bf7b5c04,
292            0x110f184e51c5f59,
293        ])),
294        c1: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
295    },
296    // Fq2(u + 1)**(((q^3) - 1) / 6)
297    Fq2 {
298        c0: Fq(FqRepr([
299            0x3e2f585da55c9ad1,
300            0x4294213d86c18183,
301            0x382844c88b623732,
302            0x92ad2afd19103e18,
303            0x1d794e4fac7cf0b9,
304            0xbd592fc7d825ec8,
305        ])),
306        c1: Fq(FqRepr([
307            0x7bcfa7a25aa30fda,
308            0xdc17dec12a927e7c,
309            0x2f088dd86b4ebef1,
310            0xd1ca2087da74d4a7,
311            0x2da2596696cebc1d,
312            0xe2b7eedbbfd87d2,
313        ])),
314    },
315    // Fq2(u + 1)**(((q^4) - 1) / 6)
316    Fq2 {
317        c0: Fq(FqRepr([
318            0x30f1361b798a64e8,
319            0xf3b8ddab7ece5a2a,
320            0x16a8ca3ac61577f7,
321            0xc26a2ff874fd029b,
322            0x3636b76660701c6e,
323            0x51ba4ab241b6160,
324        ])),
325        c1: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
326    },
327    // Fq2(u + 1)**(((q^5) - 1) / 6)
328    Fq2 {
329        c0: Fq(FqRepr([
330            0x3726c30af242c66c,
331            0x7c2ac1aad1b6fe70,
332            0xa04007fbba4b14a2,
333            0xef517c3266341429,
334            0x95ba654ed2226b,
335            0x2e370eccc86f7dd,
336        ])),
337        c1: Fq(FqRepr([
338            0x82d83cf50dbce43f,
339            0xa2813e53df9d018f,
340            0xc6f0caa53c65e181,
341            0x7525cf528d50fe95,
342            0x4a85ed50f4798a6b,
343            0x171da0fd6cf8eebd,
344        ])),
345    },
346    // Fq2(u + 1)**(((q^6) - 1) / 6)
347    Fq2 {
348        c0: Fq(FqRepr([
349            0x43f5fffffffcaaae,
350            0x32b7fff2ed47fffd,
351            0x7e83a49a2e99d69,
352            0xeca8f3318332bb7a,
353            0xef148d1ea0f4c069,
354            0x40ab3263eff0206,
355        ])),
356        c1: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
357    },
358    // Fq2(u + 1)**(((q^7) - 1) / 6)
359    Fq2 {
360        c0: Fq(FqRepr([
361            0xb2f66aad4ce5d646,
362            0x5842a06bfc497cec,
363            0xcf4895d42599d394,
364            0xc11b9cba40a8e8d0,
365            0x2e3813cbe5a0de89,
366            0x110eefda88847faf,
367        ])),
368        c1: Fq(FqRepr([
369            0x7089552b319d465,
370            0xc6695f92b50a8313,
371            0x97e83cccd117228f,
372            0xa35baecab2dc29ee,
373            0x1ce393ea5daace4d,
374            0x8f2220fb0fb66eb,
375        ])),
376    },
377    // Fq2(u + 1)**(((q^8) - 1) / 6)
378    Fq2 {
379        c0: Fq(FqRepr([
380            0xcd03c9e48671f071,
381            0x5dab22461fcda5d2,
382            0x587042afd3851b95,
383            0x8eb60ebe01bacb9e,
384            0x3f97d6e83d050d2,
385            0x18f0206554638741,
386        ])),
387        c1: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
388    },
389    // Fq2(u + 1)**(((q^9) - 1) / 6)
390    Fq2 {
391        c0: Fq(FqRepr([
392            0x7bcfa7a25aa30fda,
393            0xdc17dec12a927e7c,
394            0x2f088dd86b4ebef1,
395            0xd1ca2087da74d4a7,
396            0x2da2596696cebc1d,
397            0xe2b7eedbbfd87d2,
398        ])),
399        c1: Fq(FqRepr([
400            0x3e2f585da55c9ad1,
401            0x4294213d86c18183,
402            0x382844c88b623732,
403            0x92ad2afd19103e18,
404            0x1d794e4fac7cf0b9,
405            0xbd592fc7d825ec8,
406        ])),
407    },
408    // Fq2(u + 1)**(((q^10) - 1) / 6)
409    Fq2 {
410        c0: Fq(FqRepr([
411            0x890dc9e4867545c3,
412            0x2af322533285a5d5,
413            0x50880866309b7e2c,
414            0xa20d1b8c7e881024,
415            0x14e4f04fe2db9068,
416            0x14e56d3f1564853a,
417        ])),
418        c1: Fq(FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x0])),
419    },
420    // Fq2(u + 1)**(((q^11) - 1) / 6)
421    Fq2 {
422        c0: Fq(FqRepr([
423            0x82d83cf50dbce43f,
424            0xa2813e53df9d018f,
425            0xc6f0caa53c65e181,
426            0x7525cf528d50fe95,
427            0x4a85ed50f4798a6b,
428            0x171da0fd6cf8eebd,
429        ])),
430        c1: Fq(FqRepr([
431            0x3726c30af242c66c,
432            0x7c2ac1aad1b6fe70,
433            0xa04007fbba4b14a2,
434            0xef517c3266341429,
435            0x95ba654ed2226b,
436            0x2e370eccc86f7dd,
437        ])),
438    },
439];
440
441// -((2**384) mod q) mod q
442pub const NEGATIVE_ONE: Fq = Fq(FqRepr([
443    0x43f5fffffffcaaae,
444    0x32b7fff2ed47fffd,
445    0x7e83a49a2e99d69,
446    0xeca8f3318332bb7a,
447    0xef148d1ea0f4c069,
448    0x40ab3263eff0206,
449]));
450
451// p-1 / 2
452#[cfg(test)]
453pub const P_M1_OVER2: Fq = Fq(FqRepr([
454    0xa1fafffffffe5557u64,
455    0x995bfff976a3fffeu64,
456    0x03f41d24d174ceb4u64,
457    0xf6547998c1995dbdu64,
458    0x778a468f507a6034u64,
459    0x020559931f7f8103u64,
460]));
461
462#[derive(PrimeField, Zeroize)]
463#[PrimeFieldModulus = "4002409555221667393417789825735904156556882819939007885332058136124031650490837864442687629129015664037894272559787"]
464#[PrimeFieldGenerator = "2"]
465pub struct Fq(pub(super) FqRepr);
466
467/// # Safety
468pub const unsafe fn transmute(r: FqRepr) -> Fq {
469    Fq(r)
470}
471
472impl BaseFromRO for Fq {
473    type BaseLength = U64;
474
475    // ZZ note: Convert an output keying material to an Fq element
476    // the input generic array is gauranteed to have 64 bytes
477    // TODO: length checks and safeguards on the wrappers?
478    fn from_okm(okm: &GenericArray<u8, U64>) -> Fq {
479        const F_2_256: Fq = Fq(FqRepr([
480            0x75b3cd7c5ce820fu64,
481            0x3ec6ba621c3edb0bu64,
482            0x168a13d82bff6bceu64,
483            0x87663c4bf8c449d2u64,
484            0x15f34c83ddc8d830u64,
485            0xf9628b49caa2e85u64,
486        ]));
487
488        // unwraps are safe here: we only use 32 bytes at a time, which is strictly less than p
489        let mut repr = FqRepr::default();
490        repr.read_be(Cursor::new([0; 16]).chain(Cursor::new(&okm[..32])))
491            .unwrap();
492        let mut elm = Fq::from_repr(repr).unwrap();
493        elm.mul_assign(&F_2_256);
494
495        repr.read_be(Cursor::new([0; 16]).chain(Cursor::new(&okm[32..])))
496            .unwrap();
497        let elm2 = Fq::from_repr(repr).unwrap();
498        elm.add_assign(&elm2);
499        elm
500    }
501}
502
503impl Signum0 for Fq {
504    // returns the sign of a center lifted element over the integer ring
505    fn sgn0(&self) -> Sgn0Result {
506        // (group_order - 1)/2
507        const PM1DIV2: FqRepr = FqRepr([
508            0xdcff7fffffffd555u64,
509            0x0f55ffff58a9ffffu64,
510            0xb39869507b587b12u64,
511            0xb23ba5c279c2895fu64,
512            0x258dd3db21a5d66bu64,
513            0x0d0088f51cbff34du64,
514        ]);
515
516        if self.into_repr().cmp(&PM1DIV2) == Ordering::Greater {
517            Sgn0Result::Negative
518        } else {
519            Sgn0Result::NonNegative
520        }
521    }
522}
523
524#[test]
525fn test_b_coeff() {
526    assert_eq!(Fq::from_repr(FqRepr::from(4)).unwrap(), B_COEFF);
527}
528
529#[test]
530#[allow(clippy::cognitive_complexity)]
531fn test_frob_coeffs() {
532    let mut nqr = Fq::one();
533    nqr.negate();
534
535    assert_eq!(FROBENIUS_COEFF_FQ2_C1[0], Fq::one());
536    assert_eq!(
537        FROBENIUS_COEFF_FQ2_C1[1],
538        nqr.pow([
539            0xdcff7fffffffd555,
540            0xf55ffff58a9ffff,
541            0xb39869507b587b12,
542            0xb23ba5c279c2895f,
543            0x258dd3db21a5d66b,
544            0xd0088f51cbff34d
545        ])
546    );
547
548    let nqr = Fq2 {
549        c0: Fq::one(),
550        c1: Fq::one(),
551    };
552
553    assert_eq!(FROBENIUS_COEFF_FQ6_C1[0], Fq2::one());
554    assert_eq!(
555        FROBENIUS_COEFF_FQ6_C1[1],
556        nqr.pow([
557            0x9354ffffffffe38e,
558            0xa395554e5c6aaaa,
559            0xcd104635a790520c,
560            0xcc27c3d6fbd7063f,
561            0x190937e76bc3e447,
562            0x8ab05f8bdd54cde
563        ])
564    );
565    assert_eq!(
566        FROBENIUS_COEFF_FQ6_C1[2],
567        nqr.pow([
568            0xb78e0000097b2f68,
569            0xd44f23b47cbd64e3,
570            0x5cb9668120b069a9,
571            0xccea85f9bf7b3d16,
572            0xdba2c8d7adb356d,
573            0x9cd75ded75d7429,
574            0xfc65c31103284fab,
575            0xc58cb9a9b249ee24,
576            0xccf734c3118a2e9a,
577            0xa0f4304c5a256ce6,
578            0xc3f0d2f8e0ba61f8,
579            0xe167e192ebca97
580        ])
581    );
582    assert_eq!(
583        FROBENIUS_COEFF_FQ6_C1[3],
584        nqr.pow([
585            0xdbc6fcd6f35b9e06,
586            0x997dead10becd6aa,
587            0x9dbbd24c17206460,
588            0x72b97acc6057c45e,
589            0xf8e9a230bf0c628e,
590            0x647ccb1885c63a7,
591            0xce80264fc55bf6ee,
592            0x94d8d716c3939fc4,
593            0xad78f0eb77ee6ee1,
594            0xd6fe49bfe57dc5f9,
595            0x2656d6c15c63647,
596            0xdf6282f111fa903,
597            0x1bdba63e0632b4bb,
598            0x6883597bcaa505eb,
599            0xa56d4ec90c34a982,
600            0x7e4c42823bbe90b2,
601            0xf64728aa6dcb0f20,
602            0x16e57e16ef152f
603        ])
604    );
605    assert_eq!(
606        FROBENIUS_COEFF_FQ6_C1[4],
607        nqr.pow([
608            0x4649add3c71c6d90,
609            0x43caa6528972a865,
610            0xcda8445bbaaa0fbb,
611            0xc93dea665662aa66,
612            0x2863bc891834481d,
613            0x51a0c3f5d4ccbed8,
614            0x9210e660f90ccae9,
615            0xe2bd6836c546d65e,
616            0xf223abbaa7cf778b,
617            0xd4f10b222cf11680,
618            0xd540f5eff4a1962e,
619            0xa123a1f140b56526,
620            0x31ace500636a59f6,
621            0x3a82bc8c8dfa57a9,
622            0x648c511e217fc1f8,
623            0x36c17ffd53a4558f,
624            0x881bef5fd684eefd,
625            0x5d648dbdc5dbb522,
626            0x8fd07bf06e5e59b8,
627            0x8ddec8a9acaa4b51,
628            0x4cc1f8688e2def26,
629            0xa74e63cb492c03de,
630            0x57c968173d1349bb,
631            0x253674e02a866
632        ])
633    );
634    assert_eq!(
635        FROBENIUS_COEFF_FQ6_C1[5],
636        nqr.pow([
637            0xf896f792732eb2be,
638            0x49c86a6d1dc593a1,
639            0xe5b31e94581f91c3,
640            0xe3da5cc0a6b20d7f,
641            0x822caef950e0bfed,
642            0x317ed950b9ee67cd,
643            0xffd664016ee3f6cd,
644            0x77d991c88810b122,
645            0x62e72e635e698264,
646            0x905e1a1a2d22814a,
647            0xf5b7ab3a3f33d981,
648            0x175871b0bc0e25dd,
649            0x1e2e9a63df5c3772,
650            0xe888b1f7445b149d,
651            0x9551c19e5e7e2c24,
652            0xecf21939a3d2d6be,
653            0xd830dbfdab72dbd4,
654            0x7b34af8d622d40c0,
655            0x3df6d20a45671242,
656            0xaf86bee30e21d98,
657            0x41064c1534e5df5d,
658            0xf5f6cabd3164c609,
659            0xa5d14bdf2b7ee65,
660            0xa718c069defc9138,
661            0xdb1447e770e3110e,
662            0xc1b164a9e90af491,
663            0x7180441f9d251602,
664            0x1fd3a5e6a9a893e,
665            0x1e17b779d54d5db,
666            0x3c7afafe3174
667        ])
668    );
669
670    assert_eq!(FROBENIUS_COEFF_FQ6_C2[0], Fq2::one());
671    assert_eq!(
672        FROBENIUS_COEFF_FQ6_C2[1],
673        nqr.pow([
674            0x26a9ffffffffc71c,
675            0x1472aaa9cb8d5555,
676            0x9a208c6b4f20a418,
677            0x984f87adf7ae0c7f,
678            0x32126fced787c88f,
679            0x11560bf17baa99bc
680        ])
681    );
682    assert_eq!(
683        FROBENIUS_COEFF_FQ6_C2[2],
684        nqr.pow([
685            0x6f1c000012f65ed0,
686            0xa89e4768f97ac9c7,
687            0xb972cd024160d353,
688            0x99d50bf37ef67a2c,
689            0x1b74591af5b66adb,
690            0x139aebbdaebae852,
691            0xf8cb862206509f56,
692            0x8b1973536493dc49,
693            0x99ee698623145d35,
694            0x41e86098b44ad9cd,
695            0x87e1a5f1c174c3f1,
696            0x1c2cfc325d7952f
697        ])
698    );
699    assert_eq!(
700        FROBENIUS_COEFF_FQ6_C2[3],
701        nqr.pow([
702            0xb78df9ade6b73c0c,
703            0x32fbd5a217d9ad55,
704            0x3b77a4982e40c8c1,
705            0xe572f598c0af88bd,
706            0xf1d344617e18c51c,
707            0xc8f996310b8c74f,
708            0x9d004c9f8ab7eddc,
709            0x29b1ae2d87273f89,
710            0x5af1e1d6efdcddc3,
711            0xadfc937fcafb8bf3,
712            0x4cadad82b8c6c8f,
713            0x1bec505e223f5206,
714            0x37b74c7c0c656976,
715            0xd106b2f7954a0bd6,
716            0x4ada9d9218695304,
717            0xfc988504777d2165,
718            0xec8e5154db961e40,
719            0x2dcafc2dde2a5f
720        ])
721    );
722    assert_eq!(
723        FROBENIUS_COEFF_FQ6_C2[4],
724        nqr.pow([
725            0x8c935ba78e38db20,
726            0x87954ca512e550ca,
727            0x9b5088b775541f76,
728            0x927bd4ccacc554cd,
729            0x50c779123068903b,
730            0xa34187eba9997db0,
731            0x2421ccc1f21995d2,
732            0xc57ad06d8a8dacbd,
733            0xe44757754f9eef17,
734            0xa9e2164459e22d01,
735            0xaa81ebdfe9432c5d,
736            0x424743e2816aca4d,
737            0x6359ca00c6d4b3ed,
738            0x750579191bf4af52,
739            0xc918a23c42ff83f0,
740            0x6d82fffaa748ab1e,
741            0x1037debfad09ddfa,
742            0xbac91b7b8bb76a45,
743            0x1fa0f7e0dcbcb370,
744            0x1bbd9153595496a3,
745            0x9983f0d11c5bde4d,
746            0x4e9cc796925807bc,
747            0xaf92d02e7a269377,
748            0x4a6ce9c0550cc
749        ])
750    );
751    assert_eq!(
752        FROBENIUS_COEFF_FQ6_C2[5],
753        nqr.pow([
754            0xf12def24e65d657c,
755            0x9390d4da3b8b2743,
756            0xcb663d28b03f2386,
757            0xc7b4b9814d641aff,
758            0x4595df2a1c17fdb,
759            0x62fdb2a173dccf9b,
760            0xffacc802ddc7ed9a,
761            0xefb3239110216245,
762            0xc5ce5cc6bcd304c8,
763            0x20bc34345a450294,
764            0xeb6f56747e67b303,
765            0x2eb0e361781c4bbb,
766            0x3c5d34c7beb86ee4,
767            0xd11163ee88b6293a,
768            0x2aa3833cbcfc5849,
769            0xd9e4327347a5ad7d,
770            0xb061b7fb56e5b7a9,
771            0xf6695f1ac45a8181,
772            0x7beda4148ace2484,
773            0x15f0d7dc61c43b30,
774            0x820c982a69cbbeba,
775            0xebed957a62c98c12,
776            0x14ba297be56fdccb,
777            0x4e3180d3bdf92270,
778            0xb6288fcee1c6221d,
779            0x8362c953d215e923,
780            0xe300883f3a4a2c05,
781            0x3fa74bcd535127c,
782            0x3c2f6ef3aa9abb6,
783            0x78f5f5fc62e8
784        ])
785    );
786
787    assert_eq!(FROBENIUS_COEFF_FQ12_C1[0], Fq2::one());
788    assert_eq!(
789        FROBENIUS_COEFF_FQ12_C1[1],
790        nqr.pow([
791            0x49aa7ffffffff1c7,
792            0x51caaaa72e35555,
793            0xe688231ad3c82906,
794            0xe613e1eb7deb831f,
795            0xc849bf3b5e1f223,
796            0x45582fc5eeaa66f
797        ])
798    );
799    assert_eq!(
800        FROBENIUS_COEFF_FQ12_C1[2],
801        nqr.pow([
802            0xdbc7000004bd97b4,
803            0xea2791da3e5eb271,
804            0x2e5cb340905834d4,
805            0xe67542fcdfbd9e8b,
806            0x86dd1646bd6d9ab6,
807            0x84e6baef6baeba14,
808            0x7e32e188819427d5,
809            0x62c65cd4d924f712,
810            0x667b9a6188c5174d,
811            0x507a18262d12b673,
812            0xe1f8697c705d30fc,
813            0x70b3f0c975e54b
814        ])
815    );
816    assert_eq!(
817        FROBENIUS_COEFF_FQ12_C1[3],
818        nqr.pow(vec![
819            0x6de37e6b79adcf03,
820            0x4cbef56885f66b55,
821            0x4edde9260b903230,
822            0x395cbd66302be22f,
823            0xfc74d1185f863147,
824            0x323e658c42e31d3,
825            0x67401327e2adfb77,
826            0xca6c6b8b61c9cfe2,
827            0xd6bc7875bbf73770,
828            0xeb7f24dff2bee2fc,
829            0x8132b6b60ae31b23,
830            0x86fb1417888fd481,
831            0x8dedd31f03195a5d,
832            0x3441acbde55282f5,
833            0x52b6a764861a54c1,
834            0x3f2621411ddf4859,
835            0xfb23945536e58790,
836            0xb72bf0b778a97,
837        ])
838    );
839    assert_eq!(
840        FROBENIUS_COEFF_FQ12_C1[4],
841        nqr.pow(vec![
842            0xa324d6e9e38e36c8,
843            0xa1e5532944b95432,
844            0x66d4222ddd5507dd,
845            0xe49ef5332b315533,
846            0x1431de448c1a240e,
847            0xa8d061faea665f6c,
848            0x490873307c866574,
849            0xf15eb41b62a36b2f,
850            0x7911d5dd53e7bbc5,
851            0x6a78859116788b40,
852            0x6aa07af7fa50cb17,
853            0x5091d0f8a05ab293,
854            0x98d6728031b52cfb,
855            0x1d415e4646fd2bd4,
856            0xb246288f10bfe0fc,
857            0x9b60bffea9d22ac7,
858            0x440df7afeb42777e,
859            0x2eb246dee2edda91,
860            0xc7e83df8372f2cdc,
861            0x46ef6454d65525a8,
862            0x2660fc344716f793,
863            0xd3a731e5a49601ef,
864            0x2be4b40b9e89a4dd,
865            0x129b3a7015433,
866        ])
867    );
868    assert_eq!(
869        FROBENIUS_COEFF_FQ12_C1[5],
870        nqr.pow(vec![
871            0xfc4b7bc93997595f,
872            0xa4e435368ee2c9d0,
873            0xf2d98f4a2c0fc8e1,
874            0xf1ed2e60535906bf,
875            0xc116577ca8705ff6,
876            0x98bf6ca85cf733e6,
877            0x7feb3200b771fb66,
878            0x3becc8e444085891,
879            0x31739731af34c132,
880            0xc82f0d0d169140a5,
881            0xfadbd59d1f99ecc0,
882            0xbac38d85e0712ee,
883            0x8f174d31efae1bb9,
884            0x744458fba22d8a4e,
885            0x4aa8e0cf2f3f1612,
886            0x76790c9cd1e96b5f,
887            0x6c186dfed5b96dea,
888            0x3d9a57c6b116a060,
889            0x1efb690522b38921,
890            0x857c35f718710ecc,
891            0xa083260a9a72efae,
892            0xfafb655e98b26304,
893            0x52e8a5ef95bf732,
894            0x538c6034ef7e489c,
895            0xed8a23f3b8718887,
896            0x60d8b254f4857a48,
897            0x38c0220fce928b01,
898            0x80fe9d2f354d449f,
899            0xf0bdbbceaa6aed,
900            0x1e3d7d7f18ba,
901        ])
902    );
903    assert_eq!(
904        FROBENIUS_COEFF_FQ12_C1[6],
905        nqr.pow(vec![
906            0x21219610a012ba3c,
907            0xa5c19ad35375325,
908            0x4e9df1e497674396,
909            0xfb05b717c991c6ef,
910            0x4a1265bca93a32f2,
911            0xd875ff2a7bdc1f66,
912            0xc6d8754736c771b2,
913            0x2d80c759ba5a2ae7,
914            0x138a20df4b03cc1a,
915            0xc22d07fe68e93024,
916            0xd1dc474d3b433133,
917            0xc22aa5e75044e5c,
918            0xf657c6fbf9c17ebf,
919            0xc591a794a58660d,
920            0x2261850ee1453281,
921            0xd17d3bd3b7f5efb4,
922            0xf00cec8ec507d01,
923            0x2a6a775657a00ae6,
924            0x5f098a12ff470719,
925            0x409d194e7b5c5afa,
926            0x1d66478e982af5b,
927            0xda425a5b5e01ca3f,
928            0xf77e4f78747e903c,
929            0x177d49f73732c6fc,
930            0xa9618fecabe0e1f4,
931            0xba5337eac90bd080,
932            0x66fececdbc35d4e7,
933            0xa4cd583203d9206f,
934            0x98391632ceeca596,
935            0x4946b76e1236ad3f,
936            0xa0dec64e60e711a1,
937            0xfcb41ed3605013,
938            0x8ca8f9692ae1e3a9,
939            0xd3078bfc28cc1baf,
940            0xf0536f764e982f82,
941            0x3125f1a2656,
942        ])
943    );
944    assert_eq!(
945        FROBENIUS_COEFF_FQ12_C1[7],
946        nqr.pow(vec![
947            0x742754a1f22fdb,
948            0x2a1955c2dec3a702,
949            0x9747b28c796d134e,
950            0xc113a0411f59db79,
951            0x3bb0fa929853bfc1,
952            0x28c3c25f8f6fb487,
953            0xbc2b6c99d3045b34,
954            0x98fb67d6badde1fd,
955            0x48841d76a24d2073,
956            0xd49891145fe93ae6,
957            0xc772b9c8e74d4099,
958            0xccf4e7b9907755bb,
959            0x9cf47b25d42fd908,
960            0x5616a0c347fc445d,
961            0xff93b7a7ad1b8a6d,
962            0xac2099256b78a77a,
963            0x7804a95b02892e1c,
964            0x5cf59ca7bfd69776,
965            0xa7023502acd3c866,
966            0xc76f4982fcf8f37,
967            0x51862a5a57ac986e,
968            0x38b80ed72b1b1023,
969            0x4a291812066a61e1,
970            0xcd8a685eff45631,
971            0x3f40f708764e4fa5,
972            0x8aa0441891285092,
973            0x9eff60d71cdf0a9,
974            0x4fdd9d56517e2bfa,
975            0x1f3c80d74a28bc85,
976            0x24617417c064b648,
977            0x7ddda1e4385d5088,
978            0xf9e132b11dd32a16,
979            0xcc957cb8ef66ab99,
980            0xd4f206d37cb752c5,
981            0x40de343f28ad616b,
982            0x8d1f24379068f0e3,
983            0x6f31d7947ea21137,
984            0x27311f9c32184061,
985            0x9eea0664cc78ce5f,
986            0x7d4151f6fea9a0da,
987            0x454096fa75bd571a,
988            0x4fe0f20ecb,
989        ])
990    );
991    assert_eq!(
992        FROBENIUS_COEFF_FQ12_C1[8],
993        nqr.pow(vec![
994            0x802f5720d0b25710,
995            0x6714f0a258b85c7c,
996            0x31394c90afdf16e,
997            0xe9d2b0c64f957b19,
998            0xe67c0d9c5e7903ee,
999            0x3156fdc5443ea8ef,
1000            0x7c4c50524d88c892,
1001            0xc99dc8990c0ad244,
1002            0xd37ababf3649a896,
1003            0x76fe4b838ff7a20c,
1004            0xcf69ee2cec728db3,
1005            0xb83535548e5f41,
1006            0x371147684ccb0c23,
1007            0x194f6f4fa500db52,
1008            0xc4571dc78a4c5374,
1009            0xe4d46d479999ca97,
1010            0x76b6785a615a151c,
1011            0xcceb8bcea7eaf8c1,
1012            0x80d87a6fbe5ae687,
1013            0x6a97ddddb85ce85,
1014            0xd783958f26034204,
1015            0x7144506f2e2e8590,
1016            0x948693d377aef166,
1017            0x8364621ed6f96056,
1018            0xf021777c4c09ee2d,
1019            0xc6cf5e746ecd50b,
1020            0xa2337b7aa22743df,
1021            0xae753f8bbacab39c,
1022            0xfc782a9e34d3c1cc,
1023            0x21b827324fe494d9,
1024            0x5692ce350ed03b38,
1025            0xf323a2b3cd0481b0,
1026            0xe859c97a4ccad2e3,
1027            0x48434b70381e4503,
1028            0x46042d62e4132ed8,
1029            0x48c4d6f56122e2f2,
1030            0xf87711ab9f5c1af7,
1031            0xb14b7a054759b469,
1032            0x8eb0a96993ffa9aa,
1033            0x9b21fb6fc58b760c,
1034            0xf3abdd115d2e7d25,
1035            0xf7beac3d4d12409c,
1036            0x40a5585cce69bf03,
1037            0x697881e1ba22d5a8,
1038            0x3d6c04e6ad373fd9,
1039            0x849871bf627be886,
1040            0x550f4b9b71b28ef9,
1041            0x81d2e0d78,
1042        ])
1043    );
1044    assert_eq!(
1045        FROBENIUS_COEFF_FQ12_C1[9],
1046        nqr.pow(vec![
1047            0x4af4accf7de0b977,
1048            0x742485e21805b4ee,
1049            0xee388fbc4ac36dec,
1050            0x1e199da57ad178a,
1051            0xc27c12b292c6726a,
1052            0x162e6ed84505b5e8,
1053            0xe191683f336e09df,
1054            0x17deb7e8d1e0fce6,
1055            0xd944f19ad06f5836,
1056            0x4c5f5e59f6276026,
1057            0xf1ba9c7c148a38a8,
1058            0xd205fe2dba72b326,
1059            0x9a2cf2a4c289824e,
1060            0x4f47ad512c39e24d,
1061            0xc5894d984000ea09,
1062            0x2974c03ff7cf01fa,
1063            0xfcd243b48cb99a22,
1064            0x2b5150c9313ac1e8,
1065            0x9089f37c7fc80eda,
1066            0x989540cc9a7aea56,
1067            0x1ab1d4e337e63018,
1068            0x42b546c30d357e43,
1069            0x1c6abc04f76233d9,
1070            0x78b3b8d88bf73e47,
1071            0x151c4e4c45dc68e6,
1072            0x519a79c4f54397ed,
1073            0x93f5b51535a127c5,
1074            0x5fc51b6f52fa153e,
1075            0x2e0504f2d4a965c3,
1076            0xc85bd3a3da52bffe,
1077            0x98c60957a46a89ef,
1078            0x48c03b5976b91cae,
1079            0xc6598040a0a61438,
1080            0xbf0b49dc255953af,
1081            0xb78dff905b628ab4,
1082            0x68140b797ba74ab8,
1083            0x116cf037991d1143,
1084            0x2f7fe82e58acb0b8,
1085            0xc20bf7a8f7be5d45,
1086            0x86c2905c338d5709,
1087            0xff13a3ae6c8ace3d,
1088            0xb6f95e2282d08337,
1089            0xd49f7b313e9cbf29,
1090            0xf794517193a1ce8c,
1091            0x39641fecb596a874,
1092            0x411c4c4edf462fb3,
1093            0x3f8cd55c10cf25b4,
1094            0x2bdd7ea165e860b6,
1095            0xacd7d2cef4caa193,
1096            0x6558a1d09a05f96,
1097            0x1f52b5f5b546fc20,
1098            0x4ee22a5a8c250c12,
1099            0xd3a63a54a205b6b3,
1100            0xd2ff5be8,
1101        ])
1102    );
1103    assert_eq!(
1104        FROBENIUS_COEFF_FQ12_C1[10],
1105        nqr.pow(vec![
1106            0xe5953a4f96cdda44,
1107            0x336b2d734cbc32bb,
1108            0x3f79bfe3cd7410e,
1109            0x267ae19aaa0f0332,
1110            0x85a9c4db78d5c749,
1111            0x90996b046b5dc7d8,
1112            0x8945eae9820afc6a,
1113            0x2644ddea2b036bd,
1114            0x39898e35ac2e3819,
1115            0x2574eab095659ab9,
1116            0x65953d51ac5ea798,
1117            0xc6b8c7afe6752466,
1118            0x40e9e993e9286544,
1119            0x7e0ad34ad9700ea0,
1120            0xac1015eba2c69222,
1121            0x24f057a19239b5d8,
1122            0x2043b48c8a3767eb,
1123            0x1117c124a75d7ff4,
1124            0x433cfd1a09fb3ce7,
1125            0x25b087ce4bcf7fb,
1126            0xbcee0dc53a3e5bdb,
1127            0xbffda040cf028735,
1128            0xf7cf103a25512acc,
1129            0x31d4ecda673130b9,
1130            0xea0906dab18461e6,
1131            0x5a40585a5ac3050d,
1132            0x803358fc14fd0eda,
1133            0x3678ca654eada770,
1134            0x7b91a1293a45e33e,
1135            0xcd5e5b8ea8530e43,
1136            0x21ae563ab34da266,
1137            0xecb00dad60df8894,
1138            0x77fe53e652facfef,
1139            0x9b7d1ad0b00244ec,
1140            0xe695df5ca73f801,
1141            0x23cdb21feeab0149,
1142            0x14de113e7ea810d9,
1143            0x52600cd958dac7e7,
1144            0xc83392c14667e488,
1145            0x9f808444bc1717fc,
1146            0x56facb4bcf7c788f,
1147            0x8bcad53245fc3ca0,
1148            0xdef661e83f27d81c,
1149            0x37d4ebcac9ad87e5,
1150            0x6fe8b24f5cdb9324,
1151            0xee08a26c1197654c,
1152            0xc98b22f65f237e9a,
1153            0xf54873a908ed3401,
1154            0x6e1cb951d41f3f3,
1155            0x290b2250a54e8df6,
1156            0x7f36d51eb1db669e,
1157            0xb08c7ed81a6ee43e,
1158            0x95e1c90fb092f680,
1159            0x429e4afd0e8b820,
1160            0x2c14a83ee87d715c,
1161            0xf37267575cfc8af5,
1162            0xb99e9afeda3c2c30,
1163            0x8f0f69da75792d5a,
1164            0x35074a85a533c73,
1165            0x156ed119,
1166        ])
1167    );
1168    assert_eq!(
1169        FROBENIUS_COEFF_FQ12_C1[11],
1170        nqr.pow(vec![
1171            0x107db680942de533,
1172            0x6262b24d2052393b,
1173            0x6136df824159ebc,
1174            0xedb052c9970c5deb,
1175            0xca813aea916c3777,
1176            0xf49dacb9d76c1788,
1177            0x624941bd372933bb,
1178            0xa5e60c2520638331,
1179            0xb38b661683411074,
1180            0x1d2c9af4c43d962b,
1181            0x17d807a0f14aa830,
1182            0x6e6581a51012c108,
1183            0x668a537e5b35e6f5,
1184            0x6c396cf3782dca5d,
1185            0x33b679d1bff536ed,
1186            0x736cce41805d90aa,
1187            0x8a562f369eb680bf,
1188            0x9f61aa208a11ded8,
1189            0x43dd89dd94d20f35,
1190            0xcf84c6610575c10a,
1191            0x9f318d49cf2fe8e6,
1192            0xbbc6e5f25a6e434e,
1193            0x6528c433d11d987b,
1194            0xffced71cc48c0e8a,
1195            0x4cbb1474f4cb2a26,
1196            0x66a035c0b28b7231,
1197            0xa6f2875faa1a82ae,
1198            0xdd1ea3deff818b02,
1199            0xe0cfdf0dcdecf701,
1200            0x9aefa231f2f6d23,
1201            0xfb251297efa06746,
1202            0x5a40d367df985538,
1203            0x1ea31d69ab506fed,
1204            0xc64ea8280e89a73f,
1205            0x969acf9f2d4496f4,
1206            0xe84c9181ee60c52c,
1207            0xc60f27fc19fc6ca4,
1208            0x760b33d850154048,
1209            0x84f69080f66c8457,
1210            0xc0192ba0fabf640e,
1211            0xd2c338765c23a3a8,
1212            0xa7838c20f02cec6c,
1213            0xb7cf01d020572877,
1214            0xd63ffaeba0be200a,
1215            0xf7492baeb5f041ac,
1216            0x8602c5212170d117,
1217            0xad9b2e83a5a42068,
1218            0x2461829b3ba1083e,
1219            0x7c34650da5295273,
1220            0xdc824ba800a8265a,
1221            0xd18d9b47836af7b2,
1222            0x3af78945c58cbf4d,
1223            0x7ed9575b8596906c,
1224            0x6d0c133895009a66,
1225            0x53bc1247ea349fe1,
1226            0x6b3063078d41aa7a,
1227            0x6184acd8cd880b33,
1228            0x76f4d15503fd1b96,
1229            0x7a9afd61eef25746,
1230            0xce974aadece60609,
1231            0x88ca59546a8ceafd,
1232            0x6d29391c41a0ac07,
1233            0x443843a60e0f46a6,
1234            0xa1590f62fd2602c7,
1235            0x536d5b15b514373f,
1236            0x22d582b,
1237        ])
1238    );
1239}
1240
1241#[test]
1242fn test_neg_one() {
1243    let mut o = Fq::one();
1244    o.negate();
1245
1246    assert_eq!(NEGATIVE_ONE, o);
1247}
1248
1249#[cfg(test)]
1250use rand_core::SeedableRng;
1251//use rand::{Rand, SeedableRng, XorShiftRng};
1252
1253#[test]
1254fn test_fq_repr_ordering() {
1255    use std::cmp::Ordering;
1256
1257    fn assert_equality(a: FqRepr, b: FqRepr) {
1258        assert_eq!(a, b);
1259        assert!(a.cmp(&b) == Ordering::Equal);
1260    }
1261
1262    fn assert_lt(a: FqRepr, b: FqRepr) {
1263        assert!(a < b);
1264        assert!(b > a);
1265    }
1266
1267    assert_equality(
1268        FqRepr([9999, 9999, 9999, 9999, 9999, 9999]),
1269        FqRepr([9999, 9999, 9999, 9999, 9999, 9999]),
1270    );
1271    assert_equality(
1272        FqRepr([9999, 9998, 9999, 9999, 9999, 9999]),
1273        FqRepr([9999, 9998, 9999, 9999, 9999, 9999]),
1274    );
1275    assert_equality(
1276        FqRepr([9999, 9999, 9999, 9997, 9999, 9999]),
1277        FqRepr([9999, 9999, 9999, 9997, 9999, 9999]),
1278    );
1279    assert_lt(
1280        FqRepr([9999, 9999, 9999, 9997, 9999, 9998]),
1281        FqRepr([9999, 9999, 9999, 9997, 9999, 9999]),
1282    );
1283    assert_lt(
1284        FqRepr([9999, 9999, 9999, 9997, 9998, 9999]),
1285        FqRepr([9999, 9999, 9999, 9997, 9999, 9999]),
1286    );
1287    assert_lt(
1288        FqRepr([9, 9999, 9999, 9997, 9998, 9999]),
1289        FqRepr([9999, 9999, 9999, 9997, 9999, 9999]),
1290    );
1291}
1292
1293#[test]
1294fn test_fq_repr_from() {
1295    assert_eq!(FqRepr::from(100), FqRepr([100, 0, 0, 0, 0, 0]));
1296}
1297
1298#[test]
1299fn test_fq_repr_is_odd() {
1300    assert!(!FqRepr::from(0).is_odd());
1301    assert!(FqRepr::from(0).is_even());
1302    assert!(FqRepr::from(1).is_odd());
1303    assert!(!FqRepr::from(1).is_even());
1304    assert!(!FqRepr::from(324834872).is_odd());
1305    assert!(FqRepr::from(324834872).is_even());
1306    assert!(FqRepr::from(324834873).is_odd());
1307    assert!(!FqRepr::from(324834873).is_even());
1308}
1309
1310#[test]
1311fn test_fq_repr_is_zero() {
1312    assert!(FqRepr::from(0).is_zero());
1313    assert!(!FqRepr::from(1).is_zero());
1314    assert!(!FqRepr([0, 0, 0, 0, 1, 0]).is_zero());
1315}
1316
1317#[test]
1318fn test_fq_repr_div2() {
1319    let mut a = FqRepr([
1320        0x8b0ad39f8dd7482a,
1321        0x147221c9a7178b69,
1322        0x54764cb08d8a6aa0,
1323        0x8519d708e1d83041,
1324        0x41f82777bd13fdb,
1325        0xf43944578f9b771b,
1326    ]);
1327    a.div2();
1328    assert_eq!(
1329        a,
1330        FqRepr([
1331            0xc58569cfc6eba415,
1332            0xa3910e4d38bc5b4,
1333            0xaa3b265846c53550,
1334            0xc28ceb8470ec1820,
1335            0x820fc13bbde89fed,
1336            0x7a1ca22bc7cdbb8d
1337        ])
1338    );
1339    for _ in 0..10 {
1340        a.div2();
1341    }
1342    assert_eq!(
1343        a,
1344        FqRepr([
1345            0x6d31615a73f1bae9,
1346            0x54028e443934e2f1,
1347            0x82a8ec99611b14d,
1348            0xfb70a33ae11c3b06,
1349            0xe36083f04eef7a27,
1350            0x1e87288af1f36e
1351        ])
1352    );
1353    for _ in 0..300 {
1354        a.div2();
1355    }
1356    assert_eq!(a, FqRepr([0x7288af1f36ee3608, 0x1e8, 0x0, 0x0, 0x0, 0x0]));
1357    for _ in 0..50 {
1358        a.div2();
1359    }
1360    assert_eq!(a, FqRepr([0x7a1ca2, 0x0, 0x0, 0x0, 0x0, 0x0]));
1361    for _ in 0..22 {
1362        a.div2();
1363    }
1364    assert_eq!(a, FqRepr([0x1, 0x0, 0x0, 0x0, 0x0, 0x0]));
1365    a.div2();
1366    assert!(a.is_zero());
1367}
1368
1369#[test]
1370fn test_fq_repr_shr() {
1371    let mut a = FqRepr([
1372        0xaa5cdd6172847ffd,
1373        0x43242c06aed55287,
1374        0x9ddd5b312f3dd104,
1375        0xc5541fd48046b7e7,
1376        0x16080cf4071e0b05,
1377        0x1225f2901aea514e,
1378    ]);
1379    a.shr(0);
1380    assert_eq!(
1381        a,
1382        FqRepr([
1383            0xaa5cdd6172847ffd,
1384            0x43242c06aed55287,
1385            0x9ddd5b312f3dd104,
1386            0xc5541fd48046b7e7,
1387            0x16080cf4071e0b05,
1388            0x1225f2901aea514e
1389        ])
1390    );
1391    a.shr(1);
1392    assert_eq!(
1393        a,
1394        FqRepr([
1395            0xd52e6eb0b9423ffe,
1396            0x21921603576aa943,
1397            0xceeead98979ee882,
1398            0xe2aa0fea40235bf3,
1399            0xb04067a038f0582,
1400            0x912f9480d7528a7
1401        ])
1402    );
1403    a.shr(50);
1404    assert_eq!(
1405        a,
1406        FqRepr([
1407            0x8580d5daaa50f54b,
1408            0xab6625e7ba208864,
1409            0x83fa9008d6fcf3bb,
1410            0x19e80e3c160b8aa,
1411            0xbe52035d4a29c2c1,
1412            0x244
1413        ])
1414    );
1415    a.shr(130);
1416    assert_eq!(
1417        a,
1418        FqRepr([
1419            0xa0fea40235bf3cee,
1420            0x4067a038f0582e2a,
1421            0x2f9480d7528a70b0,
1422            0x91,
1423            0x0,
1424            0x0
1425        ])
1426    );
1427    a.shr(64);
1428    assert_eq!(
1429        a,
1430        FqRepr([0x4067a038f0582e2a, 0x2f9480d7528a70b0, 0x91, 0x0, 0x0, 0x0])
1431    );
1432}
1433
1434#[test]
1435fn test_fq_repr_mul2() {
1436    let mut a = FqRepr::from(23712937547);
1437    a.mul2();
1438    assert_eq!(a, FqRepr([0xb0acd6c96, 0x0, 0x0, 0x0, 0x0, 0x0]));
1439    for _ in 0..60 {
1440        a.mul2();
1441    }
1442    assert_eq!(
1443        a,
1444        FqRepr([0x6000000000000000, 0xb0acd6c9, 0x0, 0x0, 0x0, 0x0])
1445    );
1446    for _ in 0..300 {
1447        a.mul2();
1448    }
1449    assert_eq!(a, FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0xcd6c960000000000]));
1450    for _ in 0..17 {
1451        a.mul2();
1452    }
1453    assert_eq!(a, FqRepr([0x0, 0x0, 0x0, 0x0, 0x0, 0x2c00000000000000]));
1454    for _ in 0..6 {
1455        a.mul2();
1456    }
1457    assert!(a.is_zero());
1458}
1459
1460#[test]
1461fn test_fq_repr_num_bits() {
1462    let mut a = FqRepr::from(0);
1463    assert_eq!(0, a.num_bits());
1464    a = FqRepr::from(1);
1465    for i in 1..385 {
1466        assert_eq!(i, a.num_bits());
1467        a.mul2();
1468    }
1469    assert_eq!(0, a.num_bits());
1470}
1471
1472#[test]
1473fn test_fq_repr_sub_noborrow() {
1474    let mut rng = rand_xorshift::XorShiftRng::from_seed([
1475        0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06, 0xbc,
1476        0xe5,
1477    ]);
1478    let mut t = FqRepr([
1479        0x827a4a08041ebd9,
1480        0x3c239f3dcc8f0d6b,
1481        0x9ab46a912d555364,
1482        0x196936b17b43910b,
1483        0xad0eb3948a5c34fd,
1484        0xd56f7b5ab8b5ce8,
1485    ]);
1486    t.sub_noborrow(&FqRepr([
1487        0xc7867917187ca02b,
1488        0x5d75679d4911ffef,
1489        0x8c5b3e48b1a71c15,
1490        0x6a427ae846fd66aa,
1491        0x7a37e7265ee1eaf9,
1492        0x7c0577a26f59d5,
1493    ]));
1494    assert!(
1495        t == FqRepr([
1496            0x40a12b8967c54bae,
1497            0xdeae37a0837d0d7b,
1498            0xe592c487bae374e,
1499            0xaf26bbc934462a61,
1500            0x32d6cc6e2b7a4a03,
1501            0xcdaf23e091c0313
1502        ])
1503    );
1504
1505    for _ in 0..1000 {
1506        let mut a = Fq::random(&mut rng).into_repr();
1507        a.0[5] >>= 30;
1508        let mut b = a;
1509        for _ in 0..10 {
1510            b.mul2();
1511        }
1512        let mut c = b;
1513        for _ in 0..10 {
1514            c.mul2();
1515        }
1516
1517        assert!(a < b);
1518        assert!(b < c);
1519
1520        let mut csub_ba = c;
1521        csub_ba.sub_noborrow(&b);
1522        csub_ba.sub_noborrow(&a);
1523
1524        let mut csub_ab = c;
1525        csub_ab.sub_noborrow(&a);
1526        csub_ab.sub_noborrow(&b);
1527
1528        assert_eq!(csub_ab, csub_ba);
1529    }
1530
1531    // Subtracting q+1 from q should produce -1 (mod 2**384)
1532    let mut qplusone = FqRepr([
1533        0xb9feffffffffaaab,
1534        0x1eabfffeb153ffff,
1535        0x6730d2a0f6b0f624,
1536        0x64774b84f38512bf,
1537        0x4b1ba7b6434bacd7,
1538        0x1a0111ea397fe69a,
1539    ]);
1540    qplusone.sub_noborrow(&FqRepr([
1541        0xb9feffffffffaaac,
1542        0x1eabfffeb153ffff,
1543        0x6730d2a0f6b0f624,
1544        0x64774b84f38512bf,
1545        0x4b1ba7b6434bacd7,
1546        0x1a0111ea397fe69a,
1547    ]));
1548    assert_eq!(
1549        qplusone,
1550        FqRepr([
1551            0xffffffffffffffff,
1552            0xffffffffffffffff,
1553            0xffffffffffffffff,
1554            0xffffffffffffffff,
1555            0xffffffffffffffff,
1556            0xffffffffffffffff
1557        ])
1558    );
1559}
1560
1561#[test]
1562fn test_fq_repr_add_nocarry() {
1563    let mut rng = rand_xorshift::XorShiftRng::from_seed([
1564        0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06, 0xbc,
1565        0xe5,
1566    ]);
1567    let mut t = FqRepr([
1568        0x827a4a08041ebd9,
1569        0x3c239f3dcc8f0d6b,
1570        0x9ab46a912d555364,
1571        0x196936b17b43910b,
1572        0xad0eb3948a5c34fd,
1573        0xd56f7b5ab8b5ce8,
1574    ]);
1575    t.add_nocarry(&FqRepr([
1576        0xc7867917187ca02b,
1577        0x5d75679d4911ffef,
1578        0x8c5b3e48b1a71c15,
1579        0x6a427ae846fd66aa,
1580        0x7a37e7265ee1eaf9,
1581        0x7c0577a26f59d5,
1582    ]));
1583    assert!(
1584        t == FqRepr([
1585            0xcfae1db798be8c04,
1586            0x999906db15a10d5a,
1587            0x270fa8d9defc6f79,
1588            0x83abb199c240f7b6,
1589            0x27469abae93e1ff6,
1590            0xdd2fd2d4dfab6be
1591        ])
1592    );
1593
1594    // Test for the associativity of addition.
1595    for _ in 0..1000 {
1596        let mut a = Fq::random(&mut rng).into_repr();
1597        let mut b = Fq::random(&mut rng).into_repr();
1598        let mut c = Fq::random(&mut rng).into_repr();
1599
1600        // Unset the first few bits, so that overflow won't occur.
1601        a.0[5] >>= 3;
1602        b.0[5] >>= 3;
1603        c.0[5] >>= 3;
1604
1605        let mut abc = a;
1606        abc.add_nocarry(&b);
1607        abc.add_nocarry(&c);
1608
1609        let mut acb = a;
1610        acb.add_nocarry(&c);
1611        acb.add_nocarry(&b);
1612
1613        let mut bac = b;
1614        bac.add_nocarry(&a);
1615        bac.add_nocarry(&c);
1616
1617        let mut bca = b;
1618        bca.add_nocarry(&c);
1619        bca.add_nocarry(&a);
1620
1621        let mut cab = c;
1622        cab.add_nocarry(&a);
1623        cab.add_nocarry(&b);
1624
1625        let mut cba = c;
1626        cba.add_nocarry(&b);
1627        cba.add_nocarry(&a);
1628
1629        assert_eq!(abc, acb);
1630        assert_eq!(abc, bac);
1631        assert_eq!(abc, bca);
1632        assert_eq!(abc, cab);
1633        assert_eq!(abc, cba);
1634    }
1635
1636    // Adding 1 to (2^384 - 1) should produce zero
1637    let mut x = FqRepr([
1638        0xffffffffffffffff,
1639        0xffffffffffffffff,
1640        0xffffffffffffffff,
1641        0xffffffffffffffff,
1642        0xffffffffffffffff,
1643        0xffffffffffffffff,
1644    ]);
1645    x.add_nocarry(&FqRepr::from(1));
1646    assert!(x.is_zero());
1647}
1648
1649#[test]
1650fn test_fq_is_valid() {
1651    let mut a = Fq(MODULUS);
1652    assert!(!a.is_valid());
1653    a.0.sub_noborrow(&FqRepr::from(1));
1654    assert!(a.is_valid());
1655    assert!(Fq(FqRepr::from(0)).is_valid());
1656    assert!(Fq(FqRepr([
1657        0xdf4671abd14dab3e,
1658        0xe2dc0c9f534fbd33,
1659        0x31ca6c880cc444a6,
1660        0x257a67e70ef33359,
1661        0xf9b29e493f899b36,
1662        0x17c8be1800b9f059
1663    ]))
1664    .is_valid());
1665    assert!(!Fq(FqRepr([
1666        0xffffffffffffffff,
1667        0xffffffffffffffff,
1668        0xffffffffffffffff,
1669        0xffffffffffffffff,
1670        0xffffffffffffffff,
1671        0xffffffffffffffff
1672    ]))
1673    .is_valid());
1674
1675    let mut rng = rand_xorshift::XorShiftRng::from_seed([
1676        0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06, 0xbc,
1677        0xe5,
1678    ]);
1679    for _ in 0..1000 {
1680        let a = Fq::random(&mut rng);
1681        assert!(a.is_valid());
1682    }
1683}
1684
1685#[test]
1686fn test_fq_add_assign() {
1687    {
1688        // Random number
1689        let mut tmp = Fq(FqRepr([
1690            0x624434821df92b69,
1691            0x503260c04fd2e2ea,
1692            0xd9df726e0d16e8ce,
1693            0xfbcb39adfd5dfaeb,
1694            0x86b8a22b0c88b112,
1695            0x165a2ed809e4201b,
1696        ]));
1697        assert!(tmp.is_valid());
1698        // Test that adding zero has no effect.
1699        tmp.add_assign(&Fq(FqRepr::from(0)));
1700        assert_eq!(
1701            tmp,
1702            Fq(FqRepr([
1703                0x624434821df92b69,
1704                0x503260c04fd2e2ea,
1705                0xd9df726e0d16e8ce,
1706                0xfbcb39adfd5dfaeb,
1707                0x86b8a22b0c88b112,
1708                0x165a2ed809e4201b
1709            ]))
1710        );
1711        // Add one and test for the result.
1712        tmp.add_assign(&Fq(FqRepr::from(1)));
1713        assert_eq!(
1714            tmp,
1715            Fq(FqRepr([
1716                0x624434821df92b6a,
1717                0x503260c04fd2e2ea,
1718                0xd9df726e0d16e8ce,
1719                0xfbcb39adfd5dfaeb,
1720                0x86b8a22b0c88b112,
1721                0x165a2ed809e4201b
1722            ]))
1723        );
1724        // Add another random number that exercises the reduction.
1725        tmp.add_assign(&Fq(FqRepr([
1726            0x374d8f8ea7a648d8,
1727            0xe318bb0ebb8bfa9b,
1728            0x613d996f0a95b400,
1729            0x9fac233cb7e4fef1,
1730            0x67e47552d253c52,
1731            0x5c31b227edf25da,
1732        ])));
1733        assert_eq!(
1734            tmp,
1735            Fq(FqRepr([
1736                0xdf92c410c59fc997,
1737                0x149f1bd05a0add85,
1738                0xd3ec393c20fba6ab,
1739                0x37001165c1bde71d,
1740                0x421b41c9f662408e,
1741                0x21c38104f435f5b
1742            ]))
1743        );
1744        // Add one to (q - 1) and test for the result.
1745        tmp = Fq(FqRepr([
1746            0xb9feffffffffaaaa,
1747            0x1eabfffeb153ffff,
1748            0x6730d2a0f6b0f624,
1749            0x64774b84f38512bf,
1750            0x4b1ba7b6434bacd7,
1751            0x1a0111ea397fe69a,
1752        ]));
1753        tmp.add_assign(&Fq(FqRepr::from(1)));
1754        assert!(tmp.0.is_zero());
1755        // Add a random number to another one such that the result is q - 1
1756        tmp = Fq(FqRepr([
1757            0x531221a410efc95b,
1758            0x72819306027e9717,
1759            0x5ecefb937068b746,
1760            0x97de59cd6feaefd7,
1761            0xdc35c51158644588,
1762            0xb2d176c04f2100,
1763        ]));
1764        tmp.add_assign(&Fq(FqRepr([
1765            0x66ecde5bef0fe14f,
1766            0xac2a6cf8aed568e8,
1767            0x861d70d86483edd,
1768            0xcc98f1b7839a22e8,
1769            0x6ee5e2a4eae7674e,
1770            0x194e40737930c599,
1771        ])));
1772        assert_eq!(
1773            tmp,
1774            Fq(FqRepr([
1775                0xb9feffffffffaaaa,
1776                0x1eabfffeb153ffff,
1777                0x6730d2a0f6b0f624,
1778                0x64774b84f38512bf,
1779                0x4b1ba7b6434bacd7,
1780                0x1a0111ea397fe69a
1781            ]))
1782        );
1783        // Add one to the result and test for it.
1784        tmp.add_assign(&Fq(FqRepr::from(1)));
1785        assert!(tmp.0.is_zero());
1786    }
1787
1788    // Test associativity
1789    let mut rng = rand_xorshift::XorShiftRng::from_seed([
1790        0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06, 0xbc,
1791        0xe5,
1792    ]);
1793    for _ in 0..1000 {
1794        // Generate a, b, c and ensure (a + b) + c == a + (b + c).
1795        let a = Fq::random(&mut rng);
1796        let b = Fq::random(&mut rng);
1797        let c = Fq::random(&mut rng);
1798
1799        let mut tmp1 = a;
1800        tmp1.add_assign(&b);
1801        tmp1.add_assign(&c);
1802
1803        let mut tmp2 = b;
1804        tmp2.add_assign(&c);
1805        tmp2.add_assign(&a);
1806
1807        assert!(tmp1.is_valid());
1808        assert!(tmp2.is_valid());
1809        assert_eq!(tmp1, tmp2);
1810    }
1811}
1812
1813#[test]
1814fn test_fq_sub_assign() {
1815    {
1816        // Test arbitrary subtraction that tests reduction.
1817        let mut tmp = Fq(FqRepr([
1818            0x531221a410efc95b,
1819            0x72819306027e9717,
1820            0x5ecefb937068b746,
1821            0x97de59cd6feaefd7,
1822            0xdc35c51158644588,
1823            0xb2d176c04f2100,
1824        ]));
1825        tmp.sub_assign(&Fq(FqRepr([
1826            0x98910d20877e4ada,
1827            0x940c983013f4b8ba,
1828            0xf677dc9b8345ba33,
1829            0xbef2ce6b7f577eba,
1830            0xe1ae288ac3222c44,
1831            0x5968bb602790806,
1832        ])));
1833        assert_eq!(
1834            tmp,
1835            Fq(FqRepr([
1836                0x748014838971292c,
1837                0xfd20fad49fddde5c,
1838                0xcf87f198e3d3f336,
1839                0x3d62d6e6e41883db,
1840                0x45a3443cd88dc61b,
1841                0x151d57aaf755ff94
1842            ]))
1843        );
1844
1845        // Test the opposite subtraction which doesn't test reduction.
1846        tmp = Fq(FqRepr([
1847            0x98910d20877e4ada,
1848            0x940c983013f4b8ba,
1849            0xf677dc9b8345ba33,
1850            0xbef2ce6b7f577eba,
1851            0xe1ae288ac3222c44,
1852            0x5968bb602790806,
1853        ]));
1854        tmp.sub_assign(&Fq(FqRepr([
1855            0x531221a410efc95b,
1856            0x72819306027e9717,
1857            0x5ecefb937068b746,
1858            0x97de59cd6feaefd7,
1859            0xdc35c51158644588,
1860            0xb2d176c04f2100,
1861        ])));
1862        assert_eq!(
1863            tmp,
1864            Fq(FqRepr([
1865                0x457eeb7c768e817f,
1866                0x218b052a117621a3,
1867                0x97a8e10812dd02ed,
1868                0x2714749e0f6c8ee3,
1869                0x57863796abde6bc,
1870                0x4e3ba3f4229e706
1871            ]))
1872        );
1873
1874        // Test for sensible results with zero
1875        tmp = Fq(FqRepr::from(0));
1876        tmp.sub_assign(&Fq(FqRepr::from(0)));
1877        assert!(tmp.is_zero());
1878
1879        tmp = Fq(FqRepr([
1880            0x98910d20877e4ada,
1881            0x940c983013f4b8ba,
1882            0xf677dc9b8345ba33,
1883            0xbef2ce6b7f577eba,
1884            0xe1ae288ac3222c44,
1885            0x5968bb602790806,
1886        ]));
1887        tmp.sub_assign(&Fq(FqRepr::from(0)));
1888        assert_eq!(
1889            tmp,
1890            Fq(FqRepr([
1891                0x98910d20877e4ada,
1892                0x940c983013f4b8ba,
1893                0xf677dc9b8345ba33,
1894                0xbef2ce6b7f577eba,
1895                0xe1ae288ac3222c44,
1896                0x5968bb602790806
1897            ]))
1898        );
1899    }
1900    let mut rng = rand_xorshift::XorShiftRng::from_seed([
1901        0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06, 0xbc,
1902        0xe5,
1903    ]);
1904    for _ in 0..1000 {
1905        // Ensure that (a - b) + (b - a) = 0.
1906        let a = Fq::random(&mut rng);
1907        let b = Fq::random(&mut rng);
1908
1909        let mut tmp1 = a;
1910        tmp1.sub_assign(&b);
1911
1912        let mut tmp2 = b;
1913        tmp2.sub_assign(&a);
1914
1915        tmp1.add_assign(&tmp2);
1916        assert!(tmp1.is_zero());
1917    }
1918}
1919
1920#[test]
1921fn test_fq_mul_assign() {
1922    let mut tmp = Fq(FqRepr([
1923        0xcc6200000020aa8a,
1924        0x422800801dd8001a,
1925        0x7f4f5e619041c62c,
1926        0x8a55171ac70ed2ba,
1927        0x3f69cc3a3d07d58b,
1928        0xb972455fd09b8ef,
1929    ]));
1930    tmp.mul_assign(&Fq(FqRepr([
1931        0x329300000030ffcf,
1932        0x633c00c02cc40028,
1933        0xbef70d925862a942,
1934        0x4f7fa2a82a963c17,
1935        0xdf1eb2575b8bc051,
1936        0x1162b680fb8e9566,
1937    ])));
1938    assert!(
1939        tmp == Fq(FqRepr([
1940            0x9dc4000001ebfe14,
1941            0x2850078997b00193,
1942            0xa8197f1abb4d7bf,
1943            0xc0309573f4bfe871,
1944            0xf48d0923ffaf7620,
1945            0x11d4b58c7a926e66
1946        ]))
1947    );
1948    let mut rng = rand_xorshift::XorShiftRng::from_seed([
1949        0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06, 0xbc,
1950        0xe5,
1951    ]);
1952    for _ in 0..1000000 {
1953        // Ensure that (a * b) * c = a * (b * c)
1954        let a = Fq::random(&mut rng);
1955        let b = Fq::random(&mut rng);
1956        let c = Fq::random(&mut rng);
1957
1958        let mut tmp1 = a;
1959        tmp1.mul_assign(&b);
1960        tmp1.mul_assign(&c);
1961
1962        let mut tmp2 = b;
1963        tmp2.mul_assign(&c);
1964        tmp2.mul_assign(&a);
1965
1966        assert_eq!(tmp1, tmp2);
1967    }
1968
1969    for _ in 0..1000000 {
1970        // Ensure that r * (a + b + c) = r*a + r*b + r*c
1971
1972        let r = Fq::random(&mut rng);
1973        let mut a = Fq::random(&mut rng);
1974        let mut b = Fq::random(&mut rng);
1975        let mut c = Fq::random(&mut rng);
1976
1977        let mut tmp1 = a;
1978        tmp1.add_assign(&b);
1979        tmp1.add_assign(&c);
1980        tmp1.mul_assign(&r);
1981
1982        a.mul_assign(&r);
1983        b.mul_assign(&r);
1984        c.mul_assign(&r);
1985
1986        a.add_assign(&b);
1987        a.add_assign(&c);
1988
1989        assert_eq!(tmp1, a);
1990    }
1991}
1992
1993#[test]
1994fn test_fq_squaring() {
1995    let mut a = Fq(FqRepr([
1996        0xffffffffffffffff,
1997        0xffffffffffffffff,
1998        0xffffffffffffffff,
1999        0xffffffffffffffff,
2000        0xffffffffffffffff,
2001        0x19ffffffffffffff,
2002    ]));
2003    assert!(a.is_valid());
2004    a.square();
2005    assert_eq!(
2006        a,
2007        Fq::from_repr(FqRepr([
2008            0x1cfb28fe7dfbbb86,
2009            0x24cbe1731577a59,
2010            0xcce1d4edc120e66e,
2011            0xdc05c659b4e15b27,
2012            0x79361e5a802c6a23,
2013            0x24bcbe5d51b9a6f
2014        ]))
2015        .unwrap()
2016    );
2017
2018    let mut rng = rand_xorshift::XorShiftRng::from_seed([
2019        0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06, 0xbc,
2020        0xe5,
2021    ]);
2022    for _ in 0..1000000 {
2023        // Ensure that (a * a) = a^2
2024        let a = Fq::random(&mut rng);
2025
2026        let mut tmp = a;
2027        tmp.square();
2028
2029        let mut tmp2 = a;
2030        tmp2.mul_assign(&a);
2031
2032        assert_eq!(tmp, tmp2);
2033    }
2034}
2035
2036#[test]
2037fn test_fq_inverse() {
2038    assert!(Fq::zero().inverse().is_none());
2039
2040    let mut rng = rand_xorshift::XorShiftRng::from_seed([
2041        0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06, 0xbc,
2042        0xe5,
2043    ]);
2044    let one = Fq::one();
2045
2046    for _ in 0..1000 {
2047        // Ensure that a * a^-1 = 1
2048        let mut a = Fq::random(&mut rng);
2049        let ainv = a.inverse().unwrap();
2050        a.mul_assign(&ainv);
2051        assert_eq!(a, one);
2052    }
2053}
2054
2055#[test]
2056fn test_fq_double() {
2057    let mut rng = rand_xorshift::XorShiftRng::from_seed([
2058        0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06, 0xbc,
2059        0xe5,
2060    ]);
2061    for _ in 0..1000 {
2062        // Ensure doubling a is equivalent to adding a to itself.
2063        let mut a = Fq::random(&mut rng);
2064        let mut b = a;
2065        b.add_assign(&a);
2066        a.double();
2067        assert_eq!(a, b);
2068    }
2069}
2070
2071#[test]
2072fn test_fq_negate() {
2073    {
2074        let mut a = Fq::zero();
2075        a.negate();
2076
2077        assert!(a.is_zero());
2078    }
2079
2080    let mut rng = rand_xorshift::XorShiftRng::from_seed([
2081        0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06, 0xbc,
2082        0xe5,
2083    ]);
2084    for _ in 0..1000 {
2085        // Ensure (a - (-a)) = 0.
2086        let mut a = Fq::random(&mut rng);
2087        let mut b = a;
2088        b.negate();
2089        a.add_assign(&b);
2090
2091        assert!(a.is_zero());
2092    }
2093}
2094
2095#[test]
2096fn test_fq_pow() {
2097    let mut rng = rand_xorshift::XorShiftRng::from_seed([
2098        0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06, 0xbc,
2099        0xe5,
2100    ]);
2101    for i in 0..1000 {
2102        // Exponentiate by various small numbers and ensure it consists with repeated
2103        // multiplication.
2104        let a = Fq::random(&mut rng);
2105        let target = a.pow(&[i]);
2106        let mut c = Fq::one();
2107        for _ in 0..i {
2108            c.mul_assign(&a);
2109        }
2110        assert_eq!(c, target);
2111    }
2112
2113    for _ in 0..1000 {
2114        // Exponentiating by the modulus should have no effect in a prime field.
2115        let a = Fq::random(&mut rng);
2116
2117        assert_eq!(a, a.pow(Fq::char()));
2118    }
2119}
2120
2121#[test]
2122fn test_fq_sqrt() {
2123    use ff::SqrtField;
2124    let mut rng = rand_xorshift::XorShiftRng::from_seed([
2125        0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06, 0xbc,
2126        0xe5,
2127    ]);
2128    assert_eq!(Fq::zero().sqrt().unwrap(), Fq::zero());
2129
2130    for _ in 0..1000 {
2131        // Ensure sqrt(a^2) = a or -a
2132        let a = Fq::random(&mut rng);
2133        let mut nega = a;
2134        nega.negate();
2135        let mut b = a;
2136        b.square();
2137
2138        let b = b.sqrt().unwrap();
2139
2140        assert!(a == b || nega == b);
2141    }
2142
2143    for _ in 0..1000 {
2144        // Ensure sqrt(a)^2 = a for random a
2145        let a = Fq::random(&mut rng);
2146
2147        if let Some(mut tmp) = a.sqrt() {
2148            tmp.square();
2149
2150            assert_eq!(a, tmp);
2151        }
2152    }
2153}
2154
2155#[test]
2156fn test_fq_from_into_repr() {
2157    // q + 1 should not be in the field
2158    assert!(Fq::from_repr(FqRepr([
2159        0xb9feffffffffaaac,
2160        0x1eabfffeb153ffff,
2161        0x6730d2a0f6b0f624,
2162        0x64774b84f38512bf,
2163        0x4b1ba7b6434bacd7,
2164        0x1a0111ea397fe69a
2165    ]))
2166    .is_err());
2167
2168    // q should not be in the field
2169    assert!(Fq::from_repr(Fq::char()).is_err());
2170
2171    // Multiply some arbitrary representations to see if the result is as expected.
2172    let a = FqRepr([
2173        0x4a49dad4ff6cde2d,
2174        0xac62a82a8f51cd50,
2175        0x2b1f41ab9f36d640,
2176        0x908a387f480735f1,
2177        0xae30740c08a875d7,
2178        0x6c80918a365ef78,
2179    ]);
2180    let mut a_fq = Fq::from_repr(a).unwrap();
2181    let b = FqRepr([
2182        0xbba57917c32f0cf0,
2183        0xe7f878cf87f05e5d,
2184        0x9498b4292fd27459,
2185        0xd59fd94ee4572cfa,
2186        0x1f607186d5bb0059,
2187        0xb13955f5ac7f6a3,
2188    ]);
2189    let b_fq = Fq::from_repr(b).unwrap();
2190    let c = FqRepr([
2191        0xf5f70713b717914c,
2192        0x355ea5ac64cbbab1,
2193        0xce60dd43417ec960,
2194        0xf16b9d77b0ad7d10,
2195        0xa44c204c1de7cdb7,
2196        0x1684487772bc9a5a,
2197    ]);
2198    a_fq.mul_assign(&b_fq);
2199    assert_eq!(a_fq.into_repr(), c);
2200
2201    // Zero should be in the field.
2202    assert!(Fq::from_repr(FqRepr::from(0)).unwrap().is_zero());
2203    let mut rng = rand_xorshift::XorShiftRng::from_seed([
2204        0x59, 0x62, 0xbe, 0x5d, 0x76, 0x3d, 0x31, 0x8d, 0x17, 0xdb, 0x37, 0x32, 0x54, 0x06, 0xbc,
2205        0xe5,
2206    ]);
2207    for _ in 0..1000 {
2208        // Try to turn Fq elements into representations and back again, and compare.
2209        let a = Fq::random(&mut rng);
2210        let a_repr = a.into_repr();
2211        let b_repr = FqRepr::from(a);
2212        assert_eq!(a_repr, b_repr);
2213        let a_again = Fq::from_repr(a_repr).unwrap();
2214
2215        assert_eq!(a, a_again);
2216    }
2217}
2218
2219#[test]
2220fn test_fq_repr_display() {
2221    assert_eq!(
2222        format!("{}", FqRepr([0xa956babf9301ea24, 0x39a8f184f3535c7b, 0xb38d35b3f6779585, 0x676cc4eef4c46f2c, 0xb1d4aad87651e694, 0x1947f0d5f4fe325a])),
2223        "0x1947f0d5f4fe325ab1d4aad87651e694676cc4eef4c46f2cb38d35b3f677958539a8f184f3535c7ba956babf9301ea24".to_string()
2224    );
2225    assert_eq!(
2226        format!("{}", FqRepr([0xb4171485fd8622dd, 0x864229a6edec7ec5, 0xc57f7bdcf8dfb707, 0x6db7ff0ecea4584a, 0xf8d8578c4a57132d, 0x6eb66d42d9fcaaa])),
2227        "0x06eb66d42d9fcaaaf8d8578c4a57132d6db7ff0ecea4584ac57f7bdcf8dfb707864229a6edec7ec5b4171485fd8622dd".to_string()
2228    );
2229    assert_eq!(
2230        format!("{}", FqRepr([0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff, 0xffffffffffffffff])),
2231        "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff".to_string()
2232    );
2233    assert_eq!(
2234        format!("{}", FqRepr([0, 0, 0, 0, 0, 0])),
2235        "0x000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000".to_string()
2236    );
2237}
2238
2239#[test]
2240fn test_fq_display() {
2241    assert_eq!(
2242        format!("{}", Fq::from_repr(FqRepr([0xa956babf9301ea24, 0x39a8f184f3535c7b, 0xb38d35b3f6779585, 0x676cc4eef4c46f2c, 0xb1d4aad87651e694, 0x1947f0d5f4fe325a])).unwrap()),
2243        "Fq(0x1947f0d5f4fe325ab1d4aad87651e694676cc4eef4c46f2cb38d35b3f677958539a8f184f3535c7ba956babf9301ea24)".to_string()
2244    );
2245    assert_eq!(
2246        format!("{}", Fq::from_repr(FqRepr([0xe28e79396ac2bbf8, 0x413f6f7f06ea87eb, 0xa4b62af4a792a689, 0xb7f89f88f59c1dc5, 0x9a551859b1e43a9a, 0x6c9f5a1060de974])).unwrap()),
2247        "Fq(0x06c9f5a1060de9749a551859b1e43a9ab7f89f88f59c1dc5a4b62af4a792a689413f6f7f06ea87ebe28e79396ac2bbf8)".to_string()
2248    );
2249}
2250
2251#[test]
2252fn test_fq_num_bits() {
2253    assert_eq!(Fq::NUM_BITS, 381);
2254    assert_eq!(Fq::CAPACITY, 380);
2255}
2256
2257#[test]
2258fn test_fq_root_of_unity() {
2259    use ff::SqrtField;
2260
2261    assert_eq!(Fq::S, 1);
2262    assert_eq!(
2263        Fq::multiplicative_generator(),
2264        Fq::from_repr(FqRepr::from(2)).unwrap()
2265    );
2266    assert_eq!(
2267        Fq::multiplicative_generator().pow([
2268            0xdcff7fffffffd555,
2269            0xf55ffff58a9ffff,
2270            0xb39869507b587b12,
2271            0xb23ba5c279c2895f,
2272            0x258dd3db21a5d66b,
2273            0xd0088f51cbff34d
2274        ]),
2275        Fq::root_of_unity()
2276    );
2277    assert_eq!(Fq::root_of_unity().pow([1 << Fq::S]), Fq::one());
2278    assert!(Fq::multiplicative_generator().sqrt().is_none());
2279}
2280
2281#[test]
2282fn fq_field_tests() {
2283    ::tests::field::random_field_tests::<Fq>();
2284    ::tests::field::random_sqrt_tests::<Fq>();
2285    ::tests::field::random_frobenius_tests::<Fq, _>(Fq::char(), 13);
2286    ::tests::field::from_str_tests::<Fq>();
2287}
2288
2289#[test]
2290fn test_fq_ordering() {
2291    // FqRepr's ordering is well-tested, but we still need to make sure the Fq
2292    // elements aren't being compared in Montgomery form.
2293    for i in 0..100 {
2294        assert!(
2295            Fq::from_repr(FqRepr::from(i + 1)).unwrap() > Fq::from_repr(FqRepr::from(i)).unwrap()
2296        );
2297    }
2298}
2299
2300#[test]
2301fn fq_repr_tests() {
2302    ::tests::repr::random_repr_tests::<Fq, FqRepr>();
2303}
2304
2305#[test]
2306fn test_fq_legendre() {
2307    use ff::LegendreSymbol::*;
2308    use ff::SqrtField;
2309
2310    assert_eq!(QuadraticResidue, Fq::one().legendre());
2311    assert_eq!(Zero, Fq::zero().legendre());
2312
2313    assert_eq!(
2314        QuadraticNonResidue,
2315        Fq::from_repr(FqRepr::from(2)).unwrap().legendre()
2316    );
2317    assert_eq!(
2318        QuadraticResidue,
2319        Fq::from_repr(FqRepr::from(4)).unwrap().legendre()
2320    );
2321
2322    let e = FqRepr([
2323        0x52a112f249778642,
2324        0xd0bedb989b7991f,
2325        0xdad3b6681aa63c05,
2326        0xf2efc0bb4721b283,
2327        0x6057a98f18c24733,
2328        0x1022c2fd122889e4,
2329    ]);
2330    assert_eq!(QuadraticNonResidue, Fq::from_repr(e).unwrap().legendre());
2331    let e = FqRepr([
2332        0x6dae594e53a96c74,
2333        0x19b16ca9ba64b37b,
2334        0x5c764661a59bfc68,
2335        0xaa346e9b31c60a,
2336        0x346059f9d87a9fa9,
2337        0x1d61ac6bfd5c88b,
2338    ]);
2339    assert_eq!(QuadraticResidue, Fq::from_repr(e).unwrap().legendre());
2340}
2341
2342#[test]
2343fn test_fq_hash_to_field_xof_shake128() {
2344    use hash_to_field::{hash_to_field, ExpandMsgXof};
2345    use sha3::Shake128;
2346
2347    let u = hash_to_field::<Fq, ExpandMsgXof<Shake128>>(b"hello world", b"asdfqwerzxcv", 5);
2348    let expect = FqRepr([
2349        0x24606c02a2832651u64,
2350        0x938bdda212c48cebu64,
2351        0x1efda56062ec419eu64,
2352        0x56875b0494cf23c3u64,
2353        0x949e3a98626b3315u64,
2354        0xc26e7d7774840efu64,
2355    ]);
2356    assert_eq!(u[0], Fq::from_repr(expect).unwrap());
2357    let expect = FqRepr([
2358        0x9ad7d8d863f5bfd3u64,
2359        0x1a7fed20387de776u64,
2360        0x6940573ad5f2a648u64,
2361        0x836dc98edb77a5fau64,
2362        0x83a168be2975dc4cu64,
2363        0x6aa86f37d87b8cbu64,
2364    ]);
2365    assert_eq!(u[1], Fq::from_repr(expect).unwrap());
2366    let expect = FqRepr([
2367        0x15adbbe5d2882d3eu64,
2368        0xa3c020ddabea153u64,
2369        0xd5a7221a07f9c8bfu64,
2370        0xc8129a2c66578e42u64,
2371        0x4602d1382e5bb3f3u64,
2372        0x131f6d4aad6c289du64,
2373    ]);
2374    assert_eq!(u[2], Fq::from_repr(expect).unwrap());
2375    let expect = FqRepr([
2376        0xb474338a39faf63au64,
2377        0xae4f84a983c65a3bu64,
2378        0x79bdddd1f69341u64,
2379        0x837431a260f39db6u64,
2380        0x5648bea8387eacb8u64,
2381        0x10cc1407134a8b52u64,
2382    ]);
2383    assert_eq!(u[3], Fq::from_repr(expect).unwrap());
2384    let expect = FqRepr([
2385        0xde0bb37d7fd2c03u64,
2386        0x938b1e576b3bdbf5u64,
2387        0xf26d472ca0462516u64,
2388        0x32e742ce787399au64,
2389        0x3cbe0849357f259u64,
2390        0x182cd9a1a944fce4u64,
2391    ]);
2392    assert_eq!(u[4], Fq::from_repr(expect).unwrap());
2393}
2394
2395#[test]
2396fn test_fq_hash_to_field_xmd_sha256() {
2397    use hash_to_field::{hash_to_field, ExpandMsgXmd};
2398    use sha2::Sha256;
2399
2400    let u = hash_to_field::<Fq, ExpandMsgXmd<Sha256>>(b"hello world", b"asdfqwerzxcv", 5);
2401    let expect = FqRepr([
2402        0x8f07d74549bb8afau64,
2403        0x31e6bf8606ac3fb0u64,
2404        0xb9bd8770f984262fu64,
2405        0x3a164f8b239f6e05u64,
2406        0xc1232049588c34aeu64,
2407        0x19a22f099079589au64,
2408    ]);
2409    assert_eq!(u[0], Fq::from_repr(expect).unwrap());
2410    let expect = FqRepr([
2411        0xc14526c4fe3bbab1u64,
2412        0x6c3c7216400b8f66u64,
2413        0xf0cd062901da4caau64,
2414        0xf979e14776f9d2u64,
2415        0xb1fd23bf5a331884u64,
2416        0xffc3b7768d268d5u64,
2417    ]);
2418    assert_eq!(u[1], Fq::from_repr(expect).unwrap());
2419    let expect = FqRepr([
2420        0xbb3fc44aad40676du64,
2421        0xbb56dbb2eb91dbb3u64,
2422        0x54c705505e6bf0cau64,
2423        0x8654b8b21138e0bcu64,
2424        0x8717f9d046d925d6u64,
2425        0xb6c6899739c2d59u64,
2426    ]);
2427    assert_eq!(u[2], Fq::from_repr(expect).unwrap());
2428    let expect = FqRepr([
2429        0xd2747ff3500179aau64,
2430        0xa6625f23f9e6da71u64,
2431        0xdb1fdf290dd7b1adu64,
2432        0x3a55cba1ee4bc942u64,
2433        0xbcb608643d7ca236u64,
2434        0x19de74df84b63e54u64,
2435    ]);
2436    assert_eq!(u[3], Fq::from_repr(expect).unwrap());
2437    let expect = FqRepr([
2438        0x2c941e7ac5de2986u64,
2439        0x55abffcf150d8759u64,
2440        0x32bc08f24fe6d1a9u64,
2441        0x28010e76f58a9f71u64,
2442        0x278f14ec0fbf0472u64,
2443        0xdc230491783efb9u64,
2444    ]);
2445    assert_eq!(u[4], Fq::from_repr(expect).unwrap());
2446}
2447
2448#[test]
2449fn test_fq_sgn0() {
2450    assert_eq!(Fq::zero().sgn0(), Sgn0Result::NonNegative);
2451    assert_eq!(Fq::one().sgn0(), Sgn0Result::NonNegative);
2452    assert_eq!(P_M1_OVER2.sgn0(), Sgn0Result::NonNegative);
2453
2454    let p_p1_over2 = {
2455        let mut tmp = P_M1_OVER2;
2456        tmp.add_assign(&Fq::one());
2457        tmp
2458    };
2459    assert_eq!(p_p1_over2.sgn0(), Sgn0Result::Negative);
2460
2461    let neg_p_p1_over2 = {
2462        let mut tmp = p_p1_over2;
2463        tmp.negate_if(Sgn0Result::Negative);
2464        tmp
2465    };
2466    assert_eq!(neg_p_p1_over2, P_M1_OVER2);
2467
2468    let m1 = {
2469        let mut tmp = Fq::one();
2470        tmp.negate();
2471        tmp
2472    };
2473    assert_eq!(m1.sgn0(), Sgn0Result::Negative);
2474
2475    let m0 = {
2476        let mut tmp = Fq::zero();
2477        tmp.negate();
2478        tmp
2479    };
2480    assert_eq!(m0.sgn0(), Sgn0Result::NonNegative);
2481}
pairing_plus/bls12_381/fq.rs

pairing_plus/bls12_381/
fq.rs
