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