1use ark_ff::{
  2    biginteger::{BigInteger, BigInteger384},
  3    fields::{
  4        fp6_3over2::Fp6Parameters, FftField, FftParameters, Field, Fp2Parameters, FpParameters,
  5        PrimeField, SquareRootField,
  6    },
  7    One, UniformRand, Zero,
  8};
  9use ark_serialize::{buffer_bit_byte_size, CanonicalSerialize};
 10use ark_std::rand::Rng;
 11use ark_std::test_rng;
 12use core::{
 13    cmp::Ordering,
 14    ops::{AddAssign, MulAssign, SubAssign},
 15};
 16
 17use crate::{Fq, Fq12, Fq2, Fq2Parameters, Fq6, Fq6Parameters, FqParameters, Fr};
 18
 19use ark_algebra_test_templates::fields::*;
 20
 21pub(crate) const ITERATIONS: usize = 5;
 22
 23#[test]
 24fn test_fr() {
 25    let mut rng = test_rng();
 26    for _ in 0..ITERATIONS {
 27        let a: Fr = rng.gen();
 28        let b: Fr = rng.gen();
 29        field_test(a, b);
 30        primefield_test::<Fr>();
 31        sqrt_field_test(b);
 32        let byte_size = a.serialized_size();
 33        field_serialization_test::<Fr>(byte_size);
 34    }
 35}
 36
 37#[test]
 38fn test_fq() {
 39    let mut rng = test_rng();
 40    for _ in 0..ITERATIONS {
 41        let a: Fq = rng.gen();
 42        let b: Fq = rng.gen();
 43        field_test(a, b);
 44        primefield_test::<Fq>();
 45        sqrt_field_test(a);
 46        let byte_size = a.serialized_size();
 47        let (_, buffer_size) = buffer_bit_byte_size(Fq::size_in_bits());
 48        assert_eq!(byte_size, buffer_size);
 49        field_serialization_test::<Fq>(byte_size);
 50    }
 51}
 52
 53#[test]
 54fn test_fq2() {
 55    let mut rng = test_rng();
 56    for _ in 0..ITERATIONS {
 57        let a: Fq2 = rng.gen();
 58        let b: Fq2 = rng.gen();
 59        field_test(a, b);
 60        sqrt_field_test(a);
 61    }
 62    frobenius_test::<Fq2, _>(Fq::characteristic(), 13);
 63    let byte_size = Fq2::zero().serialized_size();
 64    field_serialization_test::<Fq2>(byte_size);
 65}
 66
 67#[test]
 68fn test_fq6() {
 69    let mut rng = test_rng();
 70    for _ in 0..ITERATIONS {
 71        let g: Fq6 = rng.gen();
 72        let h: Fq6 = rng.gen();
 73        field_test(g, h);
 74    }
 75
 76    frobenius_test::<Fq6, _>(Fq::characteristic(), 13);
 77    let byte_size = Fq6::zero().serialized_size();
 78    field_serialization_test::<Fq6>(byte_size);
 79}
 80
 81#[test]
 82fn test_fq12() {
 83    let mut rng = test_rng();
 84    for _ in 0..ITERATIONS {
 85        let g: Fq12 = rng.gen();
 86        let h: Fq12 = rng.gen();
 87        field_test(g, h);
 88    }
 89    frobenius_test::<Fq12, _>(Fq::characteristic(), 13);
 90    let byte_size = Fq12::zero().serialized_size();
 91    field_serialization_test::<Fq12>(byte_size);
 92}
 93
 94#[test]
 95fn test_fq_repr_from() {
 96    assert_eq!(
 97        BigInteger384::from(100),
 98        BigInteger384([100, 0, 0, 0, 0, 0])
 99    );
100}
101
102#[test]
103fn test_fq_repr_is_odd() {
104    assert!(!BigInteger384::from(0).is_odd());
105    assert!(BigInteger384::from(0).is_even());
106    assert!(BigInteger384::from(1).is_odd());
107    assert!(!BigInteger384::from(1).is_even());
108    assert!(!BigInteger384::from(324834872).is_odd());
109    assert!(BigInteger384::from(324834872).is_even());
110    assert!(BigInteger384::from(324834873).is_odd());
111    assert!(!BigInteger384::from(324834873).is_even());
112}
113
114#[test]
115fn test_fq_repr_is_zero() {
116    assert!(BigInteger384::from(0).is_zero());
117    assert!(!BigInteger384::from(1).is_zero());
118    assert!(!BigInteger384([0, 0, 0, 0, 1, 0]).is_zero());
119}
120
121#[test]
122fn test_fq_repr_num_bits() {
123    let mut a = BigInteger384::from(0);
124    assert_eq!(0, a.num_bits());
125    a = BigInteger384::from(1);
126    for i in 1..385 {
127        assert_eq!(i, a.num_bits());
128        a.mul2();
129    }
130    assert_eq!(0, a.num_bits());
131}
132
133#[test]
134fn test_fq_add_assign() {
135    // Test associativity
136
137    let mut rng = test_rng();
138
139    for _ in 0..1000 {
140        // Generate a, b, c and ensure (a + b) + c == a + (b + c).
141        let a = Fq::rand(&mut rng);
142        let b = Fq::rand(&mut rng);
143        let c = Fq::rand(&mut rng);
144
145        let mut tmp1 = a;
146        tmp1.add_assign(&b);
147        tmp1.add_assign(&c);
148
149        let mut tmp2 = b;
150        tmp2.add_assign(&c);
151        tmp2.add_assign(&a);
152
153        assert_eq!(tmp1, tmp2);
154    }
155}
156
157#[test]
158fn test_fq_sub_assign() {
159    let mut rng = test_rng();
160
161    for _ in 0..1000 {
162        // Ensure that (a - b) + (b - a) = 0.
163        let a = Fq::rand(&mut rng);
164        let b = Fq::rand(&mut rng);
165
166        let mut tmp1 = a;
167        tmp1.sub_assign(&b);
168
169        let mut tmp2 = b;
170        tmp2.sub_assign(&a);
171
172        tmp1.add_assign(&tmp2);
173        assert!(tmp1.is_zero());
174    }
175}
176
177#[test]
178fn test_fq_mul_assign() {
179    let mut rng = test_rng();
180
181    for _ in 0..1000000 {
182        // Ensure that (a * b) * c = a * (b * c)
183        let a = Fq::rand(&mut rng);
184        let b = Fq::rand(&mut rng);
185        let c = Fq::rand(&mut rng);
186
187        let mut tmp1 = a;
188        tmp1.mul_assign(&b);
189        tmp1.mul_assign(&c);
190
191        let mut tmp2 = b;
192        tmp2.mul_assign(&c);
193        tmp2.mul_assign(&a);
194
195        assert_eq!(tmp1, tmp2);
196    }
197
198    for _ in 0..1000000 {
199        // Ensure that r * (a + b + c) = r*a + r*b + r*c
200
201        let r = Fq::rand(&mut rng);
202        let mut a = Fq::rand(&mut rng);
203        let mut b = Fq::rand(&mut rng);
204        let mut c = Fq::rand(&mut rng);
205
206        let mut tmp1 = a;
207        tmp1.add_assign(&b);
208        tmp1.add_assign(&c);
209        tmp1.mul_assign(&r);
210
211        a.mul_assign(&r);
212        b.mul_assign(&r);
213        c.mul_assign(&r);
214
215        a.add_assign(&b);
216        a.add_assign(&c);
217
218        assert_eq!(tmp1, a);
219    }
220}
221
222#[test]
223fn test_fq_squaring() {
224    let mut rng = test_rng();
225
226    for _ in 0..1000000 {
227        // Ensure that (a * a) = a^2
228        let a = Fq::rand(&mut rng);
229
230        let mut tmp = a;
231        tmp.square_in_place();
232
233        let mut tmp2 = a;
234        tmp2.mul_assign(&a);
235
236        assert_eq!(tmp, tmp2);
237    }
238}
239
240#[test]
241fn test_fq_inverse() {
242    assert!(Fq::zero().inverse().is_none());
243
244    let mut rng = test_rng();
245
246    let one = Fq::one();
247
248    for _ in 0..1000 {
249        // Ensure that a * a^-1 = 1
250        let mut a = Fq::rand(&mut rng);
251        let ainv = a.inverse().unwrap();
252        a.mul_assign(&ainv);
253        assert_eq!(a, one);
254    }
255}
256
257#[test]
258fn test_fq_double_in_place() {
259    let mut rng = test_rng();
260
261    for _ in 0..1000 {
262        // Ensure doubling a is equivalent to adding a to itself.
263        let mut a = Fq::rand(&mut rng);
264        let mut b = a;
265        b.add_assign(&a);
266        a.double_in_place();
267        assert_eq!(a, b);
268    }
269}
270
271#[test]
272fn test_fq_negate() {
273    {
274        let a = -Fq::zero();
275
276        assert!(a.is_zero());
277    }
278
279    let mut rng = test_rng();
280
281    for _ in 0..1000 {
282        // Ensure (a - (-a)) = 0.
283        let mut a = Fq::rand(&mut rng);
284        let b = -a;
285        a.add_assign(&b);
286
287        assert!(a.is_zero());
288    }
289}
290
291#[test]
292fn test_fq_pow() {
293    let mut rng = test_rng();
294
295    for i in 0..1000 {
296        // Exponentiate by various small numbers and ensure it consists with repeated
297        // multiplication.
298        let a = Fq::rand(&mut rng);
299        let target = a.pow(&[i]);
300        let mut c = Fq::one();
301        for _ in 0..i {
302            c.mul_assign(&a);
303        }
304        assert_eq!(c, target);
305    }
306
307    for _ in 0..1000 {
308        // Exponentiating by the modulus should have no effect in a prime field.
309        let a = Fq::rand(&mut rng);
310
311        assert_eq!(a, a.pow(Fq::characteristic()));
312    }
313}
314
315#[test]
316fn test_fq_sqrt() {
317    let mut rng = test_rng();
318
319    assert_eq!(Fq::zero().sqrt().unwrap(), Fq::zero());
320
321    for _ in 0..1000 {
322        // Ensure sqrt(a^2) = a or -a
323        let a = Fq::rand(&mut rng);
324        let nega = -a;
325        let mut b = a;
326        b.square_in_place();
327
328        let b = b.sqrt().unwrap();
329
330        assert!(a == b || nega == b);
331    }
332
333    for _ in 0..1000 {
334        // Ensure sqrt(a)^2 = a for random a
335        let a = Fq::rand(&mut rng);
336
337        if let Some(mut tmp) = a.sqrt() {
338            tmp.square_in_place();
339
340            assert_eq!(a, tmp);
341        }
342    }
343}
344
345#[test]
346fn test_fq_num_bits() {
347    assert_eq!(FqParameters::MODULUS_BITS, 377);
348    assert_eq!(FqParameters::CAPACITY, 376);
349}
350
351#[test]
352fn test_fq_root_of_unity() {
353    assert_eq!(FqParameters::TWO_ADICITY, 46);
354    assert_eq!(
355        Fq::multiplicative_generator().pow([
356            0x7510c00000021423,
357            0x88bee82520005c2d,
358            0x67cc03d44e3c7bcd,
359            0x1701b28524ec688b,
360            0xe9185f1443ab18ec,
361            0x6b8
362        ]),
363        Fq::two_adic_root_of_unity()
364    );
365    assert_eq!(
366        Fq::two_adic_root_of_unity().pow([1 << FqParameters::TWO_ADICITY]),
367        Fq::one()
368    );
369    assert!(Fq::multiplicative_generator().sqrt().is_none());
370}
371
372#[test]
373fn test_fq_ordering() {
374    // BigInteger384's ordering is well-tested, but we still need to make sure the
375    // Fq elements aren't being compared in Montgomery form.
376    for i in 0..100 {
377        assert!(Fq::from(BigInteger384::from(i + 1)) > Fq::from(BigInteger384::from(i)));
378    }
379}
380
381#[test]
382fn test_fq_legendre() {
383    use ark_ff::fields::LegendreSymbol::*;
384
385    assert_eq!(QuadraticResidue, Fq::one().legendre());
386    assert_eq!(Zero, Fq::zero().legendre());
387    assert_eq!(
388        QuadraticResidue,
389        Fq::from(BigInteger384::from(4)).legendre()
390    );
391    assert_eq!(
392        QuadraticNonResidue,
393        Fq::from(BigInteger384::from(5)).legendre()
394    );
395}
396
397#[test]
398fn test_fq2_ordering() {
399    let mut a = Fq2::new(Fq::zero(), Fq::zero());
400    let mut b = a.clone();
401
402    assert!(a.cmp(&b) == Ordering::Equal);
403    b.c0.add_assign(&Fq::one());
404    assert!(a.cmp(&b) == Ordering::Less);
405    a.c0.add_assign(&Fq::one());
406    assert!(a.cmp(&b) == Ordering::Equal);
407    b.c1.add_assign(&Fq::one());
408    assert!(a.cmp(&b) == Ordering::Less);
409    a.c0.add_assign(&Fq::one());
410    assert!(a.cmp(&b) == Ordering::Less);
411    a.c1.add_assign(&Fq::one());
412    assert!(a.cmp(&b) == Ordering::Greater);
413    b.c0.add_assign(&Fq::one());
414    assert!(a.cmp(&b) == Ordering::Equal);
415}
416
417#[test]
418fn test_fq2_basics() {
419    assert_eq!(Fq2::new(Fq::zero(), Fq::zero(),), Fq2::zero());
420    assert_eq!(Fq2::new(Fq::one(), Fq::zero(),), Fq2::one());
421    assert!(Fq2::zero().is_zero());
422    assert!(!Fq2::one().is_zero());
423    assert!(!Fq2::new(Fq::zero(), Fq::one(),).is_zero());
424}
425
426#[test]
427fn test_fq2_legendre() {
428    use ark_ff::fields::LegendreSymbol::*;
429
430    assert_eq!(Zero, Fq2::zero().legendre());
431    // i^2 = -1
432    let mut m1 = -Fq2::one();
433    assert_eq!(QuadraticResidue, m1.legendre());
434    m1 = Fq6Parameters::mul_fp2_by_nonresidue(&m1);
435    assert_eq!(QuadraticNonResidue, m1.legendre());
436}
437
438#[test]
439fn test_fq2_mul_nonresidue() {
440    let mut rng = test_rng();
441
442    let nqr = Fq2::new(Fq::zero(), Fq::one());
443
444    let quadratic_non_residue = Fq2::new(
445        Fq2Parameters::QUADRATIC_NONRESIDUE.0,
446        Fq2Parameters::QUADRATIC_NONRESIDUE.1,
447    );
448    for _ in 0..1000 {
449        let mut a = Fq2::rand(&mut rng);
450        let mut b = a;
451        a = quadratic_non_residue * &a;
452        b.mul_assign(&nqr);
453
454        assert_eq!(a, b);
455    }
456}
457
458#[test]
459fn test_fq6_mul_by_1() {
460    let mut rng = test_rng();
461
462    for _ in 0..1000 {
463        let c1 = Fq2::rand(&mut rng);
464        let mut a = Fq6::rand(&mut rng);
465        let mut b = a;
466
467        a.mul_by_1(&c1);
468        b.mul_assign(&Fq6::new(Fq2::zero(), c1, Fq2::zero()));
469
470        assert_eq!(a, b);
471    }
472}
473
474#[test]
475fn test_fq6_mul_by_01() {
476    let mut rng = test_rng();
477
478    for _ in 0..1000 {
479        let c0 = Fq2::rand(&mut rng);
480        let c1 = Fq2::rand(&mut rng);
481        let mut a = Fq6::rand(&mut rng);
482        let mut b = a;
483
484        a.mul_by_01(&c0, &c1);
485        b.mul_assign(&Fq6::new(c0, c1, Fq2::zero()));
486
487        assert_eq!(a, b);
488    }
489}
490
491#[test]
492fn test_fq12_mul_by_014() {
493    let mut rng = test_rng();
494
495    for _ in 0..1000 {
496        let c0 = Fq2::rand(&mut rng);
497        let c1 = Fq2::rand(&mut rng);
498        let c5 = Fq2::rand(&mut rng);
499        let mut a = Fq12::rand(&mut rng);
500        let mut b = a;
501
502        a.mul_by_014(&c0, &c1, &c5);
503        b.mul_assign(&Fq12::new(
504            Fq6::new(c0, c1, Fq2::zero()),
505            Fq6::new(Fq2::zero(), c5, Fq2::zero()),
506        ));
507
508        assert_eq!(a, b);
509    }
510}
511
512#[test]
513fn test_fq12_mul_by_034() {
514    let mut rng = test_rng();
515
516    for _ in 0..1000 {
517        let c0 = Fq2::rand(&mut rng);
518        let c3 = Fq2::rand(&mut rng);
519        let c4 = Fq2::rand(&mut rng);
520        let mut a = Fq12::rand(&mut rng);
521        let mut b = a;
522
523        a.mul_by_034(&c0, &c3, &c4);
524        b.mul_assign(&Fq12::new(
525            Fq6::new(c0, Fq2::zero(), Fq2::zero()),
526            Fq6::new(c3, c4, Fq2::zero()),
527        ));
528
529        assert_eq!(a, b);
530    }
531}