ark-curves-cherry-picked/bn254/src/fields/tests.rs
bn254/src/fields/tests.rsRaw
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::rand::Rng;
11use ark_std::test_rng;
12use core::{
13 cmp::Ordering,
14 ops::{AddAssign, MulAssign, SubAssign},
15};
16
17use crate::{Fq, Fq12, Fq2, Fq6, Fq6Parameters, FqParameters, Fr};
18use ark_algebra_test_templates::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 = ark_std::test_rng();
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 = ark_std::test_rng();
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 = ark_std::test_rng();
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 = ark_std::test_rng();
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 = ark_std::test_rng();
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 = ark_std::test_rng();
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 = ark_std::test_rng();
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 = ark_std::test_rng();
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 = ark_std::test_rng();
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 = ark_std::test_rng();
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 = ark_std::test_rng();
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 = ark_std::test_rng();
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 = ark_std::test_rng();
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}