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