1#![allow(unused)]
  2use ark_ff::fields::{FftField, FftParameters, Field, LegendreSymbol, PrimeField, SquareRootField};
  3use ark_serialize::{buffer_bit_byte_size, Flags, SWFlags};
  4use ark_std::io::Cursor;
  5use rand::{Rng, SeedableRng};
  6use rand_xorshift::XorShiftRng;
  7
  8pub const ITERATIONS: u32 = 40;
  9
 10fn random_negation_tests<F: Field, R: Rng>(rng: &mut R) {
 11    for _ in 0..ITERATIONS {
 12        let a = F::rand(rng);
 13        let mut b = -a;
 14        b += &a;
 15
 16        assert!(b.is_zero());
 17    }
 18}
 19
 20fn random_addition_tests<F: Field, R: Rng>(rng: &mut R) {
 21    for _ in 0..ITERATIONS {
 22        let a = F::rand(rng);
 23        let b = F::rand(rng);
 24        let c = F::rand(rng);
 25
 26        let t0 = (a + &b) + &c; // (a + b) + c
 27
 28        let t1 = (a + &c) + &b; // (a + c) + b
 29
 30        let t2 = (b + &c) + &a; // (b + c) + a
 31
 32        assert_eq!(t0, t1);
 33        assert_eq!(t1, t2);
 34    }
 35}
 36
 37fn random_subtraction_tests<F: Field, R: Rng>(rng: &mut R) {
 38    for _ in 0..ITERATIONS {
 39        let a = F::rand(rng);
 40        let b = F::rand(rng);
 41
 42        let t0 = a - &b; // (a - b)
 43
 44        let mut t1 = b; // (b - a)
 45        t1 -= &a;
 46
 47        let mut t2 = t0; // (a - b) + (b - a) = 0
 48        t2 += &t1;
 49
 50        assert!(t2.is_zero());
 51    }
 52}
 53
 54fn random_multiplication_tests<F: Field, R: Rng>(rng: &mut R) {
 55    for _ in 0..ITERATIONS {
 56        let a = F::rand(rng);
 57        let b = F::rand(rng);
 58        let c = F::rand(rng);
 59
 60        let mut t0 = a; // (a * b) * c
 61        t0 *= &b;
 62        t0 *= &c;
 63
 64        let mut t1 = a; // (a * c) * b
 65        t1 *= &c;
 66        t1 *= &b;
 67
 68        let mut t2 = b; // (b * c) * a
 69        t2 *= &c;
 70        t2 *= &a;
 71
 72        assert_eq!(t0, t1);
 73        assert_eq!(t1, t2);
 74    }
 75}
 76
 77fn random_inversion_tests<F: Field, R: Rng>(rng: &mut R) {
 78    assert!(F::zero().inverse().is_none());
 79
 80    for _ in 0..ITERATIONS {
 81        let mut a = F::rand(rng);
 82        let b = a.inverse().unwrap(); // probablistically nonzero
 83        a *= &b;
 84
 85        assert_eq!(a, F::one());
 86    }
 87}
 88
 89fn random_doubling_tests<F: Field, R: Rng>(rng: &mut R) {
 90    for _ in 0..ITERATIONS {
 91        let mut a = F::rand(rng);
 92        let mut b = a;
 93        a += &b;
 94        b.double_in_place();
 95
 96        assert_eq!(a, b);
 97    }
 98}
 99
