Clearmatics Libff  0.1
C++ library for Finite Fields and Elliptic Curves
bn128_g2.cpp
Go to the documentation of this file.
1 
10 
11 namespace libff
12 {
13 
14 #ifdef PROFILE_OP_COUNTS
15 long long bn128_G2::add_cnt = 0;
16 long long bn128_G2::dbl_cnt = 0;
17 #endif
18 
19 std::vector<size_t> bn128_G2::wnaf_window_table;
20 std::vector<size_t> bn128_G2::fixed_base_exp_window_table;
21 bn128_G2 bn128_G2::G2_zero;
22 bn128_G2 bn128_G2::G2_one;
23 bigint<bn128_G2::h_limbs> bn128_G2::h;
24 
25 bn::Fp2 bn128_G2::sqrt(const bn::Fp2 &el)
26 {
27  size_t v = bn128_Fq2_s;
28  bn::Fp2 z = bn128_Fq2_nqr_to_t;
29  bn::Fp2 w = mie::power(el, bn128_Fq2_t_minus_1_over_2);
30  bn::Fp2 x = el * w;
31  bn::Fp2 b = x * w;
32 
33 #if DEBUG
34  // check if square with Euler's criterion
35  bn::Fp2 check = b;
36  for (size_t i = 0; i < v - 1; ++i) {
37  bn::Fp2::square(check, check);
38  }
39 
40  assert(check == bn::Fp2(bn::Fp(1), bn::Fp(0)));
41 #endif
42 
43  // compute square root with Tonelli--Shanks
44  // (does not terminate if not a square!)
45 
46  while (b != bn::Fp2(1)) {
47  size_t m = 0;
48  bn::Fp2 b2m = b;
49  while (b2m != bn::Fp2(bn::Fp(1), bn::Fp(0))) {
50  // invariant: b2m = b^(2^m) after entering this loop
51  bn::Fp2::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::Fp2::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 = G2_zero.X;
75  this->Y = G2_zero.Y;
76  this->Z = G2_zero.Z;
77 }
78 
79 void bn128_G2::print() const
80 {
81  if (this->is_zero()) {
82  printf("O\n");
83  } else {
84  bn128_G2 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::Fp2 r;
109  r = Z;
110  r.inverse();
111  bn::Fp2::square(Z, r);
112  X *= Z;
113  r *= Z;
114  Y *= r;
115  Z = 1;
116  }
117 }
118 
120 
121 bool bn128_G2::is_special() const { return (this->is_zero() || this->Z == 1); }
122 
123 bool bn128_G2::is_zero() const { return Z.isZero(); }
124 
125 bool bn128_G2::operator==(const bn128_G2 &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::Fp2 Z1sq, Z2sq, lhs, rhs;
138  bn::Fp2::square(Z1sq, this->Z);
139  bn::Fp2::square(Z2sq, other.Z);
140  bn::Fp2::mul(lhs, Z2sq, this->X);
141  bn::Fp2::mul(rhs, Z1sq, other.X);
142 
143  if (lhs != rhs) {
144  return false;
145  }
146 
147  bn::Fp2 Z1cubed, Z2cubed;
148  bn::Fp2::mul(Z1cubed, Z1sq, this->Z);
149  bn::Fp2::mul(Z2cubed, Z2sq, other.Z);
150  bn::Fp2::mul(lhs, Z2cubed, this->Y);
151  bn::Fp2::mul(rhs, Z1cubed, other.Y);
152 
153  return (lhs == rhs);
154 }
155 
156 bool bn128_G2::operator!=(const bn128_G2 &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_G2 result(*this);
186  bn::Fp2::neg(result.Y, result.Y);
187  return result;
188 }
189 
191 {
192  return (*this) + (-other);
193 }
194 
195 bn128_G2 bn128_G2::add(const bn128_G2 &other) const
196 {
197 #ifdef PROFILE_OP_COUNTS
198  this->add_cnt++;
199 #endif
200 
201  bn::Fp2 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_G2 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::Fp2 Z1Z1;
239  bn::Fp2::square(Z1Z1, this->Z);
240  const bn::Fp2 &U1 = this->X;
241  bn::Fp2 U2;
242  bn::Fp2::mul(U2, other.X, Z1Z1);
243  bn::Fp2 Z1_cubed;
244  bn::Fp2::mul(Z1_cubed, this->Z, Z1Z1);
245 
246  const bn::Fp2 &S1 = this->Y;
247  bn::Fp2 S2;
248  // S2 = Y2*Z1*Z1Z1
249  bn::Fp2::mul(S2, other.Y, Z1_cubed);
250 
251  if (U1 == U2 && S1 == S2) {
252  // dbl case; nothing of above can be reused
253  return this->dbl();
254  }
255 
256 #ifdef PROFILE_OP_COUNTS
257  this->add_cnt++;
258 #endif
259 
260  bn128_G2 result;
261  bn::Fp2 H, HH, I, J, r, V, tmp;
262  // H = U2-X1
263  bn::Fp2::sub(H, U2, this->X);
264  // HH = H^2
265  bn::Fp2::square(HH, H);
266  // I = 4*HH
267  bn::Fp2::add(tmp, HH, HH);
268  bn::Fp2::add(I, tmp, tmp);
269  // J = H*I
270  bn::Fp2::mul(J, H, I);
271  // r = 2*(S2-Y1)
272  bn::Fp2::sub(tmp, S2, this->Y);
273  bn::Fp2::add(r, tmp, tmp);
274  // V = X1*I
275  bn::Fp2::mul(V, this->X, I);
276  // X3 = r^2-J-2*V
277  bn::Fp2::square(result.X, r);
278  bn::Fp2::sub(result.X, result.X, J);
279  bn::Fp2::sub(result.X, result.X, V);
280  bn::Fp2::sub(result.X, result.X, V);
281  // Y3 = r*(V-X3)-2*Y1*J
282  bn::Fp2::sub(tmp, V, result.X);
283  bn::Fp2::mul(result.Y, r, tmp);
284  bn::Fp2::mul(tmp, this->Y, J);
285  bn::Fp2::sub(result.Y, result.Y, tmp);
286  bn::Fp2::sub(result.Y, result.Y, tmp);
287  // Z3 = (Z1+H)^2-Z1Z1-HH
288  bn::Fp2::add(tmp, this->Z, H);
289  bn::Fp2::square(result.Z, tmp);
290  bn::Fp2::sub(result.Z, result.Z, Z1Z1);
291  bn::Fp2::sub(result.Z, result.Z, HH);
292  return result;
293 }
294 
296 {
297 #ifdef PROFILE_OP_COUNTS
298  this->dbl_cnt++;
299 #endif
300 
301  bn::Fp2 this_coord[3], result_coord[3];
302  this->fill_coord(this_coord);
303  bn::ecop::ECDouble(result_coord, this_coord);
304 
305  bn128_G2 result(result_coord);
306  return result;
307 }
308 
309 bn128_G2 bn128_G2::mul_by_cofactor() const { return bn128_G2::h * (*this); }
310 
312 {
313  if (this->is_zero()) {
314  return true;
315  } else {
316  // y^2 = x^3 + b
317  //
318  // We are using Jacobian coordinates, so equation we need to check is
319  // actually
320  //
321  // (y/z^3)^2 = (x/z^2)^3 + b
322  // y^2 / z^6 = x^3 / z^6 + b
323  // y^2 = x^3 + b z^6
324  bn::Fp2 X2, Y2, Z2;
325  bn::Fp2::square(X2, this->X);
326  bn::Fp2::square(Y2, this->Y);
327  bn::Fp2::square(Z2, this->Z);
328 
329  bn::Fp2 X3, Z3, Z6;
330  bn::Fp2::mul(X3, X2, this->X);
331  bn::Fp2::mul(Z3, Z2, this->Z);
332  bn::Fp2::square(Z6, Z3);
333 
334  return (Y2 == X3 + bn128_twist_coeff_b * Z6);
335  }
336 }
337 
339 {
340  return zero() == scalar_field::mod * (*this);
341 }
342 
343 const bn128_G2 &bn128_G2::zero() { return G2_zero; }
344 
345 const bn128_G2 &bn128_G2::one() { return G2_one; }
346 
348 {
349  return bn128_Fr::random_element().as_bigint() * G2_one;
350 }
351 
352 void bn128_G2::write_uncompressed(std::ostream &out) const
353 {
354  bn128_G2 gcopy(*this);
355  gcopy.to_affine_coordinates();
356 
357  out << (gcopy.is_zero() ? '1' : '0') << OUTPUT_SEPARATOR;
358 
359  /* no point compression case */
360 #ifndef BINARY_OUTPUT
361  out << gcopy.X.a_ << OUTPUT_SEPARATOR << gcopy.X.b_ << OUTPUT_SEPARATOR;
362  out << gcopy.Y.a_ << OUTPUT_SEPARATOR << gcopy.Y.b_;
363 #else
364  out.write((char *)&gcopy.X.a_, sizeof(gcopy.X.a_));
365  out.write((char *)&gcopy.X.b_, sizeof(gcopy.X.b_));
366  out.write((char *)&gcopy.Y.a_, sizeof(gcopy.Y.a_));
367  out.write((char *)&gcopy.Y.b_, sizeof(gcopy.Y.b_));
368 #endif
369 }
370 
371 void bn128_G2::write_compressed(std::ostream &out) const
372 {
373  bn128_G2 gcopy(*this);
374  gcopy.to_affine_coordinates();
375 
376  out << (gcopy.is_zero() ? '1' : '0') << OUTPUT_SEPARATOR;
377 
378 #ifndef BINARY_OUTPUT
379  out << gcopy.X.a_ << OUTPUT_SEPARATOR << gcopy.X.b_;
380 #else
381  out.write((char *)&gcopy.X.a_, sizeof(gcopy.X.a_));
382  out.write((char *)&gcopy.X.b_, sizeof(gcopy.X.b_));
383 #endif
384  out << OUTPUT_SEPARATOR
385  << (((unsigned char *)&gcopy.Y.a_)[0] & 1 ? '1' : '0');
386 }
387 
388 void bn128_G2::read_uncompressed(std::istream &in, bn128_G2 &g)
389 {
390  char is_zero;
391  // this reads is_zero;
392  in.read((char *)&is_zero, 1);
393  is_zero -= '0';
395 
396 #ifndef BINARY_OUTPUT
397  in >> g.X.a_;
399  in >> g.X.b_;
401  in >> g.Y.a_;
403  in >> g.Y.b_;
404 #else
405  in.read((char *)&g.X.a_, sizeof(g.X.a_));
406  in.read((char *)&g.X.b_, sizeof(g.X.b_));
407  in.read((char *)&g.Y.a_, sizeof(g.Y.a_));
408  in.read((char *)&g.Y.b_, sizeof(g.Y.b_));
409 #endif
410 
411  // finalize
412  if (!is_zero) {
413  g.Z = bn::Fp2(bn::Fp(1), bn::Fp(0));
414  } else {
415  g = bn128_G2::zero();
416  }
417 }
418 
419 void bn128_G2::read_compressed(std::istream &in, bn128_G2 &g)
420 {
421  char is_zero;
422  // this reads is_zero;
423  in.read((char *)&is_zero, 1);
424  is_zero -= '0';
426 
427  bn::Fp2 tX;
428 #ifndef BINARY_OUTPUT
429  in >> tX.a_;
431  in >> tX.b_;
432 #else
433  in.read((char *)&tX.a_, sizeof(tX.a_));
434  in.read((char *)&tX.b_, sizeof(tX.b_));
435 #endif
437  unsigned char Y_lsb;
438  in.read((char *)&Y_lsb, 1);
439  Y_lsb -= '0';
440 
441  // y = +/- sqrt(x^3 + b)
442  if (!is_zero) {
443  g.X = tX;
444  bn::Fp2 tX2, tY2;
445  bn::Fp2::square(tX2, tX);
446  bn::Fp2::mul(tY2, tX2, tX);
447  bn::Fp2::add(tY2, tY2, bn128_twist_coeff_b);
448 
449  g.Y = bn128_G2::sqrt(tY2);
450  if ((((unsigned char *)&g.Y.a_)[0] & 1) != Y_lsb) {
451  bn::Fp2::neg(g.Y, g.Y);
452  }
453  }
454 
455  // finalize
456  if (!is_zero) {
457  g.Z = bn::Fp2(bn::Fp(1), bn::Fp(0));
458  } else {
459  g = bn128_G2::zero();
460  }
461 }
462 
463 std::ostream &operator<<(std::ostream &out, const bn128_G2 &g)
464 {
465 #ifdef NO_PT_COMPRESSION
466  g.write_uncompressed(out);
467 #else
468  g.write_compressed(out);
469 #endif
470  return out;
471 }
472 
473 std::istream &operator>>(std::istream &in, bn128_G2 &g)
474 {
475 #ifdef NO_PT_COMPRESSION
477 #else
479 #endif
480  return in;
481 }
482 
483 void bn128_G2::batch_to_special_all_non_zeros(std::vector<bn128_G2> &vec)
484 {
485  std::vector<bn::Fp2> Z_vec;
486  Z_vec.reserve(vec.size());
487 
488  for (auto &el : vec) {
489  Z_vec.emplace_back(el.Z);
490  }
491  bn_batch_invert<bn::Fp2>(Z_vec);
492 
493  const bn::Fp2 one = 1;
494 
495  for (size_t i = 0; i < vec.size(); ++i) {
496  bn::Fp2 Z2, Z3;
497  bn::Fp2::square(Z2, Z_vec[i]);
498  bn::Fp2::mul(Z3, Z2, Z_vec[i]);
499 
500  bn::Fp2::mul(vec[i].X, vec[i].X, Z2);
501  bn::Fp2::mul(vec[i].Y, vec[i].Y, Z3);
502  vec[i].Z = one;
503  }
504 }
505 
506 } // namespace libff
libff::bn128_G2::operator-
bn128_G2 operator-() const
Definition: bn128_g2.cpp:183
libff::bn128_G2::is_well_formed
bool is_well_formed() const
Definition: bn128_g2.cpp:311
libff::bn128_G2::Z
bn::Fp2 Z
Definition: bn128_g2.hpp:48
libff::bn128_Fq2_nqr_to_t
bn::Fp2 bn128_Fq2_nqr_to_t
Definition: bn128_init.cpp:26
libff::bn128_G2::dbl
bn128_G2 dbl() const
Definition: bn128_g2.cpp:295
libff::Fp_model::random_element
static Fp_model< n, modulus > random_element()
returns random element of Fp_model
libff::bn128_G2::read_uncompressed
static void read_uncompressed(std::istream &, bn128_G2 &)
Definition: bn128_g2.cpp:388
libff
Definition: ffi.cpp:8
libff::bn128_G2::wnaf_window_table
static std::vector< size_t > wnaf_window_table
Definition: bn128_g2.hpp:34
libff::bn128_Fq2_s
size_t bn128_Fq2_s
Definition: bn128_init.cpp:25
libff::bn128_G2::fill_coord
void fill_coord(bn::Fp2 coord[3]) const
Definition: bn128_g2.hpp:49
libff::bn128_G2::add
bn128_G2 add(const bn128_G2 &other) const
Definition: bn128_g2.cpp:195
libff::operator>>
std::istream & operator>>(std::istream &in, alt_bn128_G1 &g)
Definition: alt_bn128_g1.cpp:446
libff::bn128_G2::mul_by_cofactor
bn128_G2 mul_by_cofactor() const
Definition: bn128_g2.cpp:309
bn_utils.hpp
libff::bn128_G2::h
static bigint< h_limbs > h
Definition: bn128_g2.hpp:46
libff::bn128_G2::X
bn::Fp2 X
Definition: bn128_g2.hpp:48
libff::bn128_G2::G2_one
static bn128_G2 G2_one
Definition: bn128_g2.hpp:37
OUTPUT_SEPARATOR
#define OUTPUT_SEPARATOR
Definition: serialization.hpp:69
libff::bn128_G2::read_compressed
static void read_compressed(std::istream &, bn128_G2 &)
Definition: bn128_g2.cpp:419
libff::bn128_G2::to_special
void to_special()
Definition: bn128_g2.cpp:119
libff::bn128_G2::Y
bn::Fp2 Y
Definition: bn128_g2.hpp:48
libff::bn128_G2::write_uncompressed
void write_uncompressed(std::ostream &) const
Definition: bn128_g2.cpp:352
libff::bn128_G2::print_coordinates
void print_coordinates() const
Definition: bn128_g2.cpp:91
libff::consume_OUTPUT_SEPARATOR
void consume_OUTPUT_SEPARATOR(std::istream &in)
libff::bn128_G2::zero
static const bn128_G2 & zero()
Definition: bn128_g2.cpp:343
libff::bn128_G2::operator+
bn128_G2 operator+(const bn128_G2 &other) const
Definition: bn128_g2.cpp:161
libff::bn128_G2::print
void print() const
Definition: bn128_g2.cpp:79
libff::bn128_G2::batch_to_special_all_non_zeros
static void batch_to_special_all_non_zeros(std::vector< bn128_G2 > &vec)
Definition: bn128_g2.cpp:483
libff::bn128_twist_coeff_b
bn::Fp2 bn128_twist_coeff_b
Definition: bn128_init.cpp:24
libff::bn128_G2::operator==
bool operator==(const bn128_G2 &other) const
Definition: bn128_g2.cpp:125
libff::bn128_G2::G2_zero
static bn128_G2 G2_zero
Definition: bn128_g2.hpp:36
libff::bn128_G2::random_element
static bn128_G2 random_element()
Definition: bn128_g2.cpp:347
libff::bn128_G2::mixed_add
bn128_G2 mixed_add(const bn128_G2 &other) const
Definition: bn128_g2.cpp:210
libff::operator<<
std::ostream & operator<<(std::ostream &out, const alt_bn128_G1 &g)
Definition: alt_bn128_g1.cpp:436
libff::bn128_G2::one
static const bn128_G2 & one()
Definition: bn128_g2.cpp:345
libff::bn128_G2::fixed_base_exp_window_table
static std::vector< size_t > fixed_base_exp_window_table
Definition: bn128_g2.hpp:35
libff::bn128_G2::is_zero
bool is_zero() const
Definition: bn128_g2.cpp:123
libff::bn128_Fq2_t_minus_1_over_2
mie::Vuint bn128_Fq2_t_minus_1_over_2
Definition: bn128_init.cpp:27
libff::power
FieldT power(const FieldT &base, const bigint< m > &exponent)
libff::Fp_model::mod
static const constexpr bigint< n > & mod
Definition: fp.hpp:48
libff::bn128_G2::is_special
bool is_special() const
Definition: bn128_g2.cpp:121
libff::bn128_G2::operator!=
bool operator!=(const bn128_G2 &other) const
Definition: bn128_g2.cpp:156
bn128_g2.hpp
libff::bn128_G2::bn128_G2
bn128_G2()
Definition: bn128_g2.cpp:72
libff::bn128_G2
Definition: bn128_g2.hpp:24
libff::bn128_G2::write_compressed
void write_compressed(std::ostream &) const
Definition: bn128_g2.cpp:371
libff::bn128_G2::to_affine_coordinates
void to_affine_coordinates()
Definition: bn128_g2.cpp:101
libff::bn128_G2::is_in_safe_subgroup
bool is_in_safe_subgroup() const
Definition: bn128_g2.cpp:338