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