100fn random_squaring_tests<F: Field, R: Rng>(rng: &mut R) {
101    for _ in 0..ITERATIONS {
102        let mut a = F::rand(rng);
103        let mut b = a;
104        a *= &b;
105        b.square_in_place();
106
107        assert_eq!(a, b);
108    }
109}
110
111fn random_expansion_tests<F: Field, R: Rng>(rng: &mut R) {
112    for _ in 0..ITERATIONS {
113        // Compare (a + b)(c + d) and (a*c + b*c + a*d + b*d)
114
115        let a = F::rand(rng);
116        let b = F::rand(rng);
117        let c = F::rand(rng);
118        let d = F::rand(rng);
119
120        let mut t0 = a;
121        t0 += &b;
122        let mut t1 = c;
123        t1 += &d;
124        t0 *= &t1;
125
126        let mut t2 = a;
127        t2 *= &c;
128        let mut t3 = b;
129        t3 *= &c;
130        let mut t4 = a;
131        t4 *= &d;
132        let mut t5 = b;
133        t5 *= &d;
134
135        t2 += &t3;
136        t2 += &t4;
137        t2 += &t5;
138
139        assert_eq!(t0, t2);
140    }
141
142    for _ in 0..ITERATIONS {
143        // Compare (a + b)c and (a*c + b*c)
144
145        let a = F::rand(rng);
146        let b = F::rand(rng);
147        let c = F::rand(rng);
148
149        let t0 = (a + &b) * &c;
150        let t2 = a * &c + &(b * &c);
151
152        assert_eq!(t0, t2);
153    }
154}
155
156fn random_field_tests<F: Field>() {
157    let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
158
159    random_negation_tests::<F, _>(&mut rng);
160    random_addition_tests::<F, _>(&mut rng);
161    random_subtraction_tests::<F, _>(&mut rng);
162    random_multiplication_tests::<F, _>(&mut rng);
163    random_inversion_tests::<F, _>(&mut rng);
164    random_doubling_tests::<F, _>(&mut rng);
165    random_squaring_tests::<F, _>(&mut rng);
166    random_expansion_tests::<F, _>(&mut rng);
167
168    assert!(F::zero().is_zero());
169    {
170        let z = -F::zero();
171        assert!(z.is_zero());
172    }
173
174    assert!(F::zero().inverse().is_none());
175
176    // Multiplication by zero
177    {
178        let a = F::rand(&mut rng) * &F::zero();
179        assert!(a.is_zero());
180    }
181
182    // Addition by zero
183    {
184        let mut a = F::rand(&mut rng);
185        let copy = a;
186        a += &F::zero();
187        assert_eq!(a, copy);
188    }
189}
190
191fn random_sqrt_tests<F: SquareRootField>() {
192    let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
193
194    for _ in 0..ITERATIONS {
195        let a = F::rand(&mut rng);
196        let b = a.square();
197        assert_eq!(b.legendre(), LegendreSymbol::QuadraticResidue);
198
199        let b = b.sqrt().unwrap();
200        assert!(a == b || a == -b);
201    }
202
203    let mut c = F::one();
204    for _ in 0..ITERATIONS {
205        let mut b = c.square();
206        assert_eq!(b.legendre(), LegendreSymbol::QuadraticResidue);
207
208        b = b.sqrt().unwrap();
209
210        if b != c {
211            b = -b;
212        }
213
214        assert_eq!(b, c);
215
216        c += &F::one();
217    }
218}
219
220pub fn from_str_test<F: PrimeField>() {
221    {
222        let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
223
224        for _ in 0..ITERATIONS {
225            let n: u64 = rng.gen();
226
227            let a = F::from_str(&ark_std::format!("{}", n))
228                .map_err(|_| ())
229                .unwrap();
230            let b = F::from_repr(n.into()).unwrap();
231
232            assert_eq!(a, b);
233        }
234    }
235
236    assert!(F::from_str("").is_err());
237    assert!(F::from_str("0").map_err(|_| ()).unwrap().is_zero());
238    assert!(F::from_str("00").is_err());
239    assert!(F::from_str("00000000000").is_err());
240}
241
242pub fn field_test<F: Field>(a: F, b: F) {
243    let zero = F::zero();
244    assert_eq!(zero, zero);
245    assert_eq!(zero.is_zero(), true);
246    assert_eq!(zero.is_one(), false);
247
248    let one = F::one();
249    assert_eq!(one, one);
250    assert_eq!(one.is_zero(), false);
251    assert_eq!(one.is_one(), true);
252    assert_eq!(zero + &one, one);
253
254    let two = one + &one;
255    assert_eq!(two, two);
256    assert_ne!(zero, two);
257    assert_ne!(one, two);
258
259    // a == a
260    assert_eq!(a, a);
261    // a + 0 = a
262    assert_eq!(a + &zero, a);
263    // a - 0 = a
264    assert_eq!(a - &zero, a);
265    // a - a = 0
266    assert_eq!(a - &a, zero);
267    // 0 - a = -a
268    assert_eq!(zero - &a, -a);
269    // a.double() = a + a
270    assert_eq!(a.double(), a + &a);
271    // b.double() = b + b
272    assert_eq!(b.double(), b + &b);
273    // a + b = b + a
274    assert_eq!(a + &b, b + &a);
275    // a - b = -(b - a)
276    assert_eq!(a - &b, -(b - &a));
277    // (a + b) + a = a + (b + a)
278    assert_eq!((a + &b) + &a, a + &(b + &a));
279    // (a + b).double() = (a + b) + (b + a)
280    assert_eq!((a + &b).double(), (a + &b) + &(b + &a));
281
282    // a * 0 = 0
283    assert_eq!(a * &zero, zero);
284    // a * 1 = a
285    assert_eq!(a * &one, a);
286    // a * 2 = a.double()
287    assert_eq!(a * &two, a.double());
288    // a * a^-1 = 1
289    assert_eq!(a * &a.inverse().unwrap(), one);
290    // a * a = a^2
291    assert_eq!(a * &a, a.square());
292    // a * a * a = a^3
293    assert_eq!(a * &(a * &a), a.pow([0x3, 0x0, 0x0, 0x0]));
294    // a * b = b * a
295    assert_eq!(a * &b, b * &a);
296    // (a * b) * a = a * (b * a)
297    assert_eq!((a * &b) * &a, a * &(b * &a));
298    // (a + b)^2 = a^2 + 2ab + b^2
299    assert_eq!(
300        (a + &b).square(),
301        a.square() + &((a * &b) + &(a * &b)) + &b.square()
302    );
303    // (a - b)^2 = (-(b - a))^2
304    assert_eq!((a - &b).square(), (-(b - &a)).square());
305    random_field_tests::<F>();
306}
307
308pub fn fft_field_test<F: FftField>() {
309    assert_eq!(
310        F::two_adic_root_of_unity().pow([1 << F::FftParams::TWO_ADICITY]),
311        F::one()
312    );
313
314    if let Some(small_subgroup_base) = F::FftParams::SMALL_SUBGROUP_BASE {
315        let small_subgroup_base_adicity = F::FftParams::SMALL_SUBGROUP_BASE_ADICITY.unwrap();
316        let large_subgroup_root_of_unity = F::large_subgroup_root_of_unity().unwrap();
317        assert_eq!(
318            large_subgroup_root_of_unity.pow([(1 << F::FftParams::TWO_ADICITY)
319                * (small_subgroup_base as u64).pow(small_subgroup_base_adicity)]),
320            F::one()
321        );
322
323        for i in 0..F::FftParams::TWO_ADICITY {
324            for j in 0..small_subgroup_base_adicity {
325                use core::convert::TryFrom;
326                let size = usize::try_from(1 << i as usize).unwrap()
327                    * usize::try_from((small_subgroup_base as u64).pow(j)).unwrap();
328                let root = F::get_root_of_unity(size).unwrap();
329                assert_eq!(root.pow([size as u64]), F::one());
330            }
331        }
332    } else {
333        for i in 0..F::FftParams::TWO_ADICITY {
334            let size = 1 << i;
335            let root = F::get_root_of_unity(size).unwrap();
336            assert_eq!(root.pow([size as u64]), F::one());
337        }
338    }
339}
340
341pub fn primefield_test<F: PrimeField>() {
342    from_str_test::<F>();
343    let one = F::one();
344    assert_eq!(F::from(one.into_repr()), one);
345
346    fft_field_test::<F>();
347}
348
349pub fn sqrt_field_test<F: SquareRootField>(elem: F) {
350    let square = elem.square();
351    let sqrt = square.sqrt().unwrap();
352    assert!(sqrt == elem || sqrt == -elem);
353    if let Some(sqrt) = elem.sqrt() {
354        assert!(sqrt.square() == elem || sqrt.square() == -elem);
355    }
356    random_sqrt_tests::<F>();
357}
358
359pub fn frobenius_test<F: Field, C: AsRef<[u64]>>(characteristic: C, maxpower: usize) {
360    let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
361
362    for _ in 0..ITERATIONS {
363        let a = F::rand(&mut rng);
364
365        let mut a_0 = a;
366        a_0.frobenius_map(0);
367        assert_eq!(a, a_0);
368
369        let mut a_q = a.pow(&characteristic);
370        for power in 1..maxpower {
371            let mut a_qi = a;
372            a_qi.frobenius_map(power);
373            assert_eq!(a_qi, a_q, "failed on power {}", power);
374
375            a_q = a_q.pow(&characteristic);
376        }
377    }
378}
379
380pub fn field_serialization_test<F: Field>(buf_size: usize) {
381    let mut rng = XorShiftRng::seed_from_u64(1231275789u64);
382
383    for _ in 0..ITERATIONS {
384        let a = F::rand(&mut rng);
385        {
386            let mut serialized = vec![0u8; buf_size];
387            let mut cursor = Cursor::new(&mut serialized[..]);
388            a.serialize(&mut cursor).unwrap();
389
390            let mut cursor = Cursor::new(&serialized[..]);
391            let b = F::deserialize(&mut cursor).unwrap();
392            assert_eq!(a, b);
393        }
394
395        {
396            let mut serialized = vec![0u8; a.uncompressed_size()];
397            let mut cursor = Cursor::new(&mut serialized[..]);
398            a.serialize_uncompressed(&mut cursor).unwrap();
399
400            let mut cursor = Cursor::new(&serialized[..]);
401            let b = F::deserialize_uncompressed(&mut cursor).unwrap();
402            assert_eq!(a, b);
403        }
404
405        {
406            let mut serialized = vec![0u8; buf_size];
407            let mut cursor = Cursor::new(&mut serialized[..]);
408            a.serialize_with_flags(&mut cursor, SWFlags::from_y_sign(true))
409                .unwrap();
410            let mut cursor = Cursor::new(&serialized[..]);
411            let (b, flags) = F::deserialize_with_flags::<_, SWFlags>(&mut cursor).unwrap();
412            assert_eq!(flags.is_positive(), Some(true));
413            assert!(!flags.is_infinity());
414            assert_eq!(a, b);
415        }
416
417        #[derive(Default, Clone, Copy, Debug)]
418        struct DummyFlags;
419        impl Flags for DummyFlags {
420            fn u8_bitmask(&self) -> u8 {
421                0
422            }
423
424            fn from_u8(_value: u8) -> Self {
425                DummyFlags
426            }
427
428            fn from_u8_remove_flags(_value: &mut u8) -> Self {
429                DummyFlags
430            }
431
432            fn len() -> usize {
433                200
434            }
435        }
436
437        use ark_serialize::SerializationError;
438        {
439            let mut serialized = vec![0; buf_size];
440            assert!(if let SerializationError::NotEnoughSpace = a
441                .serialize_with_flags(&mut &mut serialized[..], DummyFlags)
442                .unwrap_err()
443            {
444                true
445            } else {
446                false
447            });
448            assert!(if let SerializationError::NotEnoughSpace =
449                F::deserialize_with_flags::<_, DummyFlags>(&mut &serialized[..]).unwrap_err()
450            {
451                true
452            } else {
453                false
454            });
455        }
456
457        {
458            let mut serialized = vec![0; buf_size - 1];
459            let mut cursor = Cursor::new(&mut serialized[..]);
460            a.serialize(&mut cursor).unwrap_err();
461
462            let mut cursor = Cursor::new(&serialized[..]);
463            F::deserialize(&mut cursor).unwrap_err();
464        }
465    }
466}