/*
 * Copyright (C) 2019 ING BANK N.V.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */

package bn256

// For details of the algorithms used, see "Multiplication and Squaring on
// Pairing-Friendly Fields, Devegili et al.
// http://eprint.iacr.org/2006/471.pdf.

import (
    "math/big"
)

// gfP2 implements a field of size p² as a quadratic extension of the base
// field where i²=-1.
type gfP2 struct {
    X, Y *big.Int // value is xi+y.
}

func newGFp2(pool *bnPool) *gfP2 {
    return &gfP2{pool.Get(), pool.Get()}
}

func (e *gfP2) String() string {
    x := new(big.Int).Mod(e.X, P)
    y := new(big.Int).Mod(e.Y, P)
    return "(" + x.String() + "," + y.String() + ")"
}

func (e *gfP2) Put(pool *bnPool) {
    pool.Put(e.X)
    pool.Put(e.Y)
}

func (e *gfP2) Set(a *gfP2) *gfP2 {
    e.X.Set(a.X)
    e.Y.Set(a.Y)
    return e
}

func (e *gfP2) SetZero() *gfP2 {
    e.X.SetInt64(0)
    e.Y.SetInt64(0)
    return e
}

func (e *gfP2) SetOne() *gfP2 {
    e.X.SetInt64(0)
    e.Y.SetInt64(1)
    return e
}

func (e *gfP2) Minimal() {
    if e.X.Sign() < 0 || e.X.Cmp(P) >= 0 {
        e.X.Mod(e.X, P)
    }
    if e.Y.Sign() < 0 || e.Y.Cmp(P) >= 0 {
        e.Y.Mod(e.Y, P)
    }
}

func (e *gfP2) IsZero() bool {
    return e.X.Sign() == 0 && e.Y.Sign() == 0
}

func (e *gfP2) IsOne() bool {
    if e.X.Sign() != 0 {
        return false
    }
    words := e.Y.Bits()
    return len(words) == 1 && words[0] == 1
}

func (e *gfP2) Conjugate(a *gfP2) *gfP2 {
    e.Y.Set(a.Y)
    e.X.Neg(a.X)
    return e
}

func (e *gfP2) Negative(a *gfP2) *gfP2 {
    e.X.Neg(a.X)
    e.Y.Neg(a.Y)
    return e
}

func (e *gfP2) Add(a, b *gfP2) *gfP2 {
    e.X.Add(a.X, b.X)
    e.Y.Add(a.Y, b.Y)
    return e
}

func (e *gfP2) Sub(a, b *gfP2) *gfP2 {
    e.X.Sub(a.X, b.X)
    e.Y.Sub(a.Y, b.Y)
    return e
}

func (e *gfP2) Double(a *gfP2) *gfP2 {
    e.X.Lsh(a.X, 1)
    e.Y.Lsh(a.Y, 1)
    return e
}

func (c *gfP2) Exp(a *gfP2, power *big.Int, pool *bnPool) *gfP2 {
    sum := newGFp2(pool)
    sum.SetOne()
    t := newGFp2(pool)

    for i := power.BitLen() - 1; i >= 0; i-- {
        t.Square(sum, pool)
        if power.Bit(i) != 0 {
            sum.Mul(t, a, pool)
        } else {
            sum.Set(t)
        }
    }

    c.Set(sum)

    sum.Put(pool)
    t.Put(pool)

    return c
}

// See "Multiplication and Squaring in Pairing-Friendly Fields",
// http://eprint.iacr.org/2006/471.pdf
func (e *gfP2) Mul(a, b *gfP2, pool *bnPool) *gfP2 {
    tx := pool.Get().Mul(a.X, b.Y)
    t := pool.Get().Mul(b.X, a.Y)
    tx.Add(tx, t)
    tx.Mod(tx, P)

    ty := pool.Get().Mul(a.Y, b.Y)
    t.Mul(a.X, b.X)
    ty.Sub(ty, t)
    e.Y.Mod(ty, P)
    e.X.Set(tx)

    pool.Put(tx)
    pool.Put(ty)
    pool.Put(t)

    return e
}

func (e *gfP2) MulScalar(a *gfP2, b *big.Int) *gfP2 {
    e.X.Mul(a.X, b)
    e.Y.Mul(a.Y, b)
    return e
}

// MulXi sets e=ξa where ξ=i+9 and then returns e.
func (e *gfP2) MulXi(a *gfP2, pool *bnPool) *gfP2 {
    // (xi+y)(i+3) = (9x+y)i+(9y-x)
    tx := pool.Get().Lsh(a.X, 3)
    tx.Add(tx, a.X)
    tx.Add(tx, a.Y)

    ty := pool.Get().Lsh(a.Y, 3)
    ty.Add(ty, a.Y)
    ty.Sub(ty, a.X)

    e.X.Set(tx)
    e.Y.Set(ty)

    pool.Put(tx)
    pool.Put(ty)

    return e
}

func (e *gfP2) Square(a *gfP2, pool *bnPool) *gfP2 {
    // Complex squaring algorithm:
    // (xi+b)² = (x+y)(y-x) + 2*i*x*y
    t1 := pool.Get().Sub(a.Y, a.X)
    t2 := pool.Get().Add(a.X, a.Y)
    ty := pool.Get().Mul(t1, t2)
    ty.Mod(ty, P)

    t1.Mul(a.X, a.Y)
    t1.Lsh(t1, 1)

    e.X.Mod(t1, P)
    e.Y.Set(ty)

    pool.Put(t1)
    pool.Put(t2)
    pool.Put(ty)

    return e
}

func (e *gfP2) Invert(a *gfP2, pool *bnPool) *gfP2 {
    // See "Implementing cryptographic pairings", M. Scott, section 3.2.
    // ftp://136.206.11.249/pub/crypto/pairings.pdf
    t := pool.Get()
    t.Mul(a.Y, a.Y)
    t2 := pool.Get()
    t2.Mul(a.X, a.X)
    t.Add(t, t2)

    inv := pool.Get()
    inv.ModInverse(t, P)

    e.X.Neg(a.X)
    e.X.Mul(e.X, inv)
    e.X.Mod(e.X, P)

    e.Y.Mul(a.Y, inv)
    e.Y.Mod(e.Y, P)

    pool.Put(t)
    pool.Put(t2)
    pool.Put(inv)

    return e
}

func (e *gfP2) Real() *big.Int {
    return e.X
}

func (e *gfP2) Imag() *big.Int {
    return e.Y
}