1 /** @file 2 ***************************************************************************** 3 Declaration of arithmetic in the finite field F[p^3]. 4 ***************************************************************************** 5 * @author This file is part of libff, developed by SCIPR Lab 6 * and contributors (see AUTHORS). 7 * @copyright MIT license (see LICENSE file) 8 *****************************************************************************/ 9 10 #ifndef FP3_HPP_ 11 #define FP3_HPP_ 12 #include <vector> 13 14 #include <libff/algebra/fields/fp.hpp> 15 16 namespace libff { 17 18 template<mp_size_t n, const bigint<n>& modulus> 19 class Fp3_model; 20 21 template<mp_size_t n, const bigint<n>& modulus> 22 std::ostream& operator<<(std::ostream &, const Fp3_model<n, modulus> &); 23 24 template<mp_size_t n, const bigint<n>& modulus> 25 std::istream& operator>>(std::istream &, Fp3_model<n, modulus> &); 26 27 /** 28 * Arithmetic in the field F[p^3]. 29 * 30 * Let p := modulus. This interface provides arithmetic for the extension field 31 * Fp3 = Fp[U]/(U^3-non_residue), where non_residue is in Fp. 32 * 33 * ASSUMPTION: p = 1 (mod 6) 34 */ 35 template<mp_size_t n, const bigint<n>& modulus> 36 class Fp3_model { 37 public: 38 typedef Fp_model<n, modulus> my_Fp; 39 40 static bigint<3*n> euler; // (modulus^3-1)/2 41 static size_t s; // modulus^3 = 2^s * t + 1 42 static bigint<3*n> t; // with t odd 43 static bigint<3*n> t_minus_1_over_2; // (t-1)/2 44 static my_Fp non_residue; // X^6-non_residue irreducible over Fp; used for constructing Fp3 = Fp[X] / (X^3 - non_residue) 45 static Fp3_model<n, modulus> nqr; // a quadratic nonresidue in Fp3 46 static Fp3_model<n, modulus> nqr_to_t; // nqr^t 47 static my_Fp Frobenius_coeffs_c1[3]; // non_residue^((modulus^i-1)/3) for i=0,1,2 48 static my_Fp Frobenius_coeffs_c2[3]; // non_residue^((2*modulus^i-2)/3) for i=0,1,2 49 50 my_Fp c0, c1, c2; Fp3_model()51 Fp3_model() {}; Fp3_model(const my_Fp & c0,const my_Fp & c1,const my_Fp & c2)52 Fp3_model(const my_Fp& c0, const my_Fp& c1, const my_Fp& c2) : c0(c0), c1(c1), c2(c2) {}; 53 clear()54 void clear() { c0.clear(); c1.clear(); c2.clear(); } print() const55 void print() const { printf("c0/c1/c2:\n"); c0.print(); c1.print(); c2.print(); } 56 57 static Fp3_model<n, modulus> zero(); 58 static Fp3_model<n, modulus> one(); 59 static Fp3_model<n, modulus> random_element(); 60 is_zero() const61 bool is_zero() const { return c0.is_zero() && c1.is_zero() && c2.is_zero(); } 62 bool operator==(const Fp3_model &other) const; 63 bool operator!=(const Fp3_model &other) const; 64 65 Fp3_model operator+(const Fp3_model &other) const; 66 Fp3_model operator-(const Fp3_model &other) const; 67 Fp3_model operator*(const Fp3_model &other) const; 68 Fp3_model operator-() const; 69 Fp3_model squared() const; 70 Fp3_model inverse() const; 71 Fp3_model Frobenius_map(unsigned long power) const; 72 Fp3_model sqrt() const; // HAS TO BE A SQUARE (else does not terminate) 73 74 template<mp_size_t m> 75 Fp3_model operator^(const bigint<m> &other) const; 76 size_in_bits()77 static size_t size_in_bits() { return 3*my_Fp::size_in_bits(); } base_field_char()78 static bigint<n> base_field_char() { return modulus; } 79 80 friend std::ostream& operator<< <n, modulus>(std::ostream &out, const Fp3_model<n, modulus> &el); 81 friend std::istream& operator>> <n, modulus>(std::istream &in, Fp3_model<n, modulus> &el); 82 }; 83 84 template<mp_size_t n, const bigint<n>& modulus> 85 std::ostream& operator<<(std::ostream& out, const std::vector<Fp3_model<n, modulus> > &v); 86 87 template<mp_size_t n, const bigint<n>& modulus> 88 std::istream& operator>>(std::istream& in, std::vector<Fp3_model<n, modulus> > &v); 89 90 template<mp_size_t n, const bigint<n>& modulus> 91 Fp3_model<n, modulus> operator*(const Fp_model<n, modulus> &lhs, const Fp3_model<n, modulus> &rhs); 92 93 template<mp_size_t n, const bigint<n>& modulus> 94 bigint<3*n> Fp3_model<n, modulus>::euler; 95 96 template<mp_size_t n, const bigint<n>& modulus> 97 size_t Fp3_model<n, modulus>::s; 98 99 template<mp_size_t n, const bigint<n>& modulus> 100 bigint<3*n> Fp3_model<n, modulus>::t; 101 102 template<mp_size_t n, const bigint<n>& modulus> 103 bigint<3*n> Fp3_model<n, modulus>::t_minus_1_over_2; 104 105 template<mp_size_t n, const bigint<n>& modulus> 106 Fp_model<n, modulus> Fp3_model<n, modulus>::non_residue; 107 108 template<mp_size_t n, const bigint<n>& modulus> 109 Fp3_model<n, modulus> Fp3_model<n, modulus>::nqr; 110 111 template<mp_size_t n, const bigint<n>& modulus> 112 Fp3_model<n, modulus> Fp3_model<n, modulus>::nqr_to_t; 113 114 template<mp_size_t n, const bigint<n>& modulus> 115 Fp_model<n, modulus> Fp3_model<n, modulus>::Frobenius_coeffs_c1[3]; 116 117 template<mp_size_t n, const bigint<n>& modulus> 118 Fp_model<n, modulus> Fp3_model<n, modulus>::Frobenius_coeffs_c2[3]; 119 120 } // libff 121 #include <libff/algebra/fields/fp3.tcc> 122 123 #endif // FP3_HPP_ 124