Clearmatics Libff  0.1
C++ library for Finite Fields and Elliptic Curves
alt_bn128_g1.cpp
Go to the documentation of this file.
1 
9 
10 namespace libff
11 {
12 
13 static const uint8_t G1_ZERO_FLAG = 1 << 0;
14 static const uint8_t G1_Y_LSB_FLAG = 1 << 1;
15 
16 #ifdef PROFILE_OP_COUNTS
17 long long alt_bn128_G1::add_cnt = 0;
18 long long alt_bn128_G1::dbl_cnt = 0;
19 #endif
20 
21 std::vector<size_t> alt_bn128_G1::wnaf_window_table;
23 alt_bn128_G1 alt_bn128_G1::G1_zero;
24 alt_bn128_G1 alt_bn128_G1::G1_one;
27 bigint<alt_bn128_G1::h_limbs> alt_bn128_G1::h;
28 
30 {
31  this->X = G1_zero.X;
32  this->Y = G1_zero.Y;
33  this->Z = G1_zero.Z;
34 }
35 
36 void alt_bn128_G1::print() const
37 {
38  if (this->is_zero()) {
39  printf("O\n");
40  } else {
41  alt_bn128_G1 copy(*this);
42  copy.to_affine_coordinates();
43  gmp_printf(
44  "(%Nd , %Nd)\n",
45  copy.X.as_bigint().data,
47  copy.Y.as_bigint().data,
49  }
50 }
51 
53 {
54  if (this->is_zero()) {
55  printf("O\n");
56  } else {
57  gmp_printf(
58  "(%Nd : %Nd : %Nd)\n",
59  this->X.as_bigint().data,
61  this->Y.as_bigint().data,
63  this->Z.as_bigint().data,
65  }
66 }
67 
69 {
70  if (this->is_zero()) {
71  this->X = alt_bn128_Fq::zero();
72  this->Y = alt_bn128_Fq::one();
73  this->Z = alt_bn128_Fq::zero();
74  } else {
75  const alt_bn128_Fq Z_inv = Z.inverse();
76  const alt_bn128_Fq Z2_inv = Z_inv.squared();
77  const alt_bn128_Fq Z3_inv = Z2_inv * Z_inv;
78  this->X = this->X * Z2_inv;
79  this->Y = this->Y * Z3_inv;
80  this->Z = alt_bn128_Fq::one();
81  }
82 }
83 
85 
87 {
88  return (this->is_zero() || this->Z == alt_bn128_Fq::one());
89 }
90 
91 bool alt_bn128_G1::is_zero() const { return (this->Z.is_zero()); }
92 
93 bool alt_bn128_G1::operator==(const alt_bn128_G1 &other) const
94 {
95  if (this->is_zero()) {
96  return other.is_zero();
97  }
98 
99  if (other.is_zero()) {
100  return false;
101  }
102 
103  // now neither is O
104 
105  // using Jacobian coordinates so:
106  // (X1:Y1:Z1) = (X2:Y2:Z2)
107  // iff
108  // X1/Z1^2 == X2/Z2^2 and Y1/Z1^3 == Y2/Z2^3
109  // iff
110  // X1 * Z2^2 == X2 * Z1^2 and Y1 * Z2^3 == Y2 * Z1^3
111 
112  const alt_bn128_Fq Z1_squared = (this->Z).squared();
113  const alt_bn128_Fq Z2_squared = (other.Z).squared();
114 
115  if ((this->X * Z2_squared) != (other.X * Z1_squared)) {
116  return false;
117  }
118 
119  const alt_bn128_Fq Z1_cubed = (this->Z) * Z1_squared;
120  const alt_bn128_Fq Z2_cubed = (other.Z) * Z2_squared;
121 
122  if ((this->Y * Z2_cubed) != (other.Y * Z1_cubed)) {
123  return false;
124  }
125 
126  return true;
127 }
128 
129 bool alt_bn128_G1::operator!=(const alt_bn128_G1 &other) const
130 {
131  return !(operator==(other));
132 }
133 
135 {
136  return add(other);
137 }
138 
140 {
141  return alt_bn128_G1(this->X, -(this->Y), this->Z);
142 }
143 
145 {
146  return (*this) + (-other);
147 }
148 
150 {
151  // handle special cases having to do with O
152  if (this->is_zero()) {
153  return other;
154  }
155 
156  if (other.is_zero()) {
157  return *this;
158  }
159 
160  // no need to handle points of order 2,4
161  // (they cannot exist in a prime-order subgroup)
162 
163  // handle double case
164  if (this->operator==(other)) {
165  return this->dbl();
166  }
167 
168 #ifdef PROFILE_OP_COUNTS
169  this->add_cnt++;
170 #endif
171  // NOTE: does not handle O and pts of order 2,4
172  // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-add-2007-bl
173 
174  // Z1Z1 = Z1^2
175  const alt_bn128_Fq Z1Z1 = (this->Z).squared();
176  // Z2Z2 = Z2^2
177  const alt_bn128_Fq Z2Z2 = (other.Z).squared();
178  // U1 = X1 * Z2Z2
179  const alt_bn128_Fq U1 = (this->X) * Z2Z2;
180  // U2 = X2 * Z1Z1
181  const alt_bn128_Fq U2 = (other.X) * Z1Z1;
182  // S1 = Y1 * Z2 * Z2Z2
183  const alt_bn128_Fq S1 = (this->Y) * (other.Z) * Z2Z2;
184  // S2 = Y2 * Z1 * Z1Z1
185  const alt_bn128_Fq S2 = (other.Y) * (this->Z) * Z1Z1;
186  // H = U2-U1
187  const alt_bn128_Fq H = U2 - U1;
188  const alt_bn128_Fq S2_minus_S1 = S2 - S1;
189  // I = (2 * H)^2
190  const alt_bn128_Fq I = (H + H).squared();
191  // J = H * I
192  const alt_bn128_Fq J = H * I;
193  // r = 2 * (S2-S1)
194  const alt_bn128_Fq r = S2_minus_S1 + S2_minus_S1;
195  // V = U1 * I
196  const alt_bn128_Fq V = U1 * I;
197  // X3 = r^2 - J - 2 * V
198  const alt_bn128_Fq X3 = r.squared() - J - (V + V);
199  const alt_bn128_Fq S1_J = S1 * J;
200  // Y3 = r * (V-X3)-2 S1 J
201  const alt_bn128_Fq Y3 = r * (V - X3) - (S1_J + S1_J);
202  // Z3 = ((Z1+Z2)^2-Z1Z1-Z2Z2) * H
203  const alt_bn128_Fq Z3 = ((this->Z + other.Z).squared() - Z1Z1 - Z2Z2) * H;
204 
205  return alt_bn128_G1(X3, Y3, Z3);
206 }
207 
209 {
210 #ifdef DEBUG
211  assert(other.is_special());
212 #endif
213 
214  // handle special cases having to do with O
215  if (this->is_zero()) {
216  return other;
217  }
218 
219  if (other.is_zero()) {
220  return *this;
221  }
222 
223  // no need to handle points of order 2,4
224  // (they cannot exist in a prime-order subgroup)
225 
226  // check for doubling case
227 
228  // using Jacobian coordinates so:
229  // (X1:Y1:Z1) = (X2:Y2:Z2)
230  // iff
231  // X1/Z1^2 == X2/Z2^2 and Y1/Z1^3 == Y2/Z2^3
232  // iff
233  // X1 * Z2^2 == X2 * Z1^2 and Y1 * Z2^3 == Y2 * Z1^3
234 
235  // we know that Z2 = 1
236 
237  const alt_bn128_Fq Z1Z1 = (this->Z).squared();
238 
239  const alt_bn128_Fq &U1 = this->X;
240  const alt_bn128_Fq U2 = other.X * Z1Z1;
241 
242  const alt_bn128_Fq Z1_cubed = (this->Z) * Z1Z1;
243 
244  // S1 = Y1 * Z2 * Z2Z2
245  const alt_bn128_Fq &S1 = (this->Y);
246  // S2 = Y2 * Z1 * Z1Z1
247  const alt_bn128_Fq S2 = (other.Y) * Z1_cubed;
248 
249  if (U1 == U2 && S1 == S2) {
250  // dbl case; nothing of above can be reused
251  return this->dbl();
252  }
253 
254 #ifdef PROFILE_OP_COUNTS
255  this->add_cnt++;
256 #endif
257 
258  // NOTE: does not handle O and pts of order 2,4
259  // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#addition-madd-2007-bl
260  // H = U2-X1
261  const alt_bn128_Fq H = U2 - (this->X);
262  // HH = H&2
263  const alt_bn128_Fq HH = H.squared();
264  // I = 4*HH
265  alt_bn128_Fq I = HH + HH;
266  I = I + I;
267  // J = H*I
268  const alt_bn128_Fq J = H * I;
269  // r = 2*(S2-Y1)
270  alt_bn128_Fq r = S2 - (this->Y);
271  r = r + r;
272  // V = X1*I
273  const alt_bn128_Fq V = (this->X) * I;
274  // X3 = r^2-J-2*V
275  const alt_bn128_Fq X3 = r.squared() - J - V - V;
276  // Y3 = r*(V-X3)-2*Y1*J
277  alt_bn128_Fq Y3 = (this->Y) * J;
278  Y3 = r * (V - X3) - Y3 - Y3;
279  // Z3 = (Z1+H)^2-Z1Z1-HH
280  const alt_bn128_Fq Z3 = ((this->Z) + H).squared() - Z1Z1 - HH;
281 
282  return alt_bn128_G1(X3, Y3, Z3);
283 }
284 
286 {
287 #ifdef PROFILE_OP_COUNTS
288  this->dbl_cnt++;
289 #endif
290  // handle point at infinity
291  if (this->is_zero()) {
292  return (*this);
293  }
294 
295  // no need to handle points of order 2,4
296  // (they cannot exist in a prime-order subgroup)
297 
298  // NOTE: does not handle O and pts of order 2,4
299  // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html#doubling-dbl-2009-l
300 
301  // A = X1^2
302  const alt_bn128_Fq A = (this->X).squared();
303  // B = Y1^2
304  const alt_bn128_Fq B = (this->Y).squared();
305  // C = B^2
306  const alt_bn128_Fq C = B.squared();
307  alt_bn128_Fq D = (this->X + B).squared() - A - C;
308  // D = 2 * ((X1 + B)^2 - A - C)
309  D = D + D;
310  // E = 3 * A
311  const alt_bn128_Fq E = A + A + A;
312  // F = E^2
313  const alt_bn128_Fq F = E.squared();
314  // X3 = F - 2 D
315  const alt_bn128_Fq X3 = F - (D + D);
316  alt_bn128_Fq eightC = C + C;
317  eightC = eightC + eightC;
318  eightC = eightC + eightC;
319  // Y3 = E * (D - X3) - 8 * C
320  const alt_bn128_Fq Y3 = E * (D - X3) - eightC;
321  const alt_bn128_Fq Y1Z1 = (this->Y) * (this->Z);
322  // Z3 = 2 * Y1 * Z1
323  const alt_bn128_Fq Z3 = Y1Z1 + Y1Z1;
324 
325  return alt_bn128_G1(X3, Y3, Z3);
326 }
327 
329 {
330  // Cofactor = 1
331  return *this;
332 }
333 
335 {
336  if (this->is_zero()) {
337  return true;
338  } else {
339  // y^2 = x^3 + b
340  //
341  // We are using Jacobian coordinates, so equation we need to check is
342  // actually
343  //
344  // (y/z^3)^2 = (x/z^2)^3 + b
345  // y^2 / z^6 = x^3 / z^6 + b
346  // y^2 = x^3 + b z^6
347  const alt_bn128_Fq X2 = this->X.squared();
348  const alt_bn128_Fq Y2 = this->Y.squared();
349  const alt_bn128_Fq Z2 = this->Z.squared();
350 
351  const alt_bn128_Fq X3 = this->X * X2;
352  const alt_bn128_Fq Z3 = this->Z * Z2;
353  const alt_bn128_Fq Z6 = Z3.squared();
354 
355  return (Y2 == X3 + alt_bn128_coeff_b * Z6);
356  }
357 }
358 
360 {
361  // G1 is the entire group E(Fq), and so there is nothing to check here.
362  return true;
363 }
364 
366 
368 
370 {
371  return (scalar_field::random_element().as_bigint()) * G1_one;
372 }
373 
374 void alt_bn128_G1::write_uncompressed(std::ostream &out) const
375 {
376  // <is_zero> | <x-coord> | <y-coord>
377  alt_bn128_G1 copy((*this));
378  copy.to_affine_coordinates();
379  const char is_zero = '0' + (copy.is_zero() ? G1_ZERO_FLAG : 0);
380  out.write(&is_zero, 1) << copy.X << copy.Y;
381 }
382 
383 void alt_bn128_G1::write_compressed(std::ostream &out) const
384 {
385  // <flags> | <x-coord>
386  alt_bn128_G1 copy((*this));
387  copy.to_affine_coordinates();
388  const uint8_t flags =
389  (copy.is_zero() ? G1_ZERO_FLAG : 0) |
390  ((copy.Y.as_bigint().data[0] & 1) ? G1_Y_LSB_FLAG : 0);
391  const char flags_char = '0' + flags;
392  out.write(&flags_char, 1) << copy.X;
393 }
394 
395 void alt_bn128_G1::read_uncompressed(std::istream &in, alt_bn128_G1 &out)
396 {
397  // <is_zero> | <x-coord> | <y-coord>
398  char is_zero_char;
399  in.read(&is_zero_char, 1) >> out.X >> out.Y;
400  const uint8_t is_zero = (is_zero_char - '0') & G1_ZERO_FLAG;
401 
402  if (!is_zero) {
403  out.Z = alt_bn128_Fq::one();
404  } else {
405  out = alt_bn128_G1::zero();
406  }
407 }
408 
409 void alt_bn128_G1::read_compressed(std::istream &in, alt_bn128_G1 &out)
410 {
411  // <flags> | <x-coord>
412  char flags_char;
413  in.read(&flags_char, 1) >> out.X;
414  ;
416  const uint8_t flags = flags_char - '0';
417 
418  // y = +/- sqrt(x^3 + b)
419  if (0 == (flags & G1_ZERO_FLAG)) {
420  // flags >> 1
421  const uint8_t Y_lsb = 0 != (flags & G1_Y_LSB_FLAG);
422  const alt_bn128_Fq tX2 = out.X.squared();
423  const alt_bn128_Fq tY2 = tX2 * out.X + alt_bn128_coeff_b;
424  out.Y = tY2.sqrt();
425 
426  if ((uint8_t)(out.Y.as_bigint().data[0] & 1) != Y_lsb) {
427  out.Y = -out.Y;
428  }
429 
430  out.Z = alt_bn128_Fq::one();
431  } else {
432  out = alt_bn128_G1::zero();
433  }
434 }
435 
436 std::ostream &operator<<(std::ostream &out, const alt_bn128_G1 &g)
437 {
438 #ifdef NO_PT_COMPRESSION
439  g.write_uncompressed(out);
440 #else
441  g.write_compressed(out);
442 #endif
443  return out;
444 }
445 
446 std::istream &operator>>(std::istream &in, alt_bn128_G1 &g)
447 {
448 #ifdef NO_PT_COMPRESSION
450 #else
452 #endif
453  return in;
454 }
455 
457  std::vector<alt_bn128_G1> &vec)
458 {
459  std::vector<alt_bn128_Fq> Z_vec;
460  Z_vec.reserve(vec.size());
461 
462  for (auto &el : vec) {
463  Z_vec.emplace_back(el.Z);
464  }
465  batch_invert<alt_bn128_Fq>(Z_vec);
466 
468 
469  for (size_t i = 0; i < vec.size(); ++i) {
470  const alt_bn128_Fq Z2 = Z_vec[i].squared();
471  const alt_bn128_Fq Z3 = Z_vec[i] * Z2;
472 
473  vec[i].X = vec[i].X * Z2;
474  vec[i].Y = vec[i].Y * Z3;
475  vec[i].Z = one;
476  }
477 }
478 
479 } // namespace libff
libff::alt_bn128_G1::is_in_safe_subgroup
bool is_in_safe_subgroup() const
Definition: alt_bn128_g1.cpp:359
libff::Fp_model::random_element
static Fp_model< n, modulus > random_element()
returns random element of Fp_model
libff::alt_bn128_G1::is_zero
bool is_zero() const
Definition: alt_bn128_g1.cpp:91
libff::alt_bn128_G1::to_affine_coordinates
void to_affine_coordinates()
Definition: alt_bn128_g1.cpp:68
libff
Definition: ffi.cpp:8
libff::Fp_model::squared
Fp_model squared() const
libff::alt_bn128_G1::mul_by_cofactor
alt_bn128_G1 mul_by_cofactor() const
Definition: alt_bn128_g1.cpp:328
libff::alt_bn128_G1::X
alt_bn128_Fq X
Definition: alt_bn128_g1.hpp:44
libff::Fp_model< alt_bn128_q_limbs, alt_bn128_modulus_q >::zero
static const Fp_model< n, modulus > & zero()
libff::Fp_model::is_zero
bool is_zero() const
libff::alt_bn128_G1::write_compressed
void write_compressed(std::ostream &) const
Definition: alt_bn128_g1.cpp:383
libff::operator>>
std::istream & operator>>(std::istream &in, alt_bn128_G1 &g)
Definition: alt_bn128_g1.cpp:446
libff::alt_bn128_G1::coeff_b
static alt_bn128_Fq coeff_b
Definition: alt_bn128_g1.hpp:33
libff::alt_bn128_G1::read_compressed
static void read_compressed(std::istream &, alt_bn128_G1 &)
Definition: alt_bn128_g1.cpp:409
libff::alt_bn128_G1::alt_bn128_G1
alt_bn128_G1()
Definition: alt_bn128_g1.cpp:29
libff::Fp_model::inverse
Fp_model inverse() const
libff::alt_bn128_G1::write_uncompressed
void write_uncompressed(std::ostream &) const
Definition: alt_bn128_g1.cpp:374
libff::alt_bn128_G1::operator!=
bool operator!=(const alt_bn128_G1 &other) const
Definition: alt_bn128_g1.cpp:129
libff::alt_bn128_G1::Y
alt_bn128_Fq Y
Definition: alt_bn128_g1.hpp:44
libff::alt_bn128_G1::G1_zero
static alt_bn128_G1 G1_zero
Definition: alt_bn128_g1.hpp:30
libff::Fp_model::sqrt
Fp_model sqrt() const
HAS TO BE A SQUARE (else does not terminate)
libff::Fp_model< alt_bn128_q_limbs, alt_bn128_modulus_q >::one
static const Fp_model< n, modulus > & one()
libff::alt_bn128_G1::operator==
bool operator==(const alt_bn128_G1 &other) const
Definition: alt_bn128_g1.cpp:93
libff::alt_bn128_G1::is_special
bool is_special() const
Definition: alt_bn128_g1.cpp:86
libff::consume_OUTPUT_SEPARATOR
void consume_OUTPUT_SEPARATOR(std::istream &in)
libff::alt_bn128_G1::G1_one
static alt_bn128_G1 G1_one
Definition: alt_bn128_g1.hpp:31
libff::Fp_model< alt_bn128_q_limbs, alt_bn128_modulus_q >::num_limbs
static const mp_size_t num_limbs
Definition: fp.hpp:47
libff::alt_bn128_G1::operator+
alt_bn128_G1 operator+(const alt_bn128_G1 &other) const
Definition: alt_bn128_g1.cpp:134
libff::alt_bn128_G1::h
static bigint< h_limbs > h
Definition: alt_bn128_g1.hpp:42
libff::alt_bn128_G1::add
alt_bn128_G1 add(const alt_bn128_G1 &other) const
Definition: alt_bn128_g1.cpp:149
libff::alt_bn128_G1::Z
alt_bn128_Fq Z
Definition: alt_bn128_g1.hpp:44
libff::alt_bn128_G1::operator-
alt_bn128_G1 operator-() const
Definition: alt_bn128_g1.cpp:139
libff::alt_bn128_G1::random_element
static alt_bn128_G1 random_element()
Definition: alt_bn128_g1.cpp:369
libff::alt_bn128_G1::fixed_base_exp_window_table
static std::vector< size_t > fixed_base_exp_window_table
Definition: alt_bn128_g1.hpp:29
libff::alt_bn128_Fq
Fp_model< alt_bn128_q_limbs, alt_bn128_modulus_q > alt_bn128_Fq
Definition: alt_bn128_init.hpp:31
libff::alt_bn128_G1::to_special
void to_special()
Definition: alt_bn128_g1.cpp:84
alt_bn128_g1.hpp
libff::alt_bn128_G1::coeff_a
static alt_bn128_Fq coeff_a
Definition: alt_bn128_g1.hpp:32
libff::alt_bn128_G1::print_coordinates
void print_coordinates() const
Definition: alt_bn128_g1.cpp:52
libff::Fp_model::as_bigint
bigint< n > as_bigint() const
libff::alt_bn128_G1::batch_to_special_all_non_zeros
static void batch_to_special_all_non_zeros(std::vector< alt_bn128_G1 > &vec)
Definition: alt_bn128_g1.cpp:456
libff::Fp_model< alt_bn128_q_limbs, alt_bn128_modulus_q >
libff::alt_bn128_G1::one
static const alt_bn128_G1 & one()
Definition: alt_bn128_g1.cpp:367
libff::operator<<
std::ostream & operator<<(std::ostream &out, const alt_bn128_G1 &g)
Definition: alt_bn128_g1.cpp:436
libff::alt_bn128_G1::print
void print() const
Definition: alt_bn128_g1.cpp:36
libff::alt_bn128_G1::zero
static const alt_bn128_G1 & zero()
Definition: alt_bn128_g1.cpp:365
libff::alt_bn128_G1::wnaf_window_table
static std::vector< size_t > wnaf_window_table
Definition: alt_bn128_g1.hpp:28
libff::alt_bn128_G1::dbl
alt_bn128_G1 dbl() const
Definition: alt_bn128_g1.cpp:285
libff::alt_bn128_G1
Definition: alt_bn128_g1.hpp:21
libff::alt_bn128_G1::is_well_formed
bool is_well_formed() const
Definition: alt_bn128_g1.cpp:334
libff::alt_bn128_G1::read_uncompressed
static void read_uncompressed(std::istream &, alt_bn128_G1 &)
Definition: alt_bn128_g1.cpp:395
libff::alt_bn128_G1::mixed_add
alt_bn128_G1 mixed_add(const alt_bn128_G1 &other) const
Definition: alt_bn128_g1.cpp:208
libff::alt_bn128_coeff_b
alt_bn128_Fq alt_bn128_coeff_b
Definition: alt_bn128_init.cpp:18