tate_precompute_g1.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_PAIRING_EDWARDS_183_TATE_PRECOMPUTE_G1_HPP
27 #define CRYPTO3_ALGEBRA_PAIRING_EDWARDS_183_TATE_PRECOMPUTE_G1_HPP
28 
29 #include <nil/crypto3/multiprecision/number.hpp>
30 #include <nil/crypto3/multiprecision/cpp_int.hpp>
31 
32 #include <nil/crypto3/algebra/curves/edwards.hpp>
33 #include <nil/crypto3/algebra/pairing/detail/bls12/381/params.hpp>
34 #include <nil/crypto3/algebra/pairing/detail/edwards/183/types.hpp>
35 
36 namespace nil {
37  namespace crypto3 {
38  namespace algebra {
39  namespace pairing {
40 
41  template<std::size_t Version = 183>
42  class edwards_ate_precompute_g1;
43 
44  template<>
45  class edwards_ate_precompute_g1<183> {
46  using curve_type = curves::edwards<183>;
47 
48  using params_type = detail::pairing_params<curve_type>;
49  typedef detail::types_policy<curve_type> policy_type;
50 
51  using base_field_type = typename curve_type::base_field_type;
52  using g1_type = typename curve_type::template g1_type<>;
53  using g1_affine_type = typename curve_type::template g1_type<curves::coordinates::affine>;
54 
55  using g1_field_type_value = typename g1_type::field_type::value_type;
56 
57  struct extended_g1_projective {
58  g1_field_type_value X;
59  g1_field_type_value Y;
60  g1_field_type_value Z;
61  g1_field_type_value T;
62  };
63 
64  static void doubling_step_for_miller_loop(extended_g1_projective &current,
65  typename policy_type::Fq_conic_coefficients &cc) {
66 
67  const g1_field_type_value &X = current.X, &Y = current.Y, &Z = current.Z, &T = current.T;
68  const g1_field_type_value A = X.squared(); // A = X1^2
69  const g1_field_type_value B = Y.squared(); // B = Y1^2
70  const g1_field_type_value C = Z.squared(); // C = Z1^2
71  const g1_field_type_value D = (X + Y).squared(); // D = (X1+Y1)^2
72  const g1_field_type_value E = (Y + Z).squared(); // E = (Y1+Z1)^2
73  const g1_field_type_value F = D - (A + B); // F = D-(A+B)
74  const g1_field_type_value G = E - (B + C); // G = E-(B+C)
75  const g1_field_type_value &H = A; // H = A (a=1)
76  const g1_field_type_value I = H + B; // I = H+B
77  const g1_field_type_value J = C - I; // J = C-I
78  const g1_field_type_value K = J + C; // K = J+C
79 
80  cc.c_ZZ = Y * (T - X); // c_ZZ = 2*Y1*(T1-X1)
81  cc.c_ZZ = cc.c_ZZ + cc.c_ZZ;
82 
83  cc.c_XY = J + J + G; // c_XY = 2*J+G
84  cc.c_XZ = X * T - B; // c_XZ = 2*(X1*T1-B) (a=1)
85  cc.c_XZ = cc.c_XZ + cc.c_XZ;
86 
87  current.X = F * K; // X3 = F*K
88  current.Y = I * (B - H); // Y3 = I*(B-H)
89  current.Z = I * K; // Z3 = I*K
90  current.T = F * (B - H); // T3 = F*(B-H)
91  }
92 
93  static void full_addition_step_for_miller_loop(const extended_g1_projective &base,
94  extended_g1_projective &current,
95  typename policy_type::Fq_conic_coefficients &cc) {
96 
97  const g1_field_type_value &X1 = current.X, &Y1 = current.Y, &Z1 = current.Z, &T1 = current.T;
98  const g1_field_type_value &X2 = base.X, &Y2 = base.Y, &Z2 = base.Z, &T2 = base.T;
99 
100  const g1_field_type_value A = X1 * X2; // A = X1*X2
101  const g1_field_type_value B = Y1 * Y2; // B = Y1*Y2
102  const g1_field_type_value C = Z1 * T2; // C = Z1*T2
103  const g1_field_type_value D = T1 * Z2; // D = T1*Z2
104  const g1_field_type_value E = D + C; // E = D+C
105  const g1_field_type_value F = (X1 - Y1) * (X2 + Y2) + B - A; // F = (X1-Y1)*(X2+Y2)+B-A
106  const g1_field_type_value G = B + A; // G = B + A (a=1)
107  const g1_field_type_value H = D - C; // H = D-C
108  const g1_field_type_value I = T1 * T2; // I = T1*T2
109 
110  cc.c_ZZ = (T1 - X1) * (T2 + X2) - I + A; // c_ZZ = (T1-X1)*(T2+X2)-I+A
111  cc.c_XY = X1 * Z2 - X2 * Z1 + F; // c_XY = X1*Z2-X2*Z1+F
112  cc.c_XZ = (Y1 - T1) * (Y2 + T2) - B + I - H; // c_XZ = (Y1-T1)*(Y2+T2)-B+I-H
113  current.X = E * F; // X3 = E*F
114  current.Y = G * H; // Y3 = G*H
115  current.Z = F * G; // Z3 = F*G
116  current.T = E * H; // T3 = E*H
117  }
118 
119  static void mixed_addition_step_for_miller_loop(const extended_g1_projective &base,
120  extended_g1_projective &current,
121  typename policy_type::Fq_conic_coefficients &cc) {
122 
123  const g1_field_type_value &X1 = current.X, &Y1 = current.Y, &Z1 = current.Z, &T1 = current.T;
124  const g1_field_type_value &X2 = base.X, &Y2 = base.Y, &T2 = base.T;
125 
126  const g1_field_type_value A = X1 * X2; // A = X1*X2
127  const g1_field_type_value B = Y1 * Y2; // B = Y1*Y2
128  const g1_field_type_value C = Z1 * T2; // C = Z1*T2
129  const g1_field_type_value D = T1; // D = T1*Z2
130  const g1_field_type_value E = D + C; // E = D+C
131  const g1_field_type_value F = (X1 - Y1) * (X2 + Y2) + B - A; // F = (X1-Y1)*(X2+Y2)+B-A
132  const g1_field_type_value G = B + A; // G = B + A (a=1)
133  const g1_field_type_value H = D - C; // H = D-C
134  const g1_field_type_value I = T1 * T2; // I = T1*T2
135 
136  cc.c_ZZ = (T1 - X1) * (T2 + X2) - I + A; // c_ZZ = (T1-X1)*(T2+X2)-I+A
137  cc.c_XY = X1 - X2 * Z1 + F; // c_XY = X1*Z2-X2*Z1+F
138  cc.c_XZ = (Y1 - T1) * (Y2 + T2) - B + I - H; // c_XZ = (Y1-T1)*(Y2+T2)-B+I-H
139  current.X = E * F; // X3 = E*F
140  current.Y = G * H; // Y3 = G*H
141  current.Z = F * G; // Z3 = F*G
142  current.T = E * H; // T3 = E*H
143  }
144 
145  public:
146  using g1_precomputed_type = typename policy_type::tate_g1_precomp;
147 
148  static typename policy_type::tate_g1_precomp process(const typename g1_type::value_type &P) {
149 
150  typename policy_type::tate_g1_precomp result;
151 
152  typename g1_affine_type::value_type Pcopy = P.to_affine();
153 
154  extended_g1_projective P_ext;
155  P_ext.X = Pcopy.X;
156  P_ext.Y = Pcopy.Y;
157  P_ext.Z = Pcopy.Z;
158  P_ext.T = Pcopy.X * Pcopy.Y;
159 
160  extended_g1_projective R = P_ext;
161 
162  bool found_one = false;
163  for (long i = params_type::scalar_field_bits; i >= 0; --i) {
164  const bool bit =
165  nil::crypto3::multiprecision::bit_test(params_type::scalar_field_modulus, i);
166  if (!found_one) {
167  /* this skips the MSB itself */
168  found_one |= bit;
169  continue;
170  }
171 
172  /* code below gets executed for all bits (EXCEPT the MSB itself) of
173  params_type::scalar_field_modulus (skipping leading zeros) in MSB to LSB
174  order */
175  policy_type::Fq_conic_coefficients cc;
176 
177  doubling_step_for_miller_loop(R, cc);
178  result.push_back(cc);
179 
180  if (bit) {
181  mixed_addition_step_for_miller_loop(P_ext, R, cc);
182  result.push_back(cc);
183  }
184  }
185 
186  return result;
187  }
188  };
189  } // namespace pairing
190  } // namespace algebra
191  } // namespace crypto3
192 } // namespace nil
193 #endif // CRYPTO3_ALGEBRA_PAIRING_EDWARDS_183_TATE_PRECOMPUTE_G1_HPP
nil::crypto3::algebra::pairing::edwards_ate_precompute_g1< 183 >::process
static policy_type::tate_g1_precomp process(const typename g1_type::value_type &P)
Definition: tate_precompute_g1.hpp:148
nil::crypto3::algebra::pairing::edwards_ate_precompute_g1< 183 >::g1_precomputed_type
typename policy_type::ate_g1_precomputed_type g1_precomputed_type
Definition: edwards/183/ate_precompute_g1.hpp:50
nil
Definition: pair.hpp:31