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