src/snark/libsnark/algebra/fields/fp12_2over3over2.tcc

   1 /** @file
   2  *****************************************************************************
   3  Implementation of arithmetic in the finite field F[((p^2)^3)^2].
   4  *****************************************************************************
   5  * @author     This file is part of libsnark, developed by SCIPR Lab
   6  *             and contributors (see AUTHORS).
   7  * @copyright  MIT license (see LICENSE file)
   8  *****************************************************************************/
   9
  10 #ifndef FP12_2OVER3OVER2_TCC_
  11 #define FP12_2OVER3OVER2_TCC_
  12
  13 namespace libsnark {
  14
  15 template<mp_size_t n, const bigint<n>& modulus>
  16 Fp6_3over2_model<n, modulus> Fp12_2over3over2_model<n,modulus>::mul_by_non_residue(const Fp6_3over2_model<n, modulus> &elt)
  17 {
  18     return Fp6_3over2_model<n, modulus>(non_residue * elt.c2, elt.c0, elt.c1);
  19 }
  20
  21 template<mp_size_t n, const bigint<n>& modulus>
  22 Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::zero()
  23 {
  24     return Fp12_2over3over2_model<n, modulus>(my_Fp6::zero(), my_Fp6::zero());
  25 }
  26
  27 template<mp_size_t n, const bigint<n>& modulus>
  28 Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::one()
  29 {
  30     return Fp12_2over3over2_model<n, modulus>(my_Fp6::one(), my_Fp6::zero());
  31 }
  32
  33 template<mp_size_t n, const bigint<n>& modulus>
  34 Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::random_element()
  35 {
  36     Fp12_2over3over2_model<n, modulus> r;
  37     r.c0 = my_Fp6::random_element();
  38     r.c1 = my_Fp6::random_element();
  39
  40     return r;
  41 }
  42
  43 template<mp_size_t n, const bigint<n>& modulus>
  44 bool Fp12_2over3over2_model<n,modulus>::operator==(const Fp12_2over3over2_model<n,modulus> &other) const
  45 {
  46     return (this->c0 == other.c0 && this->c1 == other.c1);
  47 }
  48
  49 template<mp_size_t n, const bigint<n>& modulus>
  50 bool Fp12_2over3over2_model<n,modulus>::operator!=(const Fp12_2over3over2_model<n,modulus> &other) const
  51 {
  52     return !(operator==(other));
  53 }
  54
  55 template<mp_size_t n, const bigint<n>& modulus>
  56 Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::operator+(const Fp12_2over3over2_model<n,modulus> &other) const
  57 {
  58     return Fp12_2over3over2_model<n,modulus>(this->c0 + other.c0,
  59                                              this->c1 + other.c1);
  60 }
  61
  62 template<mp_size_t n, const bigint<n>& modulus>
  63 Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::operator-(const Fp12_2over3over2_model<n,modulus> &other) const
  64 {
  65     return Fp12_2over3over2_model<n,modulus>(this->c0 - other.c0,
  66                                              this->c1 - other.c1);
  67 }
  68
  69 template<mp_size_t n, const bigint<n>& modulus>
  70 Fp12_2over3over2_model<n, modulus> operator*(const Fp_model<n, modulus> &lhs, const Fp12_2over3over2_model<n, modulus> &rhs)
  71 {
  72     return Fp12_2over3over2_model<n,modulus>(lhs*rhs.c0,
  73                                              lhs*rhs.c1);
  74 }
  75
  76 template<mp_size_t n, const bigint<n>& modulus>
  77 Fp12_2over3over2_model<n, modulus> operator*(const Fp2_model<n, modulus> &lhs, const Fp12_2over3over2_model<n, modulus> &rhs)
  78 {
  79     return Fp12_2over3over2_model<n,modulus>(lhs*rhs.c0,
  80                                              lhs*rhs.c1);
  81 }
  82
  83 template<mp_size_t n, const bigint<n>& modulus>
  84 Fp12_2over3over2_model<n, modulus> operator*(const Fp6_3over2_model<n, modulus> &lhs, const Fp12_2over3over2_model<n, modulus> &rhs)
  85 {
  86     return Fp12_2over3over2_model<n,modulus>(lhs*rhs.c0,
  87                                              lhs*rhs.c1);
  88 }
  89
  90 template<mp_size_t n, const bigint<n>& modulus>
  91 Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::operator*(const Fp12_2over3over2_model<n,modulus> &other) const
  92 {
  93     /* Devegili OhEig Scott Dahab --- Multiplication and Squaring on Pairing-Friendly Fields.pdf; Section 3 (Karatsuba) */
  94
  95     const my_Fp6 &A = other.c0, &B = other.c1,
  96         &a = this->c0, &b = this->c1;
  97     const my_Fp6 aA = a * A;
  98     const my_Fp6 bB = b * B;
  99
 100     return Fp12_2over3over2_model<n,modulus>(aA + Fp12_2over3over2_model<n, modulus>::mul_by_non_residue(bB),
 101                                              (a + b)*(A+B) - aA - bB);
 102 }
 103
 104 template<mp_size_t n, const bigint<n>& modulus>
 105 Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::operator-() const
 106 {
 107     return Fp12_2over3over2_model<n,modulus>(-this->c0,
 108                                              -this->c1);
 109 }
 110
 111 template<mp_size_t n, const bigint<n>& modulus>
 112 Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::squared() const
 113 {
 114     return squared_complex();
 115 }
 116
 117 template<mp_size_t n, const bigint<n>& modulus>
 118 Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::squared_karatsuba() const
 119 {
 120     /* Devegili OhEig Scott Dahab --- Multiplication and Squaring on Pairing-Friendly Fields.pdf; Section 3 (Karatsuba squaring) */
 121
 122     const my_Fp6 &a = this->c0, &b = this->c1;
 123     const my_Fp6 asq = a.squared();
 124     const my_Fp6 bsq = b.squared();
 125
 126     return Fp12_2over3over2_model<n,modulus>(asq + Fp12_2over3over2_model<n, modulus>::mul_by_non_residue(bsq),
 127                                              (a + b).squared() - asq - bsq);
 128 }
 129
 130 template<mp_size_t n, const bigint<n>& modulus>
 131 Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::squared_complex() const
 132 {
 133     /* Devegili OhEig Scott Dahab --- Multiplication and Squaring on Pairing-Friendly Fields.pdf; Section 3 (Complex squaring) */
 134
 135     const my_Fp6 &a = this->c0, &b = this->c1;
 136     const my_Fp6 ab = a * b;
 137
 138     return Fp12_2over3over2_model<n,modulus>((a + b) * (a + Fp12_2over3over2_model<n, modulus>::mul_by_non_residue(b)) - ab - Fp12_2over3over2_model<n, modulus>::mul_by_non_residue(ab),
 139                                              ab + ab);
 140 }
 141
 142 template<mp_size_t n, const bigint<n>& modulus>
 143 Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::inverse() const
 144 {
 145     /* From "High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-Naehrig Curves"; Algorithm 8 */
 146
 147     const my_Fp6 &a = this->c0, &b = this->c1;
 148     const my_Fp6 t0 = a.squared();
 149     const my_Fp6 t1 = b.squared();
 150     const my_Fp6 t2 = t0 - Fp12_2over3over2_model<n, modulus>::mul_by_non_residue(t1);
 151     const my_Fp6 t3 = t2.inverse();
 152     const my_Fp6 c0 = a * t3;
 153     const my_Fp6 c1 = - (b * t3);
 154
 155     return Fp12_2over3over2_model<n,modulus>(c0, c1);
 156 }
 157
 158 template<mp_size_t n, const bigint<n>& modulus>
 159 Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::Frobenius_map(unsigned long power) const
 160 {
 161     return Fp12_2over3over2_model<n,modulus>(c0.Frobenius_map(power),
 162                                              Frobenius_coeffs_c1[power % 12] * c1.Frobenius_map(power));
 163 }
 164
 165 template<mp_size_t n, const bigint<n>& modulus>
 166 Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::unitary_inverse() const
 167 {
 168     return Fp12_2over3over2_model<n,modulus>(this->c0,
 169                                              -this->c1);
 170 }
 171
 172 template<mp_size_t n, const bigint<n>& modulus>
 173 Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::cyclotomic_squared() const
 174 {
 175     /* OLD: naive implementation
 176        return (*this).squared();
 177     */
 178     my_Fp2 z0 = this->c0.c0;
 179     my_Fp2 z4 = this->c0.c1;
 180     my_Fp2 z3 = this->c0.c2;
 181     my_Fp2 z2 = this->c1.c0;
 182     my_Fp2 z1 = this->c1.c1;
 183     my_Fp2 z5 = this->c1.c2;
 184
 185     my_Fp2 t0, t1, t2, t3, t4, t5, tmp;
 186
 187     // t0 + t1*y = (z0 + z1*y)^2 = a^2
 188     tmp = z0 * z1;
 189     t0 = (z0 + z1) * (z0 + my_Fp6::non_residue * z1) - tmp - my_Fp6::non_residue * tmp;
 190     t1 = tmp + tmp;
 191     // t2 + t3*y = (z2 + z3*y)^2 = b^2
 192     tmp = z2 * z3;
 193     t2 = (z2 + z3) * (z2 + my_Fp6::non_residue * z3) - tmp - my_Fp6::non_residue * tmp;
 194     t3 = tmp + tmp;
 195     // t4 + t5*y = (z4 + z5*y)^2 = c^2
 196     tmp = z4 * z5;
 197     t4 = (z4 + z5) * (z4 + my_Fp6::non_residue * z5) - tmp - my_Fp6::non_residue * tmp;
 198     t5 = tmp + tmp;
 199
 200     // for A
 201
 202     // z0 = 3 * t0 - 2 * z0
 203     z0 = t0 - z0;
 204     z0 = z0 + z0;
 205     z0 = z0 + t0;
 206     // z1 = 3 * t1 + 2 * z1
 207     z1 = t1 + z1;
 208     z1 = z1 + z1;
 209     z1 = z1 + t1;
 210
 211     // for B
 212
 213     // z2 = 3 * (xi * t5) + 2 * z2
 214     tmp = my_Fp6::non_residue * t5;
 215     z2 = tmp + z2;
 216     z2 = z2 + z2;
 217     z2 = z2 + tmp;
 218
 219     // z3 = 3 * t4 - 2 * z3
 220     z3 = t4 - z3;
 221     z3 = z3 + z3;
 222     z3 = z3 + t4;
 223
 224     // for C
 225
 226     // z4 = 3 * t2 - 2 * z4
 227     z4 = t2 - z4;
 228     z4 = z4 + z4;
 229     z4 = z4 + t2;
 230
 231     // z5 = 3 * t3 + 2 * z5
 232     z5 = t3 + z5;
 233     z5 = z5 + z5;
 234     z5 = z5 + t3;
 235
 236     return Fp12_2over3over2_model<n,modulus>(my_Fp6(z0,z4,z3),my_Fp6(z2,z1,z5));
 237 }
 238
 239 template<mp_size_t n, const bigint<n>& modulus>
 240 Fp12_2over3over2_model<n,modulus> Fp12_2over3over2_model<n,modulus>::mul_by_024(const Fp2_model<n, modulus> &ell_0,
 241                                                                                 const Fp2_model<n, modulus> &ell_VW,
 242                                                                                 const Fp2_model<n, modulus> &ell_VV) const
 243 {
 244     /* OLD: naive implementation
 245        Fp12_2over3over2_model<n,modulus> a(my_Fp6(ell_0, my_Fp2::zero(), ell_VV),
 246        my_Fp6(my_Fp2::zero(), ell_VW, my_Fp2::zero()));
 247
 248        return (*this) * a;
 249     */
 250     my_Fp2 z0 = this->c0.c0;
 251     my_Fp2 z1 = this->c0.c1;
 252     my_Fp2 z2 = this->c0.c2;
 253     my_Fp2 z3 = this->c1.c0;
 254     my_Fp2 z4 = this->c1.c1;
 255     my_Fp2 z5 = this->c1.c2;
 256
 257     my_Fp2 x0 = ell_0;
 258     my_Fp2 x2 = ell_VV;
 259     my_Fp2 x4 = ell_VW;
 260
 261     my_Fp2 t0, t1, t2, s0, T3, T4, D0, D2, D4, S1;
 262
 263     D0 = z0 * x0;
 264     D2 = z2 * x2;
 265     D4 = z4 * x4;
 266     t2 = z0 + z4;
 267     t1 = z0 + z2;
 268     s0 = z1 + z3 + z5;
 269
 270     // For z.a_.a_ = z0.
 271     S1 = z1 * x2;
 272     T3 = S1 + D4;
 273     T4 = my_Fp6::non_residue * T3 + D0;
 274     z0 = T4;
 275
 276     // For z.a_.b_ = z1
 277     T3 = z5 * x4;
 278     S1 = S1 + T3;
 279     T3 = T3 + D2;
 280     T4 = my_Fp6::non_residue * T3;
 281     T3 = z1 * x0;
 282     S1 = S1 + T3;
 283     T4 = T4 + T3;
 284     z1 = T4;
 285
 286     // For z.a_.c_ = z2
 287     t0 = x0 + x2;
 288     T3 = t1 * t0 - D0 - D2;
 289     T4 = z3 * x4;
 290     S1 = S1 + T4;
 291     T3 = T3 + T4;
 292
 293     // For z.b_.a_ = z3 (z3 needs z2)
 294     t0 = z2 + z4;
 295     z2 = T3;
 296     t1 = x2 + x4;
 297     T3 = t0 * t1 - D2 - D4;
 298     T4 = my_Fp6::non_residue * T3;
 299     T3 = z3 * x0;
 300     S1 = S1 + T3;
 301     T4 = T4 + T3;
 302     z3 = T4;
 303
 304     // For z.b_.b_ = z4
 305     T3 = z5 * x2;
 306     S1 = S1 + T3;
 307     T4 = my_Fp6::non_residue * T3;
 308     t0 = x0 + x4;
 309     T3 = t2 * t0 - D0 - D4;
 310     T4 = T4 + T3;
 311     z4 = T4;
 312
 313     // For z.b_.c_ = z5.
 314     t0 = x0 + x2 + x4;
 315     T3 = s0 * t0 - S1;
 316     z5 = T3;
 317
 318     return Fp12_2over3over2_model<n,modulus>(my_Fp6(z0,z1,z2),my_Fp6(z3,z4,z5));
 319
 320 }
 321
 322 template<mp_size_t n, const bigint<n>& modulus, mp_size_t m>
 323 Fp12_2over3over2_model<n, modulus> operator^(const Fp12_2over3over2_model<n, modulus> &self, const bigint<m> &exponent)
 324 {
 325     return power<Fp12_2over3over2_model<n, modulus> >(self, exponent);
 326 }
 327
 328 template<mp_size_t n, const bigint<n>& modulus, mp_size_t m, const bigint<m>& exp_modulus>
 329 Fp12_2over3over2_model<n, modulus> operator^(const Fp12_2over3over2_model<n, modulus> &self, const Fp_model<m, exp_modulus> &exponent)
 330 {
 331     return self^(exponent.as_bigint());
 332 }
 333
 334
 335 template<mp_size_t n, const bigint<n>& modulus>
 336 template<mp_size_t m>
 337 Fp12_2over3over2_model<n, modulus> Fp12_2over3over2_model<n,modulus>::cyclotomic_exp(const bigint<m> &exponent) const
 338 {
 339     Fp12_2over3over2_model<n,modulus> res = Fp12_2over3over2_model<n,modulus>::one();
 340
 341     bool found_one = false;
 342     for (long i = m-1; i >= 0; --i)
 343     {
 344         for (long j = GMP_NUMB_BITS - 1; j >= 0; --j)
 345         {
 346             if (found_one)
 347             {
 348                 res = res.cyclotomic_squared();
 349             }
 350
 351             if (exponent.data[i] & (1ul<<j))
 352             {
 353                 found_one = true;
 354                 res = res * (*this);
 355             }
 356         }
 357     }
 358
 359     return res;
 360 }
 361
 362 template<mp_size_t n, const bigint<n>& modulus>
 363 std::ostream& operator<<(std::ostream &out, const Fp12_2over3over2_model<n, modulus> &el)
 364 {
 365     out << el.c0 << OUTPUT_SEPARATOR << el.c1;
 366     return out;
 367 }
 368
 369 template<mp_size_t n, const bigint<n>& modulus>
 370 std::istream& operator>>(std::istream &in, Fp12_2over3over2_model<n, modulus> &el)
 371 {
 372     in >> el.c0 >> el.c1;
 373     return in;
 374 }
 375
 376 template<mp_size_t n, const bigint<n>& modulus>
 377 std::ostream& operator<<(std::ostream& out, const std::vector<Fp12_2over3over2_model<n, modulus> > &v)
 378 {
 379     out << v.size() << "\n";
 380     for (const Fp12_2over3over2_model<n, modulus>& t : v)
 381     {
 382         out << t << OUTPUT_NEWLINE;
 383     }
 384
 385     return out;
 386 }
 387
 388 template<mp_size_t n, const bigint<n>& modulus>
 389 std::istream& operator>>(std::istream& in, std::vector<Fp12_2over3over2_model<n, modulus> > &v)
 390 {
 391     v.clear();
 392
 393     size_t s;
 394     in >> s;
 395
 396     char b;
 397     in.read(&b, 1);
 398
 399     v.reserve(s);
 400
 401     for (size_t i = 0; i < s; ++i)
 402     {
 403         Fp12_2over3over2_model<n, modulus> el;
 404         in >> el;
 405         v.emplace_back(el);
 406     }
 407
 408     return in;
 409 }
 410
 411 } // libsnark
 412 #endif // FP12_2OVER3OVER2_TCC_