Clearmatics Libff  0.1
C++ library for Finite Fields and Elliptic Curves
edwards_g2.cpp
Go to the documentation of this file.
1 
9 
10 namespace libff
11 {
12 
13 #ifdef PROFILE_OP_COUNTS
14 long long edwards_G2::add_cnt = 0;
15 long long edwards_G2::dbl_cnt = 0;
16 #endif
17 
18 std::vector<size_t> edwards_G2::wnaf_window_table;
19 std::vector<size_t> edwards_G2::fixed_base_exp_window_table;
20 
21 edwards_G2 edwards_G2::G2_zero;
22 edwards_G2 edwards_G2::G2_one;
23 
25 {
26  this->X = G2_zero.X;
27  this->Y = G2_zero.Y;
28  this->Z = G2_zero.Z;
29 }
30 
32 {
33  // should be
34  // edwards_Fq3(
35  // edwards_twist_mul_by_a_c0 * elt.coeffs[2],
36  // edwards_twist_mul_by_a_c1 * elt.coeffs[0],
37  // edwards_twist_mul_by_a_c2 * elt.coeffs[1])
38  // but optimizing the fact that edwards_twist_mul_by_a_c1 =
39  // edwards_twist_mul_by_a_c2 = 1
40  return edwards_Fq3(
42  elt.coeffs[0],
43  elt.coeffs[1]);
44 }
45 
47 {
48  return edwards_Fq3(
52 }
53 
54 void edwards_G2::print() const
55 {
56  if (this->is_zero()) {
57  printf("O\n");
58  } else {
59  edwards_G2 copy(*this);
60  copy.to_affine_coordinates();
61  gmp_printf(
62  "(%Nd*z^2 + %Nd*z + %Nd , %Nd*z^2 + %Nd*z + %Nd)\n",
63  copy.X.coeffs[2].as_bigint().data,
65  copy.X.coeffs[1].as_bigint().data,
67  copy.X.coeffs[0].as_bigint().data,
69  copy.Y.coeffs[2].as_bigint().data,
71  copy.Y.coeffs[1].as_bigint().data,
73  copy.Y.coeffs[0].as_bigint().data,
75  }
76 }
77 
79 {
80  if (this->is_zero()) {
81  printf("O\n");
82  } else {
83  gmp_printf(
84  "(%Nd*z^2 + %Nd*z + %Nd : %Nd*z^2 + %Nd*z + %Nd : %Nd*z^2 + %Nd*z "
85  "+ %Nd)\n",
86  this->X.coeffs[2].as_bigint().data,
88  this->X.coeffs[1].as_bigint().data,
90  this->X.coeffs[0].as_bigint().data,
92  this->Y.coeffs[2].as_bigint().data,
94  this->Y.coeffs[1].as_bigint().data,
96  this->Y.coeffs[0].as_bigint().data,
98  this->Z.coeffs[2].as_bigint().data,
100  this->Z.coeffs[1].as_bigint().data,
102  this->Z.coeffs[0].as_bigint().data,
104  }
105 }
106 
108 {
109  if (this->is_zero()) {
110  this->X = edwards_Fq3::zero();
111  this->Y = edwards_Fq3::one();
112  this->Z = edwards_Fq3::one();
113  } else {
114  // go from inverted coordinates to projective coordinates
115  edwards_Fq3 tX = this->Y * this->Z;
116  edwards_Fq3 tY = this->X * this->Z;
117  edwards_Fq3 tZ = this->X * this->Y;
118  // go from projective coordinates to affine coordinates
119  edwards_Fq3 tZ_inv = tZ.inverse();
120  this->X = tX * tZ_inv;
121  this->Y = tY * tZ_inv;
122  this->Z = edwards_Fq3::one();
123  }
124 }
125 
127 {
128  if (this->Z.is_zero()) {
129  return;
130  }
131 
132 #if defined(DEBUG) && !defined(NDEBUG)
133  const edwards_G2 copy(*this);
134 #endif
135 
136  edwards_Fq3 Z_inv = this->Z.inverse();
137  this->X = this->X * Z_inv;
138  this->Y = this->Y * Z_inv;
139  this->Z = edwards_Fq3::one();
140 
141 #ifdef DEBUG
142  assert((*this) == copy);
143 #endif
144 }
145 
147 {
148  return (this->is_zero() || this->Z == edwards_Fq3::one());
149 }
150 
152 {
153  return (this->Y.is_zero() && this->Z.is_zero());
154 }
155 
156 bool edwards_G2::operator==(const edwards_G2 &other) const
157 {
158  if (this->is_zero()) {
159  return other.is_zero();
160  }
161 
162  if (other.is_zero()) {
163  return false;
164  }
165 
166  /* now neither is O */
167 
168  // X1/Z1 = X2/Z2 <=> X1*Z2 = X2*Z1
169  if ((this->X * other.Z) != (other.X * this->Z)) {
170  return false;
171  }
172 
173  // Y1/Z1 = Y2/Z2 <=> Y1*Z2 = Y2*Z1
174  if ((this->Y * other.Z) != (other.Y * this->Z)) {
175  return false;
176  }
177 
178  return true;
179 }
180 
181 bool edwards_G2::operator!=(const edwards_G2 &other) const
182 {
183  return !(operator==(other));
184 }
185 
187 {
188  // handle special cases having to do with O
189  if (this->is_zero()) {
190  return other;
191  }
192 
193  if (other.is_zero()) {
194  return (*this);
195  }
196 
197  return this->add(other);
198 }
199 
201 {
202  return edwards_G2(-(this->X), this->Y, this->Z);
203 }
204 
206 {
207  return (*this) + (-other);
208 }
209 
211 {
212 #ifdef PROFILE_OP_COUNTS
213  this->add_cnt++;
214 #endif
215  // NOTE: does not handle O and pts of order 2,4
216  // http://www.hyperelliptic.org/EFD/g1p/auto-twisted-inverted.html#addition-add-2008-bbjlp
217 
218  // A = Z1*Z2
219  const edwards_Fq3 A = (this->Z) * (other.Z);
220  // B = d*A^2
222  // C = X1*X2
223  const edwards_Fq3 C = (this->X) * (other.X);
224  // D = Y1*Y2
225  const edwards_Fq3 D = (this->Y) * (other.Y);
226  // E = C*D
227  const edwards_Fq3 E = C * D;
228  // H = C-a*D
229  const edwards_Fq3 H = C - edwards_G2::mul_by_a(D);
230  // I = (X1+Y1)*(X2+Y2)-C-D
231  const edwards_Fq3 I = (this->X + this->Y) * (other.X + other.Y) - C - D;
232  // X3 = (E+B)*H
233  const edwards_Fq3 X3 = (E + B) * H;
234  // Y3 = (E-B)*I
235  const edwards_Fq3 Y3 = (E - B) * I;
236  // Z3 = A*H*I
237  const edwards_Fq3 Z3 = A * H * I;
238 
239  return edwards_G2(X3, Y3, Z3);
240 }
241 
243 {
244 #ifdef PROFILE_OP_COUNTS
245  this->add_cnt++;
246 #endif
247  // handle special cases having to do with O
248  if (this->is_zero()) {
249  return other;
250  }
251 
252  if (other.is_zero()) {
253  return *this;
254  }
255 
256 #ifdef DEBUG
257  assert(other.is_special());
258 #endif
259 
260  // NOTE: does not handle O and pts of order 2,4
261  // http://www.hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html#addition-madd-2007-lb
262 
263  // A = Z1*Z2
264  const edwards_Fq3 A = this->Z;
265  // B = d*A^2
267  // C = X1*X2
268  const edwards_Fq3 C = (this->X) * (other.X);
269  // D = Y1*Y2
270  const edwards_Fq3 D = (this->Y) * (other.Y);
271  // E = C*D
272  const edwards_Fq3 E = C * D;
273  // H = C-a*D
274  const edwards_Fq3 H = C - edwards_G2::mul_by_a(D);
275  // I = (X1+Y1)*(X2+Y2)-C-D
276  const edwards_Fq3 I = (this->X + this->Y) * (other.X + other.Y) - C - D;
277  // X3 = (E+B)*H
278  const edwards_Fq3 X3 = (E + B) * H;
279  // Y3 = (E-B)*I
280  const edwards_Fq3 Y3 = (E - B) * I;
281  // Z3 = A*H*I
282  const edwards_Fq3 Z3 = A * H * I;
283 
284  return edwards_G2(X3, Y3, Z3);
285 }
286 
288 {
289 #ifdef PROFILE_OP_COUNTS
290  this->dbl_cnt++;
291 #endif
292  if (this->is_zero()) {
293  return (*this);
294  } else {
295  // NOTE: does not handle O and pts of order 2,4
296  // http://www.hyperelliptic.org/EFD/g1p/auto-twisted-inverted.html#doubling-dbl-2008-bbjlp
297 
298  // A = X1^2
299  const edwards_Fq3 A = (this->X).squared();
300  // B = Y1^2
301  const edwards_Fq3 B = (this->Y).squared();
302  // U = a*B
303  const edwards_Fq3 U = edwards_G2::mul_by_a(B);
304  // C = A+U
305  const edwards_Fq3 C = A + U;
306  // D = A-U
307  const edwards_Fq3 D = A - U;
308  // E = (X1+Y1)^2-A-B
309  const edwards_Fq3 E = (this->X + this->Y).squared() - A - B;
310  // X3 = C*D
311  const edwards_Fq3 X3 = C * D;
312  const edwards_Fq3 dZZ = edwards_G2::mul_by_d(this->Z.squared());
313  // Y3 = E*(C-2*d*Z1^2)
314  const edwards_Fq3 Y3 = E * (C - dZZ - dZZ);
315  // Z3 = D*E
316  const edwards_Fq3 Z3 = D * E;
317 
318  return edwards_G2(X3, Y3, Z3);
319  }
320 }
321 
323 {
324  return edwards_G2(
325  (this->X).Frobenius_map(1),
326  edwards_twist_mul_by_q_Y * (this->Y).Frobenius_map(1),
327  edwards_twist_mul_by_q_Z * (this->Z).Frobenius_map(1));
328 }
329 
331 {
332  // Note that point at infinity is the only special case we must check as
333  // inverted representation does no cover points (0, +-c) and (+-c, 0).
334  if (this->is_zero()) {
335  return true;
336  } else {
337  // a x^2 + y^2 = 1 + d x^2 y^2
338  //
339  // We are using inverted, so equation we need to check is actually
340  //
341  // a (z/x)^2 + (z/y)^2 = 1 + d z^4 / (x^2 * y^2)
342  // z^2 (a y^2 + x^2 - dz^2) = x^2 y^2
343  edwards_Fq3 X2 = this->X.squared();
344  edwards_Fq3 Y2 = this->Y.squared();
345  edwards_Fq3 Z2 = this->Z.squared();
348  return (Z2 * (aY2 + X2 - dZ2) == X2 * Y2);
349  }
350 }
351 
352 const edwards_G2 &edwards_G2::zero() { return G2_zero; }
353 
354 const edwards_G2 &edwards_G2::one() { return G2_one; }
355 
357 {
358  return edwards_Fr::random_element().as_bigint() * G2_one;
359 }
360 
361 void edwards_G2::write_uncompressed(std::ostream &out) const
362 {
363  edwards_G2 copy(*this);
364  copy.to_affine_coordinates();
365  out << copy.X << OUTPUT_SEPARATOR << copy.Y;
366 }
367 
368 void edwards_G2::write_compressed(std::ostream &out) const
369 {
370  edwards_G2 copy(*this);
371  copy.to_affine_coordinates();
372  /* storing LSB of Y */
373  out << copy.X << OUTPUT_SEPARATOR
374  << (copy.Y.coeffs[0].as_bigint().data[0] & 1);
375 }
376 
377 void edwards_G2::read_uncompressed(std::istream &in, edwards_G2 &g)
378 {
379  edwards_Fq3 tX, tY;
380  in >> tX;
382  in >> tY;
383 
384  // using inverted coordinates
385  g.X = tY;
386  g.Y = tX;
387  g.Z = tX * tY;
388 
389 #ifdef USE_MIXED_ADDITION
390  g.to_special();
391 #endif
392 }
393 
394 void edwards_G2::read_compressed(std::istream &in, edwards_G2 &g)
395 {
396  // a x^2 + y^2 = 1 + d x^2 y^2
397  // y = sqrt((1-ax^2)/(1-dx^2))
398  edwards_Fq3 tX, tY;
399  unsigned char Y_lsb;
400  in >> tX;
402 
403  in.read((char *)&Y_lsb, 1);
404  Y_lsb -= '0';
405 
406  edwards_Fq3 tX2 = tX.squared();
407  const edwards_Fq3 tY2 =
409  (edwards_Fq3::one() - edwards_G2::mul_by_d(tX2)).inverse();
410  tY = tY2.sqrt();
411 
412  if ((tY.coeffs[0].as_bigint().data[0] & 1) != Y_lsb) {
413  tY = -tY;
414  }
415 
416  // using inverted coordinates
417  g.X = tY;
418  g.Y = tX;
419  g.Z = tX * tY;
420 
421 #ifdef USE_MIXED_ADDITION
422  g.to_special();
423 #endif
424 }
425 
426 std::ostream &operator<<(std::ostream &out, const edwards_G2 &g)
427 {
428 #ifdef NO_PT_COMPRESSION
429  g.write_uncompressed(out);
430 #else
431  g.write_compressed(out);
432 #endif
433  return out;
434 }
435 
436 std::istream &operator>>(std::istream &in, edwards_G2 &g)
437 {
438 #ifdef NO_PT_COMPRESSION
440 #else
442 #endif
443  return in;
444 }
445 
446 void edwards_G2::batch_to_special_all_non_zeros(std::vector<edwards_G2> &vec)
447 {
448  std::vector<edwards_Fq3> Z_vec;
449  Z_vec.reserve(vec.size());
450 
451  for (auto &el : vec) {
452  Z_vec.emplace_back(el.Z);
453  }
454  batch_invert<edwards_Fq3>(Z_vec);
455 
456  const edwards_Fq3 one = edwards_Fq3::one();
457 
458  for (size_t i = 0; i < vec.size(); ++i) {
459  vec[i].X = vec[i].X * Z_vec[i];
460  vec[i].Y = vec[i].Y * Z_vec[i];
461  vec[i].Z = one;
462  }
463 }
464 
465 } // namespace libff
libff::edwards_twist_mul_by_d_c0
edwards_Fq edwards_twist_mul_by_d_c0
Definition: edwards_init.cpp:26
libff::edwards_G2::mixed_add
edwards_G2 mixed_add(const edwards_G2 &other) const
Definition: edwards_g2.cpp:242
libff::edwards_G2
Definition: edwards_g2.hpp:22
libff::edwards_G2::is_special
bool is_special() const
Definition: edwards_g2.cpp:146
libff::Fp_model::random_element
static Fp_model< n, modulus > random_element()
returns random element of Fp_model
libff::edwards_G2::one
static const edwards_G2 & one()
Definition: edwards_g2.cpp:354
libff
Definition: ffi.cpp:8
libff::edwards_G2::G2_one
static edwards_G2 G2_one
Definition: edwards_g2.hpp:33
libff::edwards_G2::batch_to_special_all_non_zeros
static void batch_to_special_all_non_zeros(std::vector< edwards_G2 > &vec)
Definition: edwards_g2.cpp:446
libff::Fp3_model< edwards_q_limbs, edwards_modulus_q >::one
static Fp3_model< n, modulus > one()
libff::edwards_G2::G2_zero
static edwards_G2 G2_zero
Definition: edwards_g2.hpp:32
libff::edwards_G2::print
void print() const
Definition: edwards_g2.cpp:54
libff::edwards_G2::operator==
bool operator==(const edwards_G2 &other) const
Definition: edwards_g2.cpp:156
libff::edwards_G2::mul_by_q
edwards_G2 mul_by_q() const
Definition: edwards_g2.cpp:322
libff::edwards_G2::operator+
edwards_G2 operator+(const edwards_G2 &other) const
Definition: edwards_g2.cpp:186
libff::edwards_G2::Z
edwards_Fq3 Z
Definition: edwards_g2.hpp:35
libff::operator>>
std::istream & operator>>(std::istream &in, alt_bn128_G1 &g)
Definition: alt_bn128_g1.cpp:446
libff::edwards_G2::mul_by_a
static edwards_Fq3 mul_by_a(const edwards_Fq3 &elt)
Definition: edwards_g2.cpp:31
edwards_g2.hpp
libff::edwards_G2::operator-
edwards_G2 operator-() const
Definition: edwards_g2.cpp:200
libff::edwards_twist_mul_by_q_Z
edwards_Fq edwards_twist_mul_by_q_Z
Definition: edwards_init.cpp:30
libff::edwards_G2::X
edwards_Fq3 X
Definition: edwards_g2.hpp:35
libff::edwards_G2::zero
static const edwards_G2 & zero()
Definition: edwards_g2.cpp:352
libff::Fp3_model::coeffs
my_Fp coeffs[3]
Definition: fp3.hpp:59
libff::edwards_G2::is_zero
bool is_zero() const
Definition: edwards_g2.cpp:151
libff::edwards_G2::dbl
edwards_G2 dbl() const
Definition: edwards_g2.cpp:287
libff::edwards_G2::to_affine_coordinates
void to_affine_coordinates()
Definition: edwards_g2.cpp:107
OUTPUT_SEPARATOR
#define OUTPUT_SEPARATOR
Definition: serialization.hpp:69
libff::edwards_G2::operator!=
bool operator!=(const edwards_G2 &other) const
Definition: edwards_g2.cpp:181
libff::edwards_G2::wnaf_window_table
static std::vector< size_t > wnaf_window_table
Definition: edwards_g2.hpp:29
libff::edwards_G2::mul_by_d
static edwards_Fq3 mul_by_d(const edwards_Fq3 &elt)
Definition: edwards_g2.cpp:46
libff::consume_OUTPUT_SEPARATOR
void consume_OUTPUT_SEPARATOR(std::istream &in)
libff::Fp_model< edwards_q_limbs, edwards_modulus_q >::num_limbs
static const mp_size_t num_limbs
Definition: fp.hpp:47
libff::edwards_G2::is_well_formed
bool is_well_formed() const
Definition: edwards_g2.cpp:330
libff::edwards_G2::print_coordinates
void print_coordinates() const
Definition: edwards_g2.cpp:78
libff::edwards_twist_mul_by_a_c0
edwards_Fq edwards_twist_mul_by_a_c0
Definition: edwards_init.cpp:23
libff::Fp3_model< edwards_q_limbs, edwards_modulus_q >
libff::edwards_Fq3
Fp3_model< edwards_q_limbs, edwards_modulus_q > edwards_Fq3
Definition: edwards_init.hpp:31
libff::edwards_twist_mul_by_q_Y
edwards_Fq edwards_twist_mul_by_q_Y
Definition: edwards_init.cpp:29
libff::Fp_model::as_bigint
bigint< n > as_bigint() const
libff::edwards_G2::write_uncompressed
void write_uncompressed(std::ostream &) const
Definition: edwards_g2.cpp:361
libff::edwards_G2::add
edwards_G2 add(const edwards_G2 &other) const
Definition: edwards_g2.cpp:210
libff::edwards_twist_mul_by_d_c1
edwards_Fq edwards_twist_mul_by_d_c1
Definition: edwards_init.cpp:27
libff::edwards_G2::Y
edwards_Fq3 Y
Definition: edwards_g2.hpp:35
libff::operator<<
std::ostream & operator<<(std::ostream &out, const alt_bn128_G1 &g)
Definition: alt_bn128_g1.cpp:436
libff::Fp3_model::inverse
Fp3_model inverse() const
libff::Fp3_model::sqrt
Fp3_model sqrt() const
HAS TO BE A SQUARE (else does not terminate)
libff::Fp3_model::is_zero
bool is_zero() const
Definition: fp3.hpp:89
libff::edwards_G2::to_special
void to_special()
Definition: edwards_g2.cpp:126
libff::edwards_G2::read_compressed
static void read_compressed(std::istream &, edwards_G2 &)
Definition: edwards_g2.cpp:394
libff::edwards_G2::random_element
static edwards_G2 random_element()
Definition: edwards_g2.cpp:356
libff::edwards_G2::write_compressed
void write_compressed(std::ostream &) const
Definition: edwards_g2.cpp:368
libff::edwards_twist_mul_by_d_c2
edwards_Fq edwards_twist_mul_by_d_c2
Definition: edwards_init.cpp:28
libff::edwards_G2::edwards_G2
edwards_G2()
Definition: edwards_g2.cpp:24
libff::edwards_G2::fixed_base_exp_window_table
static std::vector< size_t > fixed_base_exp_window_table
Definition: edwards_g2.hpp:30
libff::Fp3_model::squared
Fp3_model squared() const
libff::edwards_G2::read_uncompressed
static void read_uncompressed(std::istream &, edwards_G2 &)
Definition: edwards_g2.cpp:377
libff::Fp3_model< edwards_q_limbs, edwards_modulus_q >::zero
static Fp3_model< n, modulus > zero()