Clearmatics Libff  0.1
C++ library for Finite Fields and Elliptic Curves
Public Types | Public Member Functions | Static Public Member Functions | Public Attributes | Static Public Attributes | List of all members
libff::edwards_G1 Class Reference

#include <edwards_g1.hpp>

Collaboration diagram for libff::edwards_G1:
Collaboration graph
[legend]

Public Types

typedef edwards_Fq base_field
 
typedef edwards_Fr scalar_field
 

Public Member Functions

 edwards_G1 ()
 
 edwards_G1 (const edwards_Fq &X, const edwards_Fq &Y)
 
void print () const
 
void print_coordinates () const
 
void to_affine_coordinates ()
 
void to_special ()
 
bool is_special () const
 
bool is_zero () const
 
bool operator== (const edwards_G1 &other) const
 
bool operator!= (const edwards_G1 &other) const
 
edwards_G1 operator+ (const edwards_G1 &other) const
 
edwards_G1 operator- () const
 
edwards_G1 operator- (const edwards_G1 &other) const
 
edwards_G1 add (const edwards_G1 &other) const
 
edwards_G1 mixed_add (const edwards_G1 &other) const
 
edwards_G1 dbl () const
 
bool is_well_formed () const
 
void write_uncompressed (std::ostream &) const
 
void write_compressed (std::ostream &) const
 

Static Public Member Functions

static const edwards_G1zero ()
 
static const edwards_G1one ()
 
static edwards_G1 random_element ()
 
static size_t size_in_bits ()
 
static bigint< base_field::num_limbsbase_field_char ()
 
static bigint< scalar_field::num_limbsorder ()
 
static void read_uncompressed (std::istream &, edwards_G1 &)
 
static void read_compressed (std::istream &, edwards_G1 &)
 
static void batch_to_special_all_non_zeros (std::vector< edwards_G1 > &vec)
 

Public Attributes

edwards_Fq X
 
edwards_Fq Y
 
edwards_Fq Z
 

Static Public Attributes

static std::vector< size_t > wnaf_window_table
 
static std::vector< size_t > fixed_base_exp_window_table
 
static edwards_G1 G1_zero
 
static edwards_G1 G1_one
 

Detailed Description

Definition at line 21 of file edwards_g1.hpp.

Member Typedef Documentation

◆ base_field

Definition at line 38 of file edwards_g1.hpp.

◆ scalar_field

Definition at line 42 of file edwards_g1.hpp.

Constructor & Destructor Documentation

◆ edwards_G1() [1/2]

libff::edwards_G1::edwards_G1 ( )

Definition at line 23 of file edwards_g1.cpp.

24 {
25  this->X = G1_zero.X;
26  this->Y = G1_zero.Y;
27  this->Z = G1_zero.Z;
28 }
Here is the caller graph for this function:

◆ edwards_G1() [2/2]

libff::edwards_G1::edwards_G1 ( const edwards_Fq X,
const edwards_Fq Y 
)
inline

Definition at line 44 of file edwards_g1.hpp.

45  : X(Y), Y(X), Z(X * Y){};

Member Function Documentation

◆ add()

edwards_G1 libff::edwards_G1::add ( const edwards_G1 other) const

Definition at line 165 of file edwards_g1.cpp.

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 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ base_field_char()

static bigint<base_field::num_limbs> libff::edwards_G1::base_field_char ( )
inlinestatic

Definition at line 74 of file edwards_g1.hpp.

75  {
76  return base_field::field_char();
77  }
Here is the call graph for this function:

◆ batch_to_special_all_non_zeros()

void libff::edwards_G1::batch_to_special_all_non_zeros ( std::vector< edwards_G1 > &  vec)
static

Definition at line 388 of file edwards_g1.cpp.

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 }
Here is the call graph for this function:

◆ dbl()

edwards_G1 libff::edwards_G1::dbl ( ) const

Definition at line 242 of file edwards_g1.cpp.

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 }
Here is the call graph for this function:

◆ is_special()

bool libff::edwards_G1::is_special ( ) const

Definition at line 101 of file edwards_g1.cpp.

102 {
103  return (this->is_zero() || this->Z == edwards_Fq::one());
104 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ is_well_formed()

bool libff::edwards_G1::is_well_formed ( ) const

Definition at line 275 of file edwards_g1.cpp.

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 }
Here is the call graph for this function:

◆ is_zero()

bool libff::edwards_G1::is_zero ( ) const

Definition at line 106 of file edwards_g1.cpp.

107 {
108  return (this->Y.is_zero() && this->Z.is_zero());
109 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ mixed_add()

edwards_G1 libff::edwards_G1::mixed_add ( const edwards_G1 other) const

Definition at line 197 of file edwards_g1.cpp.

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 }
Here is the call graph for this function:

◆ one()

const edwards_G1 & libff::edwards_G1::one ( )
static

Definition at line 299 of file edwards_g1.cpp.

299 { return G1_one; }
Here is the caller graph for this function:

◆ operator!=()

bool libff::edwards_G1::operator!= ( const edwards_G1 other) const

Definition at line 136 of file edwards_g1.cpp.

137 {
138  return !(operator==(other));
139 }
Here is the call graph for this function:

◆ operator+()

edwards_G1 libff::edwards_G1::operator+ ( const edwards_G1 other) const

Definition at line 141 of file edwards_g1.cpp.

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 }
Here is the call graph for this function:

