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