detail/element/fp12_2over3over2.hpp
Go to the documentation of this file.
1 //---------------------------------------------------------------------------//
2 // Copyright (c) 2020-2021 Mikhail Komarov <nemo@nil.foundation>
3 // Copyright (c) 2020-2021 Nikita Kaskov <nbering@nil.foundation>
4 //
5 // MIT License
6 //
7 // Permission is hereby granted, free of charge, to any person obtaining a copy
8 // of this software and associated documentation files (the "Software"), to deal
9 // in the Software without restriction, including without limitation the rights
10 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 // copies of the Software, and to permit persons to whom the Software is
12 // furnished to do so, subject to the following conditions:
13 //
14 // The above copyright notice and this permission notice shall be included in all
15 // copies or substantial portions of the Software.
16 //
17 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
20 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
23 // SOFTWARE.
24 //---------------------------------------------------------------------------//
25 
26 #ifndef CRYPTO3_ALGEBRA_FIELDS_ELEMENT_FP12_2OVER3OVER2_HPP
27 #define CRYPTO3_ALGEBRA_FIELDS_ELEMENT_FP12_2OVER3OVER2_HPP
28 
31 
32 #include <nil/crypto3/multiprecision/number.hpp>
33 #include <nil/crypto3/multiprecision/cpp_int.hpp>
34 
35 namespace nil {
36  namespace crypto3 {
37  namespace algebra {
38  namespace fields {
39  namespace detail {
40 
41  template<typename FieldParams>
43  typedef FieldParams policy_type;
44 
45  public:
46  typedef typename policy_type::non_residue_type non_residue_type;
47  constexpr static const non_residue_type non_residue = policy_type::non_residue;
48 
49  typedef typename policy_type::underlying_type underlying_type;
50 
51  using data_type = std::array<underlying_type, 2>;
52 
54 
56  data = data_type({underlying_type::zero(), underlying_type::zero()});
57  }
58 
60  data = data_type({in_data0, in_data1});
61  }
62 
64  data = data_type({in_data[0], in_data[1]});
65  };
66 
68 
69  inline static element_fp12_2over3over2 zero() {
70  return element_fp12_2over3over2(underlying_type::zero(), underlying_type::zero());
71  }
72 
73  inline static element_fp12_2over3over2 one() {
74  return element_fp12_2over3over2(underlying_type::one(), underlying_type::zero());
75  }
76 
77  bool operator==(const element_fp12_2over3over2 &B) const {
78  return (data[0] == B.data[0]) && (data[1] == B.data[1]);
79  }
80 
81  bool operator!=(const element_fp12_2over3over2 &B) const {
82  return (data[0] != B.data[0]) || (data[1] != B.data[1]);
83  }
84 
86  data[0] = B.data[0];
87  data[1] = B.data[1];
88 
89  return *this;
90  }
91 
93  return element_fp12_2over3over2(data[0] + B.data[0], data[1] + B.data[1]);
94  }
95 
98  }
99 
101  return element_fp12_2over3over2(data[0] - B.data[0], data[1] - B.data[1]);
102  }
103 
105  data[0] -= B.data[0];
106  data[1] -= B.data[1];
107 
108  return *this;
109  }
110 
112  data[0] += B.data[0];
113  data[1] += B.data[1];
114 
115  return *this;
116  }
117 
119  return zero() - *this;
120  }
121 
123  const underlying_type A0B0 = data[0] * B.data[0], A1B1 = data[1] * B.data[1];
124 
125  return element_fp12_2over3over2(A0B0 + mul_by_non_residue(A1B1),
126  (data[0] + data[1]) * (B.data[0] + B.data[1]) - A0B0 -
127  A1B1);
128  }
129 
131 
132  // compute squared root with Tonelli--Shanks
133  }
134 
136 
137  return (*this) * (*this); // maybe can be done more effective
138  }
139 
140  template<typename PowerType>
141  element_fp12_2over3over2 pow(const PowerType &pwr) const {
142  return element_fp12_2over3over2(power(*this, pwr));
143  }
144 
146 
147  /* From "High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig
148  * Curves"; Algorithm 8 */
149 
150  const underlying_type &A0 = data[0], &A1 = data[1];
151 
152  const underlying_type t0 = A0.squared();
153  const underlying_type t1 = A1.squared();
154  const underlying_type t2 = t0 - mul_by_non_residue(t1);
155  const underlying_type t3 = t2.inversed();
156  const underlying_type c0 = A0 * t3;
157  const underlying_type c1 = -(A1 * t3);
158 
159  return element_fp12_2over3over2(c0, c1);
160  }
161 
162  template<typename PowerType>
163  element_fp12_2over3over2 Frobenius_map(const PowerType &pwr) const {
164  // return element_fp12_2over3over2(data[0].Frobenius_map(pwr),
165  // policy_type::Frobenius_coeffs_c1[pwr % 12] *
166  // data[1].Frobenius_map(pwr)});
168  typename policy_type::non_residue_type(
169  policy_type::Frobenius_coeffs_c1[(pwr % 12) * 2],
170  policy_type::Frobenius_coeffs_c1[(pwr % 12) * 2 + 1]) *
171  data[1].Frobenius_map(pwr));
172  }
173 
175  return element_fp12_2over3over2(data[0], -data[1]);
176  }
177 
179  // naive implementation
180  // return this->squared();
181 
182  typename underlying_type::underlying_type z0 = data[0].data[0];
183  typename underlying_type::underlying_type z4 = data[0].data[1];
184  typename underlying_type::underlying_type z3 = data[0].data[2];
185 
186  typename underlying_type::underlying_type z2 = data[1].data[0];
187  typename underlying_type::underlying_type z1 = data[1].data[1];
188  typename underlying_type::underlying_type z5 = data[1].data[2];
189 
190  typename underlying_type::underlying_type t0, t1, t2, t3, t4, t5, tmp;
191 
192  // t0 + t1*y = (z0 + z1*y)^2 = a^2
193  tmp = z0 * z1;
194  t0 = (z0 + z1) * (z0 + underlying_type::non_residue * z1) - tmp -
195  underlying_type::non_residue * tmp;
196  t1 = tmp + tmp;
197  // t2 + t3*y = (z2 + z3*y)^2 = b^2
198  tmp = z2 * z3;
199  t2 = (z2 + z3) * (z2 + underlying_type::non_residue * z3) - tmp -
200  underlying_type::non_residue * tmp;
201  t3 = tmp + tmp;
202  // t4 + t5*y = (z4 + z5*y)^2 = c^2
203  tmp = z4 * z5;
204  t4 = (z4 + z5) * (z4 + underlying_type::non_residue * z5) - tmp -
205  underlying_type::non_residue * tmp;
206  t5 = tmp + tmp;
207 
208  // for A
209 
210  // z0 = 3 * t0 - 2 * z0
211  z0 = t0 - z0;
212  z0 = z0 + z0;
213  z0 = z0 + t0;
214  // z1 = 3 * t1 + 2 * z1
215  z1 = t1 + z1;
216  z1 = z1 + z1;
217  z1 = z1 + t1;
218 
219  // for B
220 
221  // z2 = 3 * (xi * t5) + 2 * z2
222  tmp = underlying_type::non_residue * t5;
223  z2 = tmp + z2;
224  z2 = z2 + z2;
225  z2 = z2 + tmp;
226 
227  // z3 = 3 * t4 - 2 * z3
228  z3 = t4 - z3;
229  z3 = z3 + z3;
230  z3 = z3 + t4;
231 
232  // for C
233 
234  // z4 = 3 * t2 - 2 * z4
235  z4 = t2 - z4;
236  z4 = z4 + z4;
237  z4 = z4 + t2;
238 
239  // z5 = 3 * t3 + 2 * z5
240  z5 = t3 + z5;
241  z5 = z5 + z5;
242  z5 = z5 + t3;
243 
244  return element_fp12_2over3over2(underlying_type(z0, z4, z3), underlying_type(z2, z1, z5));
245  }
246 
247  template<typename PowerType>
248  element_fp12_2over3over2 cyclotomic_exp(const PowerType &exponent) const {
250 
251  if (exponent == 0)
252  return res;
253 
254  bool found_one = false;
255  for (long i = nil::crypto3::multiprecision::msb(exponent); i >= 0; --i) {
256  if (found_one) {
257  res = res.cyclotomic_squared();
258  }
259 
260  if (nil::crypto3::multiprecision::bit_test(exponent, i)) {
261  found_one = true;
262  res = res * (*this);
263  }
264  }
265 
266  return res;
267  // return *this;
268  }
269 
271  mul_by_045(const typename underlying_type::underlying_type &ell_0,
272  const typename underlying_type::underlying_type &ell_VW,
273  const typename underlying_type::underlying_type &ell_VV) const {
274 
275  // element_fp12_2over3over2 a(
276  // underlying_type(ell_VW, underlying_type::underlying_type::zero(),
277  // underlying_type::underlying_type::zero()),
278  // underlying_type(underlying_type::underlying_type::zero(), ell_0, ell_VV));
279  //
280  // return (*this) * a;
281 
282  typename underlying_type::underlying_type z0 = this->data[0].data[0];
283  typename underlying_type::underlying_type z1 = this->data[0].data[1];
284  typename underlying_type::underlying_type z2 = this->data[0].data[2];
285  typename underlying_type::underlying_type z3 = this->data[1].data[0];
286  typename underlying_type::underlying_type z4 = this->data[1].data[1];
287  typename underlying_type::underlying_type z5 = this->data[1].data[2];
288 
289  typename underlying_type::underlying_type x0 = ell_VW;
290  typename underlying_type::underlying_type x4 = ell_0;
291  typename underlying_type::underlying_type x5 = ell_VV;
292 
293  typename underlying_type::underlying_type t0, t1, t2, t3, t4, t5;
294  typename underlying_type::underlying_type tmp1, tmp2;
295 
296  // TODO: non_residue should be used as static
297  tmp1 = element_fp12_2over3over2().non_residue * x4;
298  tmp2 = element_fp12_2over3over2().non_residue * x5;
299 
300  t0 = x0 * z0 + tmp1 * z4 + tmp2 * z3;
301  t1 = x0 * z1 + tmp1 * z5 + tmp2 * z4;
302  t2 = x0 * z2 + x4 * z3 + tmp2 * z5;
303  t3 = x0 * z3 + tmp1 * z2 + tmp2 * z1;
304  t4 = x0 * z4 + x4 * z0 + tmp2 * z2;
305  t5 = x0 * z5 + x4 * z1 + x5 * z0;
306 
307  return element_fp12_2over3over2(underlying_type(t0, t1, t2), underlying_type(t3, t4, t5));
308  }
309 
311  mul_by_024(const typename underlying_type::underlying_type &ell_0,
312  const typename underlying_type::underlying_type &ell_VW,
313  const typename underlying_type::underlying_type &ell_VV) const {
315  underlying_type(ell_0, underlying_type::underlying_type::zero(), ell_VV),
316  underlying_type(underlying_type::underlying_type::zero(), ell_VW,
317  underlying_type::underlying_type::zero()));
318 
319  return (*this) * a;
320  }
321 
322  /*element_fp12_2over3over2 sqru() {
323  element_fp2<FieldParams> &z0(a_.a_);
324  element_fp2<FieldParams> &z4(a_.b_);
325  element_fp2<FieldParams> &z3(a_.c_);
326  element_fp2<FieldParams> &z2(b_.a_);
327  element_fp2<FieldParams> &z1(b_.b_);
328  element_fp2<FieldParams> &z5(b_.c_);
329  element_fp4<FieldParams> t0t1;
330  element_fp2<FieldParams> t0 = t0t1.data[0], t1 = t0t1.data[1];
331 
332  t0t1 = sq_Fp4UseDbl({z0, z1}); // a^2 = t0 + t1*y
333  // For A
334  z0 = t0 - z0;
335  z0 += z0;
336  z0 += t0;
337 
338  z1 = (t1 + z1).doubled() + t1;
339 
340  // t0 and t1 are unnecessary from here.
341  element_fp2 t2, t3;
342  t0t1 = sq_Fp4UseDbl({z2, z3}); // b^2 = t0 + t1*y
343  t0t1 = sq_Fp4UseDbl({z4, z5}); // c^2 = t2 + t3*y
344  // For C
345  z4 = (t0 - z4).doubled() + t0;
346 
347  z5 = (t1 + z5).doubled() + t1;
348 
349  // For B
350  t0 = t3.mul_xi();
351 
352  z2 = (t0 + z2).doubled() + t0;
353 
354  z3 = (t2 - z3).doubled() + t2;
355  }*/
356 
357  /*inline static*/ underlying_type mul_by_non_residue(const underlying_type &A) const {
358  return underlying_type(non_residue * A.data[2], A.data[0], A.data[1]);
359  }
360  };
361 
362  template<typename FieldParams>
363  element_fp12_2over3over2<FieldParams>
364  operator*(const typename FieldParams::underlying_type::underlying_type::underlying_type &lhs,
366 
367  return element_fp12_2over3over2<FieldParams>(lhs * rhs.data[0], lhs * rhs.data[1]);
368  }
369 
370  template<typename FieldParams>
371  element_fp12_2over3over2<FieldParams>
373  const typename FieldParams::underlying_type::underlying_type::underlying_type &rhs) {
374 
375  return rhs * lhs;
376  }
377 
378  template<typename FieldParams>
379  element_fp12_2over3over2<FieldParams>
380  operator*(const typename FieldParams::underlying_type::underlying_type &lhs,
382 
383  return element_fp12_2over3over2<FieldParams>(lhs * rhs.data[0], lhs * rhs.data[1]);
384  }
385 
386  template<typename FieldParams>
387  element_fp12_2over3over2<FieldParams>
389  const typename FieldParams::underlying_type::underlying_type &rhs) {
390 
391  return rhs * lhs;
392  }
393 
394  template<typename FieldParams>
395  element_fp12_2over3over2<FieldParams> operator*(const typename FieldParams::underlying_type &lhs,
397 
398  return element_fp12_2over3over2<FieldParams>(lhs * rhs.data[0], lhs * rhs.data[1]);
399  }
400 
401  template<typename FieldParams>
403  const typename FieldParams::underlying_type &rhs) {
404 
405  return rhs * lhs;
406  }
407 
408  /*
409  (a + bw) -> (a - bw) gammar
410  */
411  /*template <typename FieldParams>
412  element_fp12_2over3over2<FieldParams> Frobenius(element_fp12_2over3over2<FieldParams> A) {
413  // this assumes (q-1)/6 is odd
414 
415  z.a_.a_.a_ = A.a_.a_.a_;
416  z.a_.b_.a_ = A.a_.b_.a_;
417  z.a_.c_.a_ = A.a_.c_.a_;
418  z.b_.a_.a_ = A.b_.a_.a_;
419  z.b_.b_.a_ = A.b_.b_.a_;
420  z.b_.c_.a_ = A.b_.c_.a_;
421 
422  z.a_.a_.b_ = -A.a_.a_.b_;
423  z.a_.b_.b_ = -A.a_.b_.b_;
424  z.a_.c_.b_ = -A.a_.c_.b_;
425  z.b_.a_.b_ = -A.b_.a_.b_;
426  z.b_.b_.b_ = -A.b_.b_.b_;
427  z.b_.c_.b_ = -A.b_.c_.b_;
428 
429  z.a_.b_ *= Param::gammar[1];
430  z.a_.c_ *= Param::gammar[3];
431 
432  z.b_.a_ *= Param::gammar[0];
433  z.b_.b_ *= Param::gammar[2];
434  z.b_.c_ *= Param::gammar[4];
435  }*/
436 
437  /*
438  gammar = c + dw
439  a + bw -> t = (a - bw)(c + dw)
440  ~t = (a + bw)(c - dw)
441  ~t * (c + dw) = (a + bw) * ((c + dw)(c - dw))
442  gammar2 = (c + dw)(c - dw) in Fp6
443  */
444  /*template <typename FieldParams>
445  element_fp12_2over3over2<FieldParams> Frobenius2(element_fp12_2over3over2<FieldParams> A) {
446 
447  z.a_.a_ = A.a_.a_;
448 
449  z.a_.a_ = A.a_.a_;
450  z.a_.b_ = A.a_.b_.mul_Fp_0(Param::gammar2[1].a_);
451  z.a_.c_ = A.a_.c_.mul_Fp_0(Param::gammar2[3].a_);
452  z.b_.a_ = A.b_.a_.mul_Fp_0(Param::gammar2[0].a_);
453  z.b_.b_ = A.b_.b_.mul_Fp_0(Param::gammar2[2].a_);
454  z.b_.c_ = A.b_.c_.mul_Fp_0(Param::gammar2[4].a_);
455  }
456 
457  template <typename FieldParams>
458  element_fp12_2over3over2<FieldParams> Frobenius3(element_fp12_2over3over2<FieldParams> A) {
459  z.a_.a_.a_ = A.a_.a_.a_;
460  z.a_.b_.a_ = A.a_.b_.a_;
461  z.a_.c_.a_ = A.a_.c_.a_;
462  z.b_.a_.a_ = A.b_.a_.a_;
463  z.b_.b_.a_ = A.b_.b_.a_;
464  z.b_.c_.a_ = A.b_.c_.a_;
465 
466  z.a_.a_.b_ = -A.a_.a_.b_;
467  z.a_.b_.b_ = -A.a_.b_.b_;
468  z.a_.c_.b_ = -A.a_.c_.b_;
469  z.b_.a_.b_ = -A.b_.a_.b_;
470  z.b_.b_.b_ = -A.b_.b_.b_;
471  z.b_.c_.b_ = -A.b_.c_.b_;
472 
473  z.a_.b_ *= Param::gammar3[1];
474  z.a_.c_ *= Param::gammar3[3];
475 
476  z.b_.a_ *= Param::gammar3[0];
477  z.b_.b_ *= Param::gammar3[2];
478  z.b_.c_ *= Param::gammar3[4];
479  }*/
480 
481  template<typename FieldParams>
484 
485  } // namespace detail
486  } // namespace fields
487  } // namespace algebra
488  } // namespace crypto3
489 } // namespace nil
490 
491 #endif // CRYPTO3_ALGEBRA_FIELDS_ELEMENT_FP12_2OVER3OVER2_HPP
Definition: detail/element/fp12_2over3over2.hpp:42
element_fp12_2over3over2 operator-(const element_fp12_2over3over2 &B) const
Definition: detail/element/fp12_2over3over2.hpp:100
element_fp12_2over3over2 Frobenius_map(const PowerType &pwr) const
Definition: detail/element/fp12_2over3over2.hpp:163
data_type data
Definition: detail/element/fp12_2over3over2.hpp:53
element_fp12_2over3over2 operator+(const element_fp12_2over3over2 &B) const
Definition: detail/element/fp12_2over3over2.hpp:92
element_fp12_2over3over2(const data_type &in_data)
Definition: detail/element/fp12_2over3over2.hpp:63
element_fp12_2over3over2()
Definition: detail/element/fp12_2over3over2.hpp:55
std::array< underlying_type, 2 > data_type
Definition: detail/element/fp12_2over3over2.hpp:51
element_fp12_2over3over2 mul_by_024(const typename underlying_type::underlying_type &ell_0, const typename underlying_type::underlying_type &ell_VW, const typename underlying_type::underlying_type &ell_VV) const
Definition: detail/element/fp12_2over3over2.hpp:311
element_fp12_2over3over2 & operator+=(const element_fp12_2over3over2 &B)
Definition: detail/element/fp12_2over3over2.hpp:111
element_fp12_2over3over2 mul_by_045(const typename underlying_type::underlying_type &ell_0, const typename underlying_type::underlying_type &ell_VW, const typename underlying_type::underlying_type &ell_VV) const
Definition: detail/element/fp12_2over3over2.hpp:271
element_fp12_2over3over2 inversed() const
Definition: detail/element/fp12_2over3over2.hpp:145
underlying_type mul_by_non_residue(const underlying_type &A) const
Definition: detail/element/fp12_2over3over2.hpp:357
element_fp12_2over3over2 sqrt() const
Definition: detail/element/fp12_2over3over2.hpp:130
element_fp12_2over3over2 doubled() const
Definition: detail/element/fp12_2over3over2.hpp:96
element_fp12_2over3over2 cyclotomic_squared() const
Definition: detail/element/fp12_2over3over2.hpp:178
constexpr static const non_residue_type non_residue
Definition: detail/element/fp12_2over3over2.hpp:47
bool operator==(const element_fp12_2over3over2 &B) const
Definition: detail/element/fp12_2over3over2.hpp:77
bool operator!=(const element_fp12_2over3over2 &B) const
Definition: detail/element/fp12_2over3over2.hpp:81
element_fp12_2over3over2 cyclotomic_exp(const PowerType &exponent) const
Definition: detail/element/fp12_2over3over2.hpp:248
element_fp12_2over3over2 & operator=(const element_fp12_2over3over2 &B)
Definition: detail/element/fp12_2over3over2.hpp:85
policy_type::underlying_type underlying_type
Definition: detail/element/fp12_2over3over2.hpp:49
element_fp12_2over3over2 squared() const
Definition: detail/element/fp12_2over3over2.hpp:135
element_fp12_2over3over2(underlying_type in_data0, underlying_type in_data1)
Definition: detail/element/fp12_2over3over2.hpp:59
policy_type::non_residue_type non_residue_type
Definition: detail/element/fp12_2over3over2.hpp:46
element_fp12_2over3over2(const element_fp12_2over3over2 &B)
Definition: detail/element/fp12_2over3over2.hpp:67
element_fp12_2over3over2 operator-() const
Definition: detail/element/fp12_2over3over2.hpp:118
element_fp12_2over3over2 & operator-=(const element_fp12_2over3over2 &B)
Definition: detail/element/fp12_2over3over2.hpp:104
static element_fp12_2over3over2 one()
Definition: detail/element/fp12_2over3over2.hpp:73
element_fp12_2over3over2 unitary_inversed() const
Definition: detail/element/fp12_2over3over2.hpp:174
element_fp12_2over3over2 operator*(const element_fp12_2over3over2 &B) const
Definition: detail/element/fp12_2over3over2.hpp:122
static element_fp12_2over3over2 zero()
Definition: detail/element/fp12_2over3over2.hpp:69
element_fp12_2over3over2 pow(const PowerType &pwr) const
Definition: detail/element/fp12_2over3over2.hpp:141
constexpr FieldValueType power(const FieldValueType &base, const NumberType &exponent)
Definition: algebra/include/nil/crypto3/algebra/fields/detail/exponentiation.hpp:41
element_fp12_2over3over2< FieldParams > operator*(const typename FieldParams::underlying_type::underlying_type::underlying_type &lhs, const element_fp12_2over3over2< FieldParams > &rhs)
Definition: detail/element/fp12_2over3over2.hpp:364
Definition: pair.hpp:31