ff_group_tests/
field.rs

1use rand_core::RngCore;
2use subtle::Choice;
3use group::ff::Field;
4
5/// Perform basic tests on equality.
6pub fn test_eq<F: Field>() {
7  let zero = F::ZERO;
8  let one = F::ONE;
9
10  assert!(zero != one, "0 == 1");
11  assert!(!bool::from(zero.ct_eq(&one)), "0 ct_eq 1");
12
13  assert_eq!(zero, F::ZERO, "0 != 0");
14  assert!(bool::from(zero.ct_eq(&F::ZERO)), "0 !ct_eq 0");
15
16  assert_eq!(one, F::ONE, "1 != 1");
17  assert!(bool::from(one.ct_eq(&F::ONE)), "1 !ct_eq 1");
18}
19
20/// Verify conditional selection works. Doesn't verify it's actually constant time.
21pub fn test_conditional_select<F: Field>() {
22  let zero = F::ZERO;
23  let one = F::ONE;
24  assert_eq!(F::conditional_select(&zero, &one, 0.into()), zero, "couldn't select when false");
25  assert_eq!(F::conditional_select(&zero, &one, 1.into()), one, "couldn't select when true");
26}
27
28/// Perform basic tests on addition.
29pub fn test_add<F: Field>() {
30  assert_eq!(F::ZERO + F::ZERO, F::ZERO, "0 + 0 != 0");
31  assert_eq!(F::ZERO + F::ONE, F::ONE, "0 + 1 != 1");
32  assert_eq!(F::ONE + F::ZERO, F::ONE, "1 + 0 != 1");
33  // Only PrimeField offers From<u64>
34  // Accordingly, we assume either double or addition is correct
35  // They either have to be matchingly correct or matchingly incorrect, yet we can't
36  // reliably determine that here
37  assert_eq!(F::ONE + F::ONE, F::ONE.double(), "1 + 1 != 2");
38}
39
40/// Perform basic tests on sum.
41pub fn test_sum<F: Field>() {
42  assert_eq!((&[] as &[F]).iter().sum::<F>(), F::ZERO, "[].sum() != 0");
43  assert_eq!([F::ZERO].iter().sum::<F>(), F::ZERO, "[0].sum() != 0");
44  assert_eq!([F::ONE].iter().sum::<F>(), F::ONE, "[1].sum() != 1");
45
46  let two = F::ONE + F::ONE;
47  assert_eq!([F::ONE, F::ONE].iter().sum::<F>(), two, "[1, 1].sum() != 2");
48  assert_eq!([two, F::ONE].iter().sum::<F>(), two + F::ONE, "[2, 1].sum() != 3");
49  assert_eq!([two, F::ZERO, F::ONE].iter().sum::<F>(), two + F::ONE, "[2, 0, 1].sum() != 3");
50}
51
52/// Perform basic tests on subtraction.
53pub fn test_sub<F: Field>() {
54  #[allow(clippy::eq_op)]
55  let expr = F::ZERO - F::ZERO;
56  assert_eq!(expr, F::ZERO, "0 - 0 != 0");
57  assert_eq!(F::ONE - F::ZERO, F::ONE, "1 - 0 != 1");
58  #[allow(clippy::eq_op)]
59  let expr = F::ONE - F::ONE;
60  assert_eq!(expr, F::ZERO, "1 - 1 != 0");
61}
62
63/// Perform basic tests on negation.
64pub fn test_neg<F: Field>() {
65  assert_eq!(-F::ZERO, F::ZERO, "-0 != 0");
66  assert_eq!(-(-F::ONE), F::ONE, "-(-1) != 1");
67  assert_eq!(F::ONE + (-F::ONE), F::ZERO, "1 + -1 != 0");
68  assert_eq!(F::ONE - (-F::ONE), F::ONE.double(), "1 - -1 != 2");
69}
70
71/// Perform basic tests on multiplication.
72pub fn test_mul<F: Field>() {
73  assert_eq!(F::ZERO * F::ZERO, F::ZERO, "0 * 0 != 0");
74  assert_eq!(F::ONE * F::ZERO, F::ZERO, "1 * 0 != 0");
75  assert_eq!(F::ONE * F::ONE, F::ONE, "1 * 1 != 1");
76  let two = F::ONE.double();
77  assert_eq!(two * (two + F::ONE), two + two + two, "2 * 3 != 6");
78}
79
80/// Perform basic tests on product.
81pub fn test_product<F: Field>() {
82  assert_eq!((&[] as &[F]).iter().product::<F>(), F::ONE, "[].product() != 1");
83  assert_eq!([F::ZERO].iter().product::<F>(), F::ZERO, "[0].product() != 0");
84  assert_eq!([F::ONE].iter().product::<F>(), F::ONE, "[1].product() != 1");
85
86  assert_eq!([F::ONE, F::ONE].iter().product::<F>(), F::ONE, "[1, 1].product() != 2");
87  let two = F::ONE + F::ONE;
88  assert_eq!([two, F::ONE].iter().product::<F>(), two, "[2, 1].product() != 2");
89  assert_eq!([two, two].iter().product::<F>(), two + two, "[2, 2].product() != 4");
90  assert_eq!([two, two, F::ONE].iter().product::<F>(), two + two, "[2, 2, 1].product() != 4");
91  assert_eq!([two, F::ZERO, F::ONE].iter().product::<F>(), F::ZERO, "[2, 0, 1].product() != 0");
92}
93
94/// Perform basic tests on the square function.
95pub fn test_square<F: Field>() {
96  assert_eq!(F::ZERO.square(), F::ZERO, "0^2 != 0");
97  assert_eq!(F::ONE.square(), F::ONE, "1^2 != 1");
98  let two = F::ONE.double();
99  assert_eq!(two.square(), two + two, "2^2 != 4");
100  let three = two + F::ONE;
101  assert_eq!(three.square(), three * three, "3^2 != 9");
102}
103
104/// Perform basic tests on the invert function.
105pub fn test_invert<F: Field>() {
106  assert!(bool::from(F::ZERO.invert().is_none()), "0.invert() is some");
107  assert_eq!(F::ONE.invert().unwrap(), F::ONE, "1.invert() != 1");
108
109  let two = F::ONE.double();
110  let three = two + F::ONE;
111  assert_eq!(two * three.invert().unwrap() * three, two, "2 * 3.invert() * 3 != 2");
112}
113
114/// Perform basic tests on the sqrt functions.
115pub fn test_sqrt<F: Field>() {
116  assert_eq!(F::ZERO.sqrt().unwrap(), F::ZERO, "sqrt(0) != 0");
117  assert!(
118    (F::ONE.sqrt().unwrap() == F::ONE) || (F::ONE.sqrt().unwrap() == -F::ONE),
119    "sqrt(1) != 1"
120  );
121
122  let mut has_root = F::ONE.double();
123  while bool::from(has_root.sqrt().is_none()) {
124    has_root += F::ONE;
125  }
126
127  // The following code doesn't assume which root is returned, yet it does assume a consistent root
128  // is returned
129  let root = has_root.sqrt().unwrap();
130  assert_eq!(root * root, has_root, "sqrt(x)^2 != x");
131
132  let check = |value: (_, _), expected: (_, F), msg| {
133    assert_eq!(bool::from(value.0), bool::from(expected.0), "{msg}");
134    assert!((value.1 == expected.1) || (value.1 == -expected.1), "{msg}");
135  };
136  check(
137    F::sqrt_ratio(&has_root, &F::ONE),
138    (Choice::from(1), root),
139    "sqrt_ratio didn't return the root with a divisor of 1",
140  );
141  check(
142    F::sqrt_ratio(&(has_root * F::ONE.double()), &F::ONE.double()),
143    (Choice::from(1), root),
144    "sqrt_ratio didn't return the root with a divisor of 2",
145  );
146
147  check(F::sqrt_alt(&F::ZERO), F::sqrt_ratio(&F::ZERO, &F::ONE), "sqrt_alt(0) != sqrt_ratio(0, 1)");
148  check(F::sqrt_alt(&F::ONE), F::sqrt_ratio(&F::ONE, &F::ONE), "sqrt_alt(1) != sqrt_ratio(1, 1)");
149  check(F::sqrt_alt(&has_root), (Choice::from(1), root), "sqrt_alt(square) != (1, root)");
150
151  // Check 0 divisors are properly implemented
152  check(
153    F::sqrt_ratio(&has_root, &F::ZERO),
154    (Choice::from(0), F::ZERO),
155    "sqrt_ratio didn't return the right value for a 0 divisor",
156  );
157
158  // Check non-squares are appropriately marked
159  let mut no_root = has_root + F::ONE;
160  while bool::from(no_root.sqrt().is_some()) {
161    no_root += F::ONE;
162  }
163  assert!(
164    !bool::from(F::sqrt_ratio(&no_root, &F::ONE).0),
165    "sqrt_ratio claimed non-square had root"
166  );
167  assert!(!bool::from(F::sqrt_alt(&no_root).0), "sqrt_alt claimed non-square had root");
168}
169
170/// Perform basic tests on the is_zero functions.
171pub fn test_is_zero<F: Field>() {
172  assert!(bool::from(F::ZERO.is_zero()), "0 is not 0");
173  assert!(F::ZERO.is_zero_vartime(), "0 is not 0");
174}
175
176/// Perform basic tests on the cube function.
177pub fn test_cube<F: Field>() {
178  assert_eq!(F::ZERO.cube(), F::ZERO, "0^3 != 0");
179  assert_eq!(F::ONE.cube(), F::ONE, "1^3 != 1");
180  let two = F::ONE.double();
181  assert_eq!(two.cube(), two * two * two, "2^3 != 8");
182}
183
184/// Test random.
185pub fn test_random<R: RngCore, F: Field>(rng: &mut R) {
186  let a = F::random(&mut *rng);
187
188  // Run up to 128 times so small fields, which may occasionally return the same element twice,
189  // are statistically unlikely to fail
190  // Field of order 1 will always fail this test due to lack of distinct elements to sample
191  // from
192  let mut pass = false;
193  for _ in 0 .. 128 {
194    let b = F::random(&mut *rng);
195    // This test passes if a distinct element is returned at least once
196    if b != a {
197      pass = true;
198    }
199  }
200  assert!(pass, "random always returned the same value");
201}
202
203/// Run all tests on fields implementing Field.
204pub fn test_field<R: RngCore, F: Field>(rng: &mut R) {
205  test_eq::<F>();
206  test_conditional_select::<F>();
207
208  test_add::<F>();
209  test_sum::<F>();
210
211  test_sub::<F>();
212  test_neg::<F>();
213
214  test_mul::<F>();
215  test_product::<F>();
216
217  test_square::<F>();
218  test_invert::<F>();
219  test_sqrt::<F>();
220  test_is_zero::<F>();
221
222  test_cube::<F>();
223
224  test_random::<R, F>(rng);
225}
ff_group_tests/field.rs

ff_group_tests/
field.rs
