Clearmatics Libff  0.1
C++ library for Finite Fields and Elliptic Curves
bn128_g1.cpp
Go to the documentation of this file.
1 
10 
11 namespace libff
12 {
13 
14 #ifdef PROFILE_OP_COUNTS
15 long long bn128_G1::add_cnt = 0;
16 long long bn128_G1::dbl_cnt = 0;
17 #endif
18 
19 std::vector<size_t> bn128_G1::wnaf_window_table;
20 std::vector<size_t> bn128_G1::fixed_base_exp_window_table;
21 bn128_G1 bn128_G1::G1_zero;
22 bn128_G1 bn128_G1::G1_one;
23 bigint<bn128_G1::h_limbs> bn128_G1::h;
24 
25 bn::Fp bn128_G1::sqrt(const bn::Fp &el)
26 {
27  size_t v = bn128_Fq_s;
28  bn::Fp z = bn128_Fq_nqr_to_t;
29  bn::Fp w = mie::power(el, bn128_Fq_t_minus_1_over_2);
30  bn::Fp x = el * w;
31  bn::Fp b = x * w;
32 
33 #if DEBUG
34  // check if square with Euler's criterion
35  bn::Fp check = b;
36  for (size_t i = 0; i < v - 1; ++i) {
37  bn::Fp::square(check, check);
38  }
39 
40  assert(check == bn::Fp(1));
41 #endif
42 
43  // compute square root with Tonelli--Shanks
44  // (does not terminate if not a square!)
45 
46  while (b != bn::Fp(1)) {
47  size_t m = 0;
48  bn::Fp b2m = b;
49  while (b2m != bn::Fp(1)) {
50  // invariant: b2m = b^(2^m) after entering this loop
51  bn::Fp::square(b2m, b2m);
52  m += 1;
53  }
54 
55  // w = z^2^(v-m-1)
56  int j = v - m - 1;
57  w = z;
58  while (j > 0) {
59  bn::Fp::square(w, w);
60  --j;
61  }
62 
63  z = w * w;
64  b = b * z;
65  x = x * w;
66  v = m;
67  }
68 
69  return x;
70 }
71 
73 {
74  this->X = G1_zero.X;
75  this->Y = G1_zero.Y;
76  this->Z = G1_zero.Z;
77 }
78 
79 void bn128_G1::print() const
80 {
81  if (this->is_zero()) {
82  printf("O\n");
83  } else {
84  bn128_G1 copy(*this);
85  copy.to_affine_coordinates();
86  std::cout << "(" << copy.X.toString(10) << " : " << copy.Y.toString(10)
87  << " : " << copy.Z.toString(10) << ")\n";
88  }
89 }
90 
92 {
93  if (this->is_zero()) {
94  printf("O\n");
95  } else {
96  std::cout << "(" << X.toString(10) << " : " << Y.toString(10) << " : "
97  << Z.toString(10) << ")\n";
98  }
99 }
100 
102 {
103  if (this->is_zero()) {
104  X = 0;
105  Y = 1;
106  Z = 0;
107  } else {
108  bn::Fp r;
109  r = Z;
110  r.inverse();
111  bn::Fp::square(Z, r);
112  X *= Z;
113  r *= Z;
114  Y *= r;
115  Z = 1;
116  }
117 }
118 
120 
121 bool bn128_G1::is_special() const { return (this->is_zero() || this->Z == 1); }
122 
123 bool bn128_G1::is_zero() const { return Z.isZero(); }
124 
125 bool bn128_G1::operator==(const bn128_G1 &other) const
126 {
127  if (this->is_zero()) {
128  return other.is_zero();
129  }
130 
131  if (other.is_zero()) {
132  return false;
133  }
134 
135  /* now neither is O */
136 
137  bn::Fp Z1sq, Z2sq, lhs, rhs;
138  bn::Fp::square(Z1sq, this->Z);
139  bn::Fp::square(Z2sq, other.Z);
140  bn::Fp::mul(lhs, Z2sq, this->X);
141  bn::Fp::mul(rhs, Z1sq, other.X);
142 
143  if (lhs != rhs) {
144  return false;
145  }
146 
147  bn::Fp Z1cubed, Z2cubed;
148  bn::Fp::mul(Z1cubed, Z1sq, this->Z);
149  bn::Fp::mul(Z2cubed, Z2sq, other.Z);
150  bn::Fp::mul(lhs, Z2cubed, this->Y);
151  bn::Fp::mul(rhs, Z1cubed, other.Y);
152 
153  return (lhs == rhs);
154 }
155 
156 bool bn128_G1::operator!=(const bn128_G1 &other) const
157 {
158  return !(operator==(other));
159 }
160 
162 {
163  // handle special cases having to do with O
164  if (this->is_zero()) {
165  return other;
166  }
167 
168  if (other.is_zero()) {
169  return *this;
170  }
171 
172  // no need to handle points of order 2,4
173  // (they cannot exist in a prime-order subgroup)
174 
175  // handle double case, and then all the rest
176  if (this->operator==(other)) {
177  return this->dbl();
178  } else {
179  return this->add(other);
180  }
181 }
182 
184 {
185  bn128_G1 result(*this);
186  bn::Fp::neg(result.Y, result.Y);
187  return result;
188 }
189 
191 {
192  return (*this) + (-other);
193 }
194 
195 bn128_G1 bn128_G1::add(const bn128_G1 &other) const
196 {
197 #ifdef PROFILE_OP_COUNTS
198  this->add_cnt++;
199 #endif
200 
201  bn::Fp this_coord[3], other_coord[3], result_coord[3];
202  this->fill_coord(this_coord);
203  other.fill_coord(other_coord);
204  bn::ecop::ECAdd(result_coord, this_coord, other_coord);
205 
206  bn128_G1 result(result_coord);
207  return result;
208 }
209 
211 {
212  if (this->is_zero()) {
213  return other;
214  }
215 
216  if (other.is_zero()) {
217  return *this;
218  }
219 
220  // no need to handle points of order 2,4
221  // (they cannot exist in a prime-order subgroup)
222 
223 #ifdef DEBUG
224  assert(other.is_special());
225 #endif
226 
227  // check for doubling case
228 
229  // using Jacobian coordinates so:
230  // (X1:Y1:Z1) = (X2:Y2:Z2)
231  // iff
232  // X1/Z1^2 == X2/Z2^2 and Y1/Z1^3 == Y2/Z2^3
233  // iff
234  // X1 * Z2^2 == X2 * Z1^2 and Y1 * Z2^3 == Y2 * Z1^3
235 
236  // we know that Z2 = 1
237 
238  bn::Fp Z1Z1;
239  bn::Fp::square(Z1Z1, this->Z);
240  const bn::Fp &U1 = this->X;
241  bn::Fp U2;
242  bn::Fp::mul(U2, other.X, Z1Z1);
243  bn::Fp Z1_cubed;
244  bn::Fp::mul(Z1_cubed, this->Z, Z1Z1);
245 
246  const bn::Fp &S1 = this->Y;
247  bn::Fp S2;
248  bn::Fp::mul(S2, other.Y, Z1_cubed); // S2 = Y2*Z1*Z1Z1
249 
250  if (U1 == U2 && S1 == S2) {
251  // dbl case; nothing of above can be reused
252  return this->dbl();
253  }
254 
255 #ifdef PROFILE_OP_COUNTS
256  this->add_cnt++;
257 #endif
258 
259  bn128_G1 result;
260  bn::Fp H, HH, I, J, r, V, tmp;
261  // H = U2-X1
262  bn::Fp::sub(H, U2, this->X);
263  // HH = H^2
264  bn::Fp::square(HH, H);
265  // I = 4*HH
266  bn::Fp::add(tmp, HH, HH);
267  bn::Fp::add(I, tmp, tmp);
268  // J = H*I
269  bn::Fp::mul(J, H, I);
270  // r = 2*(S2-Y1)
271  bn::Fp::sub(tmp, S2, this->Y);
272  bn::Fp::add(r, tmp, tmp);
273  // V = X1*I
274  bn::Fp::mul(V, this->X, I);
275  // X3 = r^2-J-2*V
276  bn::Fp::square(result.X, r);
277  bn::Fp::sub(result.X, result.X, J);
278  bn::Fp::sub(result.X, result.X, V);
279  bn::Fp::sub(result.X, result.X, V);
280  // Y3 = r*(V-X3)-2*Y1*J
281  bn::Fp::sub(tmp, V, result.X);
282  bn::Fp::mul(result.Y, r, tmp);
283  bn::Fp::mul(tmp, this->Y, J);
284  bn::Fp::sub(result.Y, result.Y, tmp);
285  bn::Fp::sub(result.Y, result.Y, tmp);
286  // Z3 = (Z1+H)^2-Z1Z1-HH
287  bn::Fp::add(tmp, this->Z, H);
288  bn::Fp::square(result.Z, tmp);
289  bn::Fp::sub(result.Z, result.Z, Z1Z1);
290  bn::Fp::sub(result.Z, result.Z, HH);
291  return result;
292 }
293 
295 {
296 #ifdef PROFILE_OP_COUNTS
297  this->dbl_cnt++;
298 #endif
299 
300  bn::Fp this_coord[3], result_coord[3];
301  this->fill_coord(this_coord);
302  bn::ecop::ECDouble(result_coord, this_coord);
303 
304  bn128_G1 result(result_coord);
305  return result;
306 }
307 
309 {
310  // Cofactor = 1
311  return (*this);
312 }
313 
314 const bn128_G1 &bn128_G1::zero() { return G1_zero; }
315 
316 const bn128_G1 &bn128_G1::one() { return G1_one; }
317 
319 {
320  return bn128_Fr::random_element().as_bigint() * G1_one;
321 }
322 
324 {
325  if (this->is_zero()) {
326  return true;
327  } else {
328  /*
329  y^2 = x^3 + b
330 
331  We are using Jacobian coordinates, so equation we need to check is
332  actually
333 
334  (y/z^3)^2 = (x/z^2)^3 + b
335  y^2 / z^6 = x^3 / z^6 + b
336  y^2 = x^3 + b z^6
337  */
338  bn::Fp X2, Y2, Z2;
339  bn::Fp::square(X2, this->X);
340  bn::Fp::square(Y2, this->Y);
341  bn::Fp::square(Z2, this->Z);
342 
343  bn::Fp X3, Z3, Z6;
344  bn::Fp::mul(X3, X2, this->X);
345  bn::Fp::mul(Z3, Z2, this->Z);
346  bn::Fp::square(Z6, Z3);
347 
348  return (Y2 == X3 + bn128_coeff_b * Z6);
349  }
350 }
351 
352 bool bn128_G1::is_in_safe_subgroup() const { return true; }
353 
354 void bn128_G1::write_uncompressed(std::ostream &out) const
355 {
356  bn128_G1 gcopy(*this);
357  gcopy.to_affine_coordinates();
358 
359  out << (gcopy.is_zero() ? '1' : '0') << OUTPUT_SEPARATOR;
360 
361 #ifndef BINARY_OUTPUT
362  out << gcopy.X << OUTPUT_SEPARATOR << gcopy.Y;
363 #else
364  out.write((char *)&gcopy.X, sizeof(gcopy.X));
365  out.write((char *)&gcopy.Y, sizeof(gcopy.Y));
366 #endif
367 }
368 
369 void bn128_G1::write_compressed(std::ostream &out) const
370 {
371  bn128_G1 gcopy(*this);
372  gcopy.to_affine_coordinates();
373 
374  out << (gcopy.is_zero() ? '1' : '0') << OUTPUT_SEPARATOR;
375 
376 #ifndef BINARY_OUTPUT
377  out << gcopy.X;
378 #else
379  out.write((char *)&gcopy.X, sizeof(gcopy.X));
380 #endif
381  out << OUTPUT_SEPARATOR << (((unsigned char *)&gcopy.Y)[0] & 1 ? '1' : '0');
382 }
383 
384 void bn128_G1::read_uncompressed(std::istream &in, bn128_G1 &g)
385 {
386  char is_zero;
387  in.read((char *)&is_zero, 1); // this reads is_zero;
388  is_zero -= '0';
390 
391 #ifndef BINARY_OUTPUT
392  in >> g.X;
394  in >> g.Y;
395 #else
396  in.read((char *)&g.X, sizeof(g.X));
397  in.read((char *)&g.Y, sizeof(g.Y));
398 #endif
399 
400  /* finalize */
401  if (!is_zero) {
402  g.Z = bn::Fp(1);
403  } else {
404  g = bn128_G1::zero();
405  }
406 }
407 
408 void bn128_G1::read_compressed(std::istream &in, bn128_G1 &g)
409 {
410  char is_zero;
411  // this reads is_zero;
412  in.read((char *)&is_zero, 1);
413  is_zero -= '0';
415 
416  bn::Fp tX;
417 #ifndef BINARY_OUTPUT
418  in >> tX;
419 #else
420  in.read((char *)&tX, sizeof(tX));
421 #endif
423  unsigned char Y_lsb;
424  in.read((char *)&Y_lsb, 1);
425  Y_lsb -= '0';
426 
427  // y = +/- sqrt(x^3 + b)
428  if (!is_zero) {
429  g.X = tX;
430  bn::Fp tX2, tY2;
431  bn::Fp::square(tX2, tX);
432  bn::Fp::mul(tY2, tX2, tX);
433  bn::Fp::add(tY2, tY2, bn128_coeff_b);
434 
435  g.Y = bn128_G1::sqrt(tY2);
436  if ((((unsigned char *)&g.Y)[0] & 1) != Y_lsb) {
437  bn::Fp::neg(g.Y, g.Y);
438  }
439  }
440 
441  /* finalize */
442  if (!is_zero) {
443  g.Z = bn::Fp(1);
444  } else {
445  g = bn128_G1::zero();
446  }
447 }
448 
449 std::ostream &operator<<(std::ostream &out, const bn128_G1 &g)
450 {
451 #ifdef NO_PT_COMPRESSION
452  g.write_uncompressed(out);
453 #else
454  g.write_compressed(out);
455 #endif
456  return out;
457 }
458 
459 std::istream &operator>>(std::istream &in, bn128_G1 &g)
460 {
461 #ifdef NO_PT_COMPRESSION
463 #else
465 #endif
466  return in;
467 }
468 
469 void bn128_G1::batch_to_special_all_non_zeros(std::vector<bn128_G1> &vec)
470 {
471  std::vector<bn::Fp> Z_vec;
472  Z_vec.reserve(vec.size());
473 
474  for (auto &el : vec) {
475  Z_vec.emplace_back(el.Z);
476  }
477  bn_batch_invert<bn::Fp>(Z_vec);
478 
479  const bn::Fp one = 1;
480 
481  for (size_t i = 0; i < vec.size(); ++i) {
482  bn::Fp Z2, Z3;
483  bn::Fp::square(Z2, Z_vec[i]);
484  bn::Fp::mul(Z3, Z2, Z_vec[i]);
485 
486  bn::Fp::mul(vec[i].X, vec[i].X, Z2);
487  bn::Fp::mul(vec[i].Y, vec[i].Y, Z3);
488  vec[i].Z = one;
489  }
490 }
491 
492 } // namespace libff
libff::bn128_G1::mul_by_cofactor
bn128_G1 mul_by_cofactor() const
Definition: bn128_g1.cpp:308
libff::bn128_G1::batch_to_special_all_non_zeros
static void batch_to_special_all_non_zeros(std::vector< bn128_G1 > &vec)
Definition: bn128_g1.cpp:469
libff::bn128_G1::G1_zero
static bn128_G1 G1_zero
Definition: bn128_g1.hpp:35
libff::Fp_model::random_element
static Fp_model< n, modulus > random_element()
returns random element of Fp_model
libff::bn128_G1::dbl
bn128_G1 dbl() const
Definition: bn128_g1.cpp:294
libff
Definition: ffi.cpp:8
libff::bn128_G1::is_in_safe_subgroup
bool is_in_safe_subgroup() const
Definition: bn128_g1.cpp:352
libff::bn128_G1::operator==
bool operator==(const bn128_G1 &other) const
Definition: bn128_g1.cpp:125
libff::bn128_G1::print
void print() const
Definition: bn128_g1.cpp:79
libff::bn128_G1::write_uncompressed
void write_uncompressed(std::ostream &) const
Definition: bn128_g1.cpp:354
libff::bn128_G1
Definition: bn128_g1.hpp:23
libff::bn128_coeff_b
bn::Fp bn128_coeff_b
Definition: bn128_init.cpp:19
libff::operator>>
std::istream & operator>>(std::istream &in, alt_bn128_G1 &g)
Definition: alt_bn128_g1.cpp:446
libff::bn128_Fq_nqr_to_t
bn::Fp bn128_Fq_nqr_to_t
Definition: bn128_init.cpp:21
bn_utils.hpp
libff::bn128_G1::read_uncompressed
static void read_uncompressed(std::istream &, bn128_G1 &)
Definition: bn128_g1.cpp:384
libff::bn128_G1::print_coordinates
void print_coordinates() const
Definition: bn128_g1.cpp:91
libff::bn128_G1::operator!=
bool operator!=(const bn128_G1 &other) const
Definition: bn128_g1.cpp:156
libff::bn128_G1::to_special
void to_special()
Definition: bn128_g1.cpp:119
OUTPUT_SEPARATOR
#define OUTPUT_SEPARATOR
Definition: serialization.hpp:69
libff::bn128_G1::random_element
static bn128_G1 random_element()
Definition: bn128_g1.cpp:318
libff::consume_OUTPUT_SEPARATOR
void consume_OUTPUT_SEPARATOR(std::istream &in)
libff::bn128_Fq_s
size_t bn128_Fq_s
Definition: bn128_init.cpp:20
libff::bn128_G1::mixed_add
bn128_G1 mixed_add(const bn128_G1 &other) const
Definition: bn128_g1.cpp:210
libff::bn128_G1::write_compressed
void write_compressed(std::ostream &) const
Definition: bn128_g1.cpp:369
libff::bn128_G1::to_affine_coordinates
void to_affine_coordinates()
Definition: bn128_g1.cpp:101
bn128_g1.hpp
libff::bn128_G1::Z
bn::Fp Z
Definition: bn128_g1.hpp:47
libff::bn128_G1::fixed_base_exp_window_table
static std::vector< size_t > fixed_base_exp_window_table
Definition: bn128_g1.hpp:34
libff::bn128_G1::one
static const bn128_G1 & one()
Definition: bn128_g1.cpp:316
libff::bn128_G1::is_well_formed
bool is_well_formed() const
Definition: bn128_g1.cpp:323
libff::bn128_G1::Y
bn::Fp Y
Definition: bn128_g1.hpp:47
libff::bn128_G1::bn128_G1
bn128_G1()
Definition: bn128_g1.cpp:72
libff::operator<<
std::ostream & operator<<(std::ostream &out, const alt_bn128_G1 &g)
Definition: alt_bn128_g1.cpp:436
libff::bn128_G1::fill_coord
void fill_coord(bn::Fp coord[3]) const
Definition: bn128_g1.hpp:48
libff::bn128_G1::h
static bigint< h_limbs > h
Definition: bn128_g1.hpp:45
libff::bn128_G1::zero
static const bn128_G1 & zero()
Definition: bn128_g1.cpp:314
libff::power
FieldT power(const FieldT &base, const bigint< m > &exponent)
libff::bn128_G1::read_compressed
static void read_compressed(std::istream &, bn128_G1 &)
Definition: bn128_g1.cpp:408
libff::bn128_G1::add
bn128_G1 add(const bn128_G1 &other) const
Definition: bn128_g1.cpp:195
libff::bn128_G1::operator+
bn128_G1 operator+(const bn128_G1 &other) const
Definition: bn128_g1.cpp:161
libff::bn128_G1::is_special
bool is_special() const
Definition: bn128_g1.cpp:121
libff::bn128_G1::G1_one
static bn128_G1 G1_one
Definition: bn128_g1.hpp:36
libff::bn128_G1::wnaf_window_table
static std::vector< size_t > wnaf_window_table
Definition: bn128_g1.hpp:33
libff::bn128_G1::operator-
bn128_G1 operator-() const
Definition: bn128_g1.cpp:183
libff::bn128_G1::is_zero
bool is_zero() const
Definition: bn128_g1.cpp:123
libff::bn128_G1::X
bn::Fp X
Definition: bn128_g1.hpp:47
libff::bn128_Fq_t_minus_1_over_2
mie::Vuint bn128_Fq_t_minus_1_over_2
Definition: bn128_init.cpp:22