fp2.tcc

Go to the documentation of this file.

/** @file
 *****************************************************************************
 Implementation of arithmetic in the finite field F[p^2].
 *****************************************************************************
 * @author     This file is part of libff, developed by SCIPR Lab
 *             and contributors (see AUTHORS).
 * @copyright  MIT license (see LICENSE file)
 *****************************************************************************/
 
#ifndef FP2_TCC_
#define FP2_TCC_
 
#include <libff/algebra/fields/field_utils.hpp>
 
namespace libff
{
 
template<mp_size_t n, const bigint<n> &modulus>
bool Fp2_model<n, modulus>::s_initialized = false;
 
template<mp_size_t n, const bigint<n> &modulus>
Fp2_model<n, modulus> Fp2_model<n, modulus>::s_zero;
 
template<mp_size_t n, const bigint<n> &modulus>
Fp2_model<n, modulus> Fp2_model<n, modulus>::s_one;
 
template<mp_size_t n, const bigint<n> &modulus>
void Fp2_model<n, modulus>::static_init()
{
    // This function may be entered several times, in particular where an
    // individual field is shread between curves.
    if (s_initialized) {
        return;
    }
 
    // Initialize s_zero and s_one
    s_zero = Fp2_model<n, modulus>(my_Fp::zero(), my_Fp::zero());
    s_one = Fp2_model<n, modulus>(my_Fp::one(), my_Fp::zero());
    s_initialized = true;
}
 
template<mp_size_t n, const bigint<n> &modulus>
const Fp2_model<n, modulus> &Fp2_model<n, modulus>::zero()
{
    return s_zero;
}
 
template<mp_size_t n, const bigint<n> &modulus>
const Fp2_model<n, modulus> &Fp2_model<n, modulus>::one()
{
    return s_one;
}
 
template<mp_size_t n, const bigint<n> &modulus>
Fp2_model<n, modulus> Fp2_model<n, modulus>::random_element()
{
    Fp2_model<n, modulus> r;
    r.coeffs[0] = my_Fp::random_element();
    r.coeffs[1] = my_Fp::random_element();
 
    return r;
}
 
template<mp_size_t n, const bigint<n> &modulus>
bool Fp2_model<n, modulus>::operator==(const Fp2_model<n, modulus> &other) const
{
    return (
        this->coeffs[0] == other.coeffs[0] &&
        this->coeffs[1] == other.coeffs[1]);
}
 
template<mp_size_t n, const bigint<n> &modulus>
bool Fp2_model<n, modulus>::operator!=(const Fp2_model<n, modulus> &other) const
{
    return !(operator==(other));
}
 
template<mp_size_t n, const bigint<n> &modulus>
Fp2_model<n, modulus> Fp2_model<n, modulus>::operator+(
    const Fp2_model<n, modulus> &other) const
{
    return Fp2_model<n, modulus>(
        this->coeffs[0] + other.coeffs[0], this->coeffs[1] + other.coeffs[1]);
}
 
template<mp_size_t n, const bigint<n> &modulus>
Fp2_model<n, modulus> Fp2_model<n, modulus>::operator-(
    const Fp2_model<n, modulus> &other) const
{
    return Fp2_model<n, modulus>(
        this->coeffs[0] - other.coeffs[0], this->coeffs[1] - other.coeffs[1]);
}
 
template<mp_size_t n, const bigint<n> &modulus>
Fp2_model<n, modulus> operator*(
    const Fp_model<n, modulus> &lhs, const Fp2_model<n, modulus> &rhs)
{
    return Fp2_model<n, modulus>(lhs * rhs.coeffs[0], lhs * rhs.coeffs[1]);
}
 
template<mp_size_t n, const bigint<n> &modulus>
Fp2_model<n, modulus> Fp2_model<n, modulus>::operator*(
    const Fp2_model<n, modulus> &other) const
{
    /* Devegili OhEig Scott Dahab --- Multiplication and Squaring on
     * Pairing-Friendly Fields.pdf; Section 3 (Karatsuba) */
    const my_Fp &A = other.coeffs[0], &B = other.coeffs[1],
                &a = this->coeffs[0], &b = this->coeffs[1];
    const my_Fp aA = a * A;
    const my_Fp bB = b * B;
 
    return Fp2_model<n, modulus>(
        aA + non_residue * bB, (a + b) * (A + B) - aA - bB);
}
 
template<mp_size_t n, const bigint<n> &modulus>
Fp2_model<n, modulus> Fp2_model<n, modulus>::operator-() const
{
    return Fp2_model<n, modulus>(-this->coeffs[0], -this->coeffs[1]);
}
 
template<mp_size_t n, const bigint<n> &modulus>
Fp2_model<n, modulus> Fp2_model<n, modulus>::squared() const
{
    return squared_complex();
}
 
template<mp_size_t n, const bigint<n> &modulus>
Fp2_model<n, modulus> Fp2_model<n, modulus>::squared_karatsuba() const
{
    // Devegili OhEig Scott Dahab --- Multiplication and Squaring on
    // Pairing-Friendly Fields.pdf; Section 3 (Karatsuba squaring)
    const my_Fp &a = this->coeffs[0], &b = this->coeffs[1];
    const my_Fp asq = a.squared();
    const my_Fp bsq = b.squared();
 
    return Fp2_model<n, modulus>(
        asq + non_residue * bsq, (a + b).squared() - asq - bsq);
}
 
template<mp_size_t n, const bigint<n> &modulus>
Fp2_model<n, modulus> Fp2_model<n, modulus>::squared_complex() const
{
    // Devegili OhEig Scott Dahab --- Multiplication and Squaring on
    // Pairing-Friendly Fields.pdf; Section 3 (Complex squaring)
    const my_Fp &a = this->coeffs[0], &b = this->coeffs[1];
    const my_Fp ab = a * b;
 
    return Fp2_model<n, modulus>(
        (a + b) * (a + non_residue * b) - ab - non_residue * ab, ab + ab);
}
 
template<mp_size_t n, const bigint<n> &modulus>
Fp2_model<n, modulus> Fp2_model<n, modulus>::inverse() const
{
    const my_Fp &a = this->coeffs[0], &b = this->coeffs[1];
 
    // From "High-Speed Software Implementation of the Optimal Ate Pairing over
    // Barreto-Naehrig Curves"; Algorithm 8
    const my_Fp t0 = a.squared();
    const my_Fp t1 = b.squared();
    const my_Fp t2 = t0 - non_residue * t1;
    const my_Fp t3 = t2.inverse();
    const my_Fp c0 = a * t3;
    const my_Fp c1 = -(b * t3);
 
    return Fp2_model<n, modulus>(c0, c1);
}
 
template<mp_size_t n, const bigint<n> &modulus>
Fp2_model<n, modulus> Fp2_model<n, modulus>::Frobenius_map(
    unsigned long power) const
{
    return Fp2_model<n, modulus>(
        coeffs[0], Frobenius_coeffs_c1[power % 2] * coeffs[1]);
}
 
template<mp_size_t n, const bigint<n> &modulus>
Fp2_model<n, modulus> Fp2_model<n, modulus>::sqrt() const
{
    Fp2_model<n, modulus> one = Fp2_model<n, modulus>::one();
 
    size_t v = Fp2_model<n, modulus>::s;
    Fp2_model<n, modulus> z = Fp2_model<n, modulus>::nqr_to_t;
    Fp2_model<n, modulus> w = (*this) ^ Fp2_model<n, modulus>::t_minus_1_over_2;
    Fp2_model<n, modulus> x = (*this) * w;
    // b = (*this)^t
    Fp2_model<n, modulus> b = x * w;
 
#if DEBUG
    // check if square with euler's criterion
    Fp2_model<n, modulus> check = b;
    for (size_t i = 0; i < v - 1; ++i) {
        check = check.squared();
    }
    if (check != one) {
        assert(0);
    }
#endif
 
    // compute square root with Tonelli--Shanks (does not terminate if not a
    // square!)
 
    while (b != one) {
        size_t m = 0;
        Fp2_model<n, modulus> b2m = b;
        while (b2m != one) {
            // invariant: b2m = b^(2^m) after entering this loop
            b2m = b2m.squared();
            m += 1;
        }
 
        // w = z^2^(v-m-1)
        int j = v - m - 1;
        w = z;
        while (j > 0) {
            w = w.squared();
            --j;
        }
 
        z = w.squared();
        b = b * z;
        x = x * w;
        v = m;
    }
 
    return x;
}
 
template<mp_size_t n, const bigint<n> &modulus>
template<mp_size_t m>
Fp2_model<n, modulus> Fp2_model<n, modulus>::operator^(
    const bigint<m> &pow) const
{
    return power<Fp2_model<n, modulus>, m>(*this, pow);
}
 
template<mp_size_t n, const bigint<n> &modulus>
std::ostream &operator<<(std::ostream &out, const Fp2_model<n, modulus> &el)
{
    out << el.coeffs[0] << el.coeffs[1];
    return out;
}
 
template<mp_size_t n, const bigint<n> &modulus>
std::istream &operator>>(std::istream &in, Fp2_model<n, modulus> &el)
{
    in >> el.coeffs[0] >> el.coeffs[1];
    return in;
}
 
template<mp_size_t n, const bigint<n> &modulus>
std::ostream &operator<<(
    std::ostream &out, const std::vector<Fp2_model<n, modulus>> &v)
{
    out << v.size() << "\n";
    for (const Fp2_model<n, modulus> &t : v) {
        out << t << OUTPUT_NEWLINE;
    }
 
    return out;
}
 
template<mp_size_t n, const bigint<n> &modulus>
std::istream &operator>>(
    std::istream &in, std::vector<Fp2_model<n, modulus>> &v)
{
    v.clear();
 
    size_t s;
    in >> s;
 
    char b;
    in.read(&b, 1);
 
    v.reserve(s);
 
    for (size_t i = 0; i < s; ++i) {
        Fp2_model<n, modulus> el;
        in >> el;
        v.emplace_back(el);
    }
 
    return in;
}
 
} // namespace libff
 
#endif // FP2_TCC_