◆ operator-() [1/2]

edwards_G1 libff::edwards_G1::operator- ( ) const

Definition at line 155 of file edwards_g1.cpp.

156 {
157  return edwards_G1(-(this->X), this->Y, this->Z);
158 }
Here is the call graph for this function:

◆ operator-() [2/2]

edwards_G1 libff::edwards_G1::operator- ( const edwards_G1 other) const

Definition at line 160 of file edwards_g1.cpp.

161 {
162  return (*this) + (-other);
163 }

◆ operator==()

bool libff::edwards_G1::operator== ( const edwards_G1 other) const

Definition at line 111 of file edwards_g1.cpp.

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 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ order()

static bigint<scalar_field::num_limbs> libff::edwards_G1::order ( )
inlinestatic

Definition at line 78 of file edwards_g1.hpp.

79  {
80  return scalar_field::field_char();
81  }
Here is the call graph for this function:

◆ print()

void libff::edwards_G1::print ( ) const

Definition at line 30 of file edwards_g1.cpp.

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 }
Here is the call graph for this function:

◆ print_coordinates()

void libff::edwards_G1::print_coordinates ( ) const

Definition at line 46 of file edwards_g1.cpp.

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 }
Here is the call graph for this function:

◆ random_element()

edwards_G1 libff::edwards_G1::random_element ( )
static

Definition at line 301 of file edwards_g1.cpp.

302 {
303  return edwards_Fr::random_element().as_bigint() * G1_one;
304 }
Here is the call graph for this function:

◆ read_compressed()

void libff::edwards_G1::read_compressed ( std::istream &  in,
edwards_G1 g 
)
static

Definition at line 337 of file edwards_g1.cpp.

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 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ read_uncompressed()

void libff::edwards_G1::read_uncompressed ( std::istream &  in,
edwards_G1 g 
)
static

Definition at line 320 of file edwards_g1.cpp.

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 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ size_in_bits()

static size_t libff::edwards_G1::size_in_bits ( )
inlinestatic

Definition at line 73 of file edwards_g1.hpp.

73 { return edwards_Fq::size_in_bits() + 1; }
Here is the call graph for this function:

◆ to_affine_coordinates()

void libff::edwards_G1::to_affine_coordinates ( )

Definition at line 62 of file edwards_g1.cpp.

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 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ to_special()

void libff::edwards_G1::to_special ( )

Definition at line 81 of file edwards_g1.cpp.

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 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ write_compressed()

void libff::edwards_G1::write_compressed ( std::ostream &  out) const

Definition at line 313 of file edwards_g1.cpp.

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 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ write_uncompressed()

void libff::edwards_G1::write_uncompressed ( std::ostream &  out) const

Definition at line 306 of file edwards_g1.cpp.

307 {
308  edwards_G1 copy(*this);
309  copy.to_affine_coordinates();
310  out << copy.X << OUTPUT_SEPARATOR << copy.Y;
311 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ zero()

const edwards_G1 & libff::edwards_G1::zero ( )
static

Definition at line 297 of file edwards_g1.cpp.

297 { return G1_zero; }

Member Data Documentation

◆ fixed_base_exp_window_table

std::vector< size_t > libff::edwards_G1::fixed_base_exp_window_table
static

Definition at line 29 of file edwards_g1.hpp.

◆ G1_one

edwards_G1 libff::edwards_G1::G1_one
static

Definition at line 31 of file edwards_g1.hpp.

◆ G1_zero

edwards_G1 libff::edwards_G1::G1_zero
static

Definition at line 30 of file edwards_g1.hpp.

◆ wnaf_window_table

std::vector< size_t > libff::edwards_G1::wnaf_window_table
static

Definition at line 28 of file edwards_g1.hpp.

◆ X

edwards_Fq libff::edwards_G1::X

Definition at line 33 of file edwards_g1.hpp.

◆ Y

edwards_Fq libff::edwards_G1::Y

Definition at line 33 of file edwards_g1.hpp.

◆ Z

edwards_Fq libff::edwards_G1::Z

Definition at line 33 of file edwards_g1.hpp.


The documentation for this class was generated from the following files:
libff::edwards_G1::G1_one
static edwards_G1 G1_one
Definition: edwards_g1.hpp:31
libff::Fp_model::random_element
static Fp_model< n, modulus > random_element()
returns random element of Fp_model
libff::Fp_model::squared
Fp_model squared() const
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::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::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::Fp_model< edwards_q_limbs, edwards_modulus_q >::size_in_bits
static size_t size_in_bits()
Definition: fp.hpp:134
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::edwards_G1
edwards_G1()
Definition: edwards_g1.cpp:23
libff::edwards_coeff_d
edwards_Fq edwards_coeff_d
Definition: edwards_init.cpp:19
libff::Fp_model< edwards_q_limbs, edwards_modulus_q >::field_char
static const bigint< n > & field_char()
Definition: fp.hpp:136
libff::Fp_model::as_bigint
bigint< n > as_bigint() const
libff::edwards_Fq
Fp_model< edwards_q_limbs, edwards_modulus_q > edwards_Fq
Definition: edwards_init.hpp:30
libff::edwards_G1::Y
edwards_Fq Y
Definition: edwards_g1.hpp:33
libff::edwards_G1::X
edwards_Fq X
Definition: edwards_g1.hpp:33
libff::edwards_G1::Z
edwards_Fq Z
Definition: edwards_g1.hpp:33