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