Clearmatics Libff  0.1
C++ library for Finite Fields and Elliptic Curves
mnt4_g1.cpp
Go to the documentation of this file.
1 
15 
16 namespace libff
17 {
18 
19 #ifdef PROFILE_OP_COUNTS
20 long long mnt4_G1::add_cnt = 0;
21 long long mnt4_G1::dbl_cnt = 0;
22 #endif
23 
24 std::vector<size_t> mnt4_G1::wnaf_window_table;
25 std::vector<size_t> mnt4_G1::fixed_base_exp_window_table;
26 mnt4_G1 mnt4_G1::G1_zero;
27 mnt4_G1 mnt4_G1::G1_one;
30 bigint<mnt4_G1::h_limbs> mnt4_G1::h;
31 
33 {
34  this->X = G1_zero.X;
35  this->Y = G1_zero.Y;
36  this->Z = G1_zero.Z;
37 }
38 
39 void mnt4_G1::print() const
40 {
41  if (this->is_zero()) {
42  printf("O\n");
43  } else {
44  mnt4_G1 copy(*this);
45  copy.to_affine_coordinates();
46  gmp_printf(
47  "(%Nd , %Nd)\n",
48  copy.X.as_bigint().data,
50  copy.Y.as_bigint().data,
52  }
53 }
54 
56 {
57  if (this->is_zero()) {
58  printf("O\n");
59  } else {
60  gmp_printf(
61  "(%Nd : %Nd : %Nd)\n",
62  this->X.as_bigint().data,
64  this->Y.as_bigint().data,
66  this->Z.as_bigint().data,
68  }
69 }
70 
72 {
73  if (this->is_zero()) {
74  this->X = mnt4_Fq::zero();
75  this->Y = mnt4_Fq::one();
76  this->Z = mnt4_Fq::zero();
77  } else {
78  const mnt4_Fq Z_inv = Z.inverse();
79  this->X = this->X * Z_inv;
80  this->Y = this->Y * Z_inv;
81  this->Z = mnt4_Fq::one();
82  }
83 }
84 
86 
87 bool mnt4_G1::is_special() const
88 {
89  return (this->is_zero() || this->Z == mnt4_Fq::one());
90 }
91 
92 bool mnt4_G1::is_zero() const
93 {
94  return (this->X.is_zero() && this->Z.is_zero());
95 }
96 
97 bool mnt4_G1::operator==(const mnt4_G1 &other) const
98 {
99  if (this->is_zero()) {
100  return other.is_zero();
101  }
102 
103  if (other.is_zero()) {
104  return false;
105  }
106 
107  /* now neither is O */
108 
109  // X1/Z1 = X2/Z2 <=> X1*Z2 = X2*Z1
110  if ((this->X * other.Z) != (other.X * this->Z)) {
111  return false;
112  }
113 
114  // Y1/Z1 = Y2/Z2 <=> Y1*Z2 = Y2*Z1
115  if ((this->Y * other.Z) != (other.Y * this->Z)) {
116  return false;
117  }
118 
119  return true;
120 }
121 
122 bool mnt4_G1::operator!=(const mnt4_G1 &other) const
123 {
124  return !(operator==(other));
125 }
126 
127 mnt4_G1 mnt4_G1::operator+(const mnt4_G1 &other) const
128 {
129  // handle special cases having to do with O
130  if (this->is_zero()) {
131  return other;
132  }
133 
134  if (other.is_zero()) {
135  return *this;
136  }
137 
138  // no need to handle points of order 2,4
139  // (they cannot exist in a prime-order subgroup)
140 
141  // handle double case, and then all the rest
142  /*
143  The code below is equivalent to (but faster than) the snippet below:
144 
145  if (this->operator==(other))
146  {
147  return this->dbl();
148  }
149  else
150  {
151  return this->add(other);
152  }
153  */
154 
155  // X1Z2 = X1*Z2
156  const mnt4_Fq X1Z2 = (this->X) * (other.Z);
157  // X2Z1 = X2*Z1
158  const mnt4_Fq X2Z1 = (this->Z) * (other.X);
159 
160  // (used both in add and double checks)
161 
162  // Y1Z2 = Y1*Z2
163  const mnt4_Fq Y1Z2 = (this->Y) * (other.Z);
164  // Y2Z1 = Y2*Z1
165  const mnt4_Fq Y2Z1 = (this->Z) * (other.Y);
166 
167  if (X1Z2 == X2Z1 && Y1Z2 == Y2Z1) {
168  // perform dbl case
169  // XX = X1^2
170  const mnt4_Fq XX = (this->X).squared();
171  // ZZ = Z1^2
172  const mnt4_Fq ZZ = (this->Z).squared();
173  // w = a*ZZ + 3*XX
174  const mnt4_Fq w = mnt4_G1::coeff_a * ZZ + (XX + XX + XX);
175  const mnt4_Fq Y1Z1 = (this->Y) * (this->Z);
176  // s = 2*Y1*Z1
177  const mnt4_Fq s = Y1Z1 + Y1Z1;
178  // ss = s^2
179  const mnt4_Fq ss = s.squared();
180  // sss = s*ss
181  const mnt4_Fq sss = s * ss;
182  // R = Y1*s
183  const mnt4_Fq R = (this->Y) * s;
184  // RR = R^2
185  const mnt4_Fq RR = R.squared();
186  // B = (X1+R)^2 - XX - RR
187  const mnt4_Fq B = ((this->X) + R).squared() - XX - RR;
188  // h = w^2 - 2*B
189  const mnt4_Fq h = w.squared() - (B + B);
190  // X3 = h*s
191  const mnt4_Fq X3 = h * s;
192  // Y3 = w*(B-h) - 2*RR
193  const mnt4_Fq Y3 = w * (B - h) - (RR + RR);
194  // Z3 = sss
195  const mnt4_Fq Z3 = sss;
196 
197  return mnt4_G1(X3, Y3, Z3);
198  }
199 
200  // if we have arrived here we are in the add case
201  // Z1Z2 = Z1*Z2
202  const mnt4_Fq Z1Z2 = (this->Z) * (other.Z);
203  // u = Y2*Z1-Y1Z2
204  const mnt4_Fq u = Y2Z1 - Y1Z2;
205  // uu = u^2
206  const mnt4_Fq uu = u.squared();
207  // v = X2*Z1-X1Z2
208  const mnt4_Fq v = X2Z1 - X1Z2;
209  // vv = v^2
210  const mnt4_Fq vv = v.squared();
211  // vvv = v*vv
212  const mnt4_Fq vvv = v * vv;
213  // R = vv*X1Z2
214  const mnt4_Fq R = vv * X1Z2;
215  // A = uu*Z1Z2 - vvv - 2*R
216  const mnt4_Fq A = uu * Z1Z2 - (vvv + R + R);
217  // X3 = v*A
218  const mnt4_Fq X3 = v * A;
219  // Y3 = u*(R-A) - vvv*Y1Z2
220  const mnt4_Fq Y3 = u * (R - A) - vvv * Y1Z2;
221  // Z3 = vvv*Z1Z2
222  const mnt4_Fq Z3 = vvv * Z1Z2;
223 
224  return mnt4_G1(X3, Y3, Z3);
225 }
226 
228 {
229  return mnt4_G1(this->X, -(this->Y), this->Z);
230 }
231 
232 mnt4_G1 mnt4_G1::operator-(const mnt4_G1 &other) const
233 {
234  return (*this) + (-other);
235 }
236 
237 mnt4_G1 mnt4_G1::add(const mnt4_G1 &other) const
238 {
239  // handle special cases having to do with O
240  if (this->is_zero()) {
241  return other;
242  }
243 
244  if (other.is_zero()) {
245  return (*this);
246  }
247 
248  // no need to handle points of order 2,4
249  // (they cannot exist in a prime-order subgroup)
250 
251  // handle double case
252  if (this->operator==(other)) {
253  return this->dbl();
254  }
255 
256 #ifdef PROFILE_OP_COUNTS
257  this->add_cnt++;
258 #endif
259  // NOTE: does not handle O and pts of order 2,4
260  // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-projective.html#addition-add-1998-cmo-2
261 
262  // Y1Z2 = Y1*Z2
263  const mnt4_Fq Y1Z2 = (this->Y) * (other.Z);
264  // X1Z2 = X1*Z2
265  const mnt4_Fq X1Z2 = (this->X) * (other.Z);
266  // Z1Z2 = Z1*Z2
267  const mnt4_Fq Z1Z2 = (this->Z) * (other.Z);
268  // u = Y2*Z1-Y1Z2
269  const mnt4_Fq u = (other.Y) * (this->Z) - Y1Z2;
270  // uu = u^2
271  const mnt4_Fq uu = u.squared();
272  // v = X2*Z1-X1Z2
273  const mnt4_Fq v = (other.X) * (this->Z) - X1Z2;
274  // vv = v^2
275  const mnt4_Fq vv = v.squared();
276  // vvv = v*vv
277  const mnt4_Fq vvv = v * vv;
278  // R = vv*X1Z2
279  const mnt4_Fq R = vv * X1Z2;
280  // A = uu*Z1Z2 - vvv - 2*R
281  const mnt4_Fq A = uu * Z1Z2 - (vvv + R + R);
282  // X3 = v*A
283  const mnt4_Fq X3 = v * A;
284  // Y3 = u*(R-A) - vvv*Y1Z2
285  const mnt4_Fq Y3 = u * (R - A) - vvv * Y1Z2;
286  // Z3 = vvv*Z1Z2
287  const mnt4_Fq Z3 = vvv * Z1Z2;
288 
289  return mnt4_G1(X3, Y3, Z3);
290 }
291 
292 mnt4_G1 mnt4_G1::mixed_add(const mnt4_G1 &other) const
293 {
294 #ifdef PROFILE_OP_COUNTS
295  this->add_cnt++;
296 #endif
297  // NOTE: does not handle O and pts of order 2,4
298  // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-projective.html#addition-add-1998-cmo-2
299  // assert(other.Z == mnt4_Fq::one());
300 
301  if (this->is_zero()) {
302  return other;
303  }
304 
305  if (other.is_zero()) {
306  return (*this);
307  }
308 
309 #ifdef DEBUG
310  assert(other.is_special());
311 #endif
312 
313  // X1Z2 = X1*Z2 (but other is special and not zero)
314  const mnt4_Fq &X1Z2 = (this->X);
315  // X2Z1 = X2*Z1
316  const mnt4_Fq X2Z1 = (this->Z) * (other.X);
317 
318  // (used both in add and double checks)
319 
320  // Y1Z2 = Y1*Z2 (but other is special and not zero)
321  const mnt4_Fq &Y1Z2 = (this->Y);
322  // Y2Z1 = Y2*Z1
323  const mnt4_Fq Y2Z1 = (this->Z) * (other.Y);
324 
325  if (X1Z2 == X2Z1 && Y1Z2 == Y2Z1) {
326  return this->dbl();
327  }
328 
329  // u = Y2*Z1-Y1
330  const mnt4_Fq u = Y2Z1 - this->Y;
331  // uu = u2
332  const mnt4_Fq uu = u.squared();
333  // v = X2*Z1-X1
334  const mnt4_Fq v = X2Z1 - this->X;
335  // vv = v2
336  const mnt4_Fq vv = v.squared();
337  // vvv = v*vv
338  const mnt4_Fq vvv = v * vv;
339  // R = vv*X1
340  const mnt4_Fq R = vv * this->X;
341  // A = uu*Z1-vvv-2*R
342  const mnt4_Fq A = uu * this->Z - vvv - R - R;
343  // X3 = v*A
344  const mnt4_Fq X3 = v * A;
345  // Y3 = u*(R-A)-vvv*Y1
346  const mnt4_Fq Y3 = u * (R - A) - vvv * this->Y;
347  // Z3 = vvv*Z1
348  const mnt4_Fq Z3 = vvv * this->Z;
349 
350  return mnt4_G1(X3, Y3, Z3);
351 }
352 
354 {
355 #ifdef PROFILE_OP_COUNTS
356  this->dbl_cnt++;
357 #endif
358  if (this->is_zero()) {
359  return (*this);
360  } else {
361  // NOTE: does not handle O and pts of order 2,4
362  // http://www.hyperelliptic.org/EFD/g1p/auto-shortw-projective.html#doubling-dbl-2007-bl
363 
364  // XX = X1^2
365  const mnt4_Fq XX = (this->X).squared();
366  // ZZ = Z1^2
367  const mnt4_Fq ZZ = (this->Z).squared();
368  // w = a*ZZ + 3*XX
369  const mnt4_Fq w = mnt4_G1::coeff_a * ZZ + (XX + XX + XX);
370  const mnt4_Fq Y1Z1 = (this->Y) * (this->Z);
371  // s = 2*Y1*Z1
372  const mnt4_Fq s = Y1Z1 + Y1Z1;
373  // ss = s^2
374  const mnt4_Fq ss = s.squared();
375  // sss = s*ss
376  const mnt4_Fq sss = s * ss;
377  // R = Y1*s
378  const mnt4_Fq R = (this->Y) * s;
379  // RR = R^2
380  const mnt4_Fq RR = R.squared();
381  // B = (X1+R)^2 - XX - RR
382  const mnt4_Fq B = ((this->X) + R).squared() - XX - RR;
383  // h = w^2 - 2*B
384  const mnt4_Fq h = w.squared() - (B + B);
385  // X3 = h*s
386  const mnt4_Fq X3 = h * s;
387  // Y3 = w*(B-h) - 2*RR
388  const mnt4_Fq Y3 = w * (B - h) - (RR + RR);
389  // Z3 = sss
390  const mnt4_Fq Z3 = sss;
391 
392  return mnt4_G1(X3, Y3, Z3);
393  }
394 }
395 
397 {
398  // Cofactor = 1
399  return (*this);
400 }
401 
403 {
404  if (this->is_zero()) {
405  return true;
406  } else {
407  // y^2 = x^3 + ax + b
408  //
409  // We are using projective, so equation we need to check is actually
410  //
411  // (y/z)^2 = (x/z)^3 + a (x/z) + b
412  // z y^2 = x^3 + a z^2 x + b z^3
413  //
414  // z (y^2 - b z^2) = x ( x^2 + a z^2)
415  const mnt4_Fq X2 = this->X.squared();
416  const mnt4_Fq Y2 = this->Y.squared();
417  const mnt4_Fq Z2 = this->Z.squared();
418 
419  return (
420  this->Z * (Y2 - mnt4_G1::coeff_b * Z2) ==
421  this->X * (X2 + mnt4_G1::coeff_a * Z2));
422  }
423 }
424 
425 bool mnt4_G1::is_in_safe_subgroup() const { return true; }
426 
427 const mnt4_G1 &mnt4_G1::zero() { return G1_zero; }
428 
429 const mnt4_G1 &mnt4_G1::one() { return G1_one; }
430 
432 {
433  return (scalar_field::random_element().as_bigint()) * G1_one;
434 }
435 
436 void mnt4_G1::write_uncompressed(std::ostream &out) const
437 {
438  mnt4_G1 copy(*this);
439  copy.to_affine_coordinates();
440 
441  out << (copy.is_zero() ? 1 : 0) << OUTPUT_SEPARATOR;
442  out << copy.X << OUTPUT_SEPARATOR << copy.Y;
443 }
444 
445 void mnt4_G1::write_compressed(std::ostream &out) const
446 {
447  mnt4_G1 copy(*this);
448  copy.to_affine_coordinates();
449 
450  out << (copy.is_zero() ? 1 : 0) << OUTPUT_SEPARATOR;
451  // storing LSB of Y
452  out << copy.X << OUTPUT_SEPARATOR << (copy.Y.as_bigint().data[0] & 1);
453 }
454 
455 void mnt4_G1::read_uncompressed(std::istream &in, mnt4_G1 &g)
456 {
457  char is_zero;
458  mnt4_Fq tX, tY;
459  in >> is_zero >> tX >> tY;
460  is_zero -= '0';
461 
462  // using projective coordinates
463  if (!is_zero) {
464  g.X = tX;
465  g.Y = tY;
466  g.Z = mnt4_Fq::one();
467  } else {
468  g = mnt4_G1::zero();
469  }
470 }
471 
472 void mnt4_G1::read_compressed(std::istream &in, mnt4_G1 &g)
473 {
474  char is_zero;
475  mnt4_Fq tX, tY;
476  in.read((char *)&is_zero, 1);
477  is_zero -= '0';
479 
480  unsigned char Y_lsb;
481  in >> tX;
483  in.read((char *)&Y_lsb, 1);
484  Y_lsb -= '0';
485 
486  // y = +/- sqrt(x^3 + a*x + b)
487  if (!is_zero) {
488  mnt4_Fq tX2 = tX.squared();
489  mnt4_Fq tY2 = (tX2 + mnt4_G1::coeff_a) * tX + mnt4_G1::coeff_b;
490  tY = tY2.sqrt();
491 
492  if ((tY.as_bigint().data[0] & 1) != Y_lsb) {
493  tY = -tY;
494  }
495  }
496 
497  // using projective coordinates
498  if (!is_zero) {
499  g.X = tX;
500  g.Y = tY;
501  g.Z = mnt4_Fq::one();
502  } else {
503  g = mnt4_G1::zero();
504  }
505 }
506 
507 std::ostream &operator<<(std::ostream &out, const mnt4_G1 &g)
508 {
509 #ifdef NO_PT_COMPRESSION
510  g.write_uncompressed(out);
511 #else
512  g.write_compressed(out);
513 #endif
514  return out;
515 }
516 
517 std::istream &operator>>(std::istream &in, mnt4_G1 &g)
518 {
519 #ifdef NO_PT_COMPRESSION
521 #else
523 #endif
524  return in;
525 }
526 
527 void mnt4_G1::batch_to_special_all_non_zeros(std::vector<mnt4_G1> &vec)
528 {
529  std::vector<mnt4_Fq> Z_vec;
530  Z_vec.reserve(vec.size());
531 
532  for (auto &el : vec) {
533  Z_vec.emplace_back(el.Z);
534  }
535  batch_invert<mnt4_Fq>(Z_vec);
536 
537  const mnt4_Fq one = mnt4_Fq::one();
538 
539  for (size_t i = 0; i < vec.size(); ++i) {
540  vec[i] = mnt4_G1(vec[i].X * Z_vec[i], vec[i].Y * Z_vec[i], one);
541  }
542 }
543 
544 } // namespace libff
libff::Fp_model::random_element
static Fp_model< n, modulus > random_element()
returns random element of Fp_model
libff
Definition: ffi.cpp:8
libff::mnt4_G1::Y
mnt4_Fq Y
Definition: mnt4_g1.hpp:49
libff::Fp_model::squared
Fp_model squared() const
libff::Fp_model< mnt4_q_limbs, mnt4_modulus_q >::zero
static const Fp_model< n, modulus > & zero()
libff::mnt4_G1::batch_to_special_all_non_zeros
static void batch_to_special_all_non_zeros(std::vector< mnt4_G1 > &vec)
Definition: mnt4_g1.cpp:527
libff::mnt4_G1::mixed_add
mnt4_G1 mixed_add(const mnt4_G1 &other) const
Definition: mnt4_g1.cpp:292
libff::Fp_model::is_zero
bool is_zero() const
libff::operator>>
std::istream & operator>>(std::istream &in, alt_bn128_G1 &g)
Definition: alt_bn128_g1.cpp:446
libff::mnt4_G1::operator==
bool operator==(const mnt4_G1 &other) const
Definition: mnt4_g1.cpp:97
libff::mnt4_G1
Definition: mnt4_g1.hpp:26
libff::Fp_model::inverse
Fp_model inverse() const
libff::mnt4_G1::random_element
static mnt4_G1 random_element()
Definition: mnt4_g1.cpp:431
libff::mnt4_G1::Z
mnt4_Fq Z
Definition: mnt4_g1.hpp:49
libff::mnt4_G1::read_uncompressed
static void read_uncompressed(std::istream &, mnt4_G1 &)
Definition: mnt4_g1.cpp:455
libff::mnt4_G1::is_well_formed
bool is_well_formed() const
Definition: mnt4_g1.cpp:402
libff::mnt4_G1::G1_one
static mnt4_G1 G1_one
Definition: mnt4_g1.hpp:36
libff::mnt4_G1::read_compressed
static void read_compressed(std::istream &, mnt4_G1 &)
Definition: mnt4_g1.cpp:472
libff::Fp_model::sqrt
Fp_model sqrt() const
HAS TO BE A SQUARE (else does not terminate)
libff::Fp_model< mnt4_q_limbs, mnt4_modulus_q >::one
static const Fp_model< n, modulus > & one()
libff::mnt4_Fq
Fp_model< mnt4_q_limbs, mnt4_modulus_q > mnt4_Fq
Definition: mnt4_init.hpp:37
OUTPUT_SEPARATOR
#define OUTPUT_SEPARATOR
Definition: serialization.hpp:69
libff::mnt4_G1::one
static const mnt4_G1 & one()
Definition: mnt4_g1.cpp:429
libff::mnt4_G1::mnt4_G1
mnt4_G1()
Definition: mnt4_g1.cpp:32
libff::mnt4_G1::coeff_a
static mnt4_Fq coeff_a
Definition: mnt4_g1.hpp:37
libff::mnt4_G1::fixed_base_exp_window_table
static std::vector< size_t > fixed_base_exp_window_table
Definition: mnt4_g1.hpp:34
libff::mnt4_G1::print
void print() const
Definition: mnt4_g1.cpp:39
libff::consume_OUTPUT_SEPARATOR
void consume_OUTPUT_SEPARATOR(std::istream &in)
libff::mnt4_G1::is_special
bool is_special() const
Definition: mnt4_g1.cpp:87
libff::Fp_model< mnt4_q_limbs, mnt4_modulus_q >::num_limbs
static const mp_size_t num_limbs
Definition: fp.hpp:47
libff::mnt4_G1::dbl
mnt4_G1 dbl() const
Definition: mnt4_g1.cpp:353
libff::mnt4_G1::is_zero
bool is_zero() const
Definition: mnt4_g1.cpp:92
libff::mnt4_G1::print_coordinates
void print_coordinates() const
Definition: mnt4_g1.cpp:55
libff::Fp_model::as_bigint
bigint< n > as_bigint() const
libff::Fp_model< mnt4_q_limbs, mnt4_modulus_q >
libff::mnt4_G1::coeff_b
static mnt4_Fq coeff_b
Definition: mnt4_g1.hpp:38
libff::mnt4_G1::wnaf_window_table
static std::vector< size_t > wnaf_window_table
Definition: mnt4_g1.hpp:33
libff::operator<<
std::ostream & operator<<(std::ostream &out, const alt_bn128_G1 &g)
Definition: alt_bn128_g1.cpp:436
libff::mnt4_G1::operator!=
bool operator!=(const mnt4_G1 &other) const
Definition: mnt4_g1.cpp:122
libff::mnt4_G1::operator+
mnt4_G1 operator+(const mnt4_G1 &other) const
Definition: mnt4_g1.cpp:127
libff::mnt4_G1::operator-
mnt4_G1 operator-() const
Definition: mnt4_g1.cpp:227
libff::mnt4_G1::h
static bigint< h_limbs > h
Definition: mnt4_g1.hpp:47
libff::mnt4_G1::to_affine_coordinates
void to_affine_coordinates()
Definition: mnt4_g1.cpp:71
libff::mnt4_G1::write_compressed
void write_compressed(std::ostream &) const
Definition: mnt4_g1.cpp:445
libff::mnt4_G1::zero
static const mnt4_G1 & zero()
Definition: mnt4_g1.cpp:427
libff::mnt4_G1::X
mnt4_Fq X
Definition: mnt4_g1.hpp:49
libff::mnt4_G1::add
mnt4_G1 add(const mnt4_G1 &other) const
Definition: mnt4_g1.cpp:237
libff::mnt4_G1::to_special
void to_special()
Definition: mnt4_g1.cpp:85
mnt4_g1.hpp
libff::mnt4_G1::write_uncompressed
void write_uncompressed(std::ostream &) const
Definition: mnt4_g1.cpp:436
libff::mnt4_G1::G1_zero
static mnt4_G1 G1_zero
Definition: mnt4_g1.hpp:35
libff::mnt4_G1::is_in_safe_subgroup
bool is_in_safe_subgroup() const
Definition: mnt4_g1.cpp:425
libff::mnt4_G1::mul_by_cofactor
mnt4_G1 mul_by_cofactor() const
Definition: mnt4_g1.cpp:396