vendor/golang.org/x/crypto/bn256/gfp2.go

   1 // Copyright 2012 The Go Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 package bn256
   6
   7 // For details of the algorithms used, see "Multiplication and Squaring on
   8 // Pairing-Friendly Fields, Devegili et al.
   9 // http://eprint.iacr.org/2006/471.pdf.
  10
  11 import (
  12         "math/big"
  13 )
  14
  15 // gfP2 implements a field of size p² as a quadratic extension of the base
  16 // field where i²=-1.
  17 type gfP2 struct {
  18         x, y *big.Int // value is xi+y.
  19 }
  20
  21 func newGFp2(pool *bnPool) *gfP2 {
  22         return &gfP2{pool.Get(), pool.Get()}
  23 }
  24
  25 func (e *gfP2) String() string {
  26         x := new(big.Int).Mod(e.x, p)
  27         y := new(big.Int).Mod(e.y, p)
  28         return "(" + x.String() + "," + y.String() + ")"
  29 }
  30
  31 func (e *gfP2) Put(pool *bnPool) {
  32         pool.Put(e.x)
  33         pool.Put(e.y)
  34 }
  35
  36 func (e *gfP2) Set(a *gfP2) *gfP2 {
  37         e.x.Set(a.x)
  38         e.y.Set(a.y)
  39         return e
  40 }
  41
  42 func (e *gfP2) SetZero() *gfP2 {
  43         e.x.SetInt64(0)
  44         e.y.SetInt64(0)
  45         return e
  46 }
  47
  48 func (e *gfP2) SetOne() *gfP2 {
  49         e.x.SetInt64(0)
  50         e.y.SetInt64(1)
  51         return e
  52 }
  53
  54 func (e *gfP2) Minimal() {
  55         if e.x.Sign() < 0 || e.x.Cmp(p) >= 0 {
  56                 e.x.Mod(e.x, p)
  57         }
  58         if e.y.Sign() < 0 || e.y.Cmp(p) >= 0 {
  59                 e.y.Mod(e.y, p)
  60         }
  61 }
  62
  63 func (e *gfP2) IsZero() bool {
  64         return e.x.Sign() == 0 && e.y.Sign() == 0
  65 }
  66
  67 func (e *gfP2) IsOne() bool {
  68         if e.x.Sign() != 0 {
  69                 return false
  70         }
  71         words := e.y.Bits()
  72         return len(words) == 1 && words[0] == 1
  73 }
  74
  75 func (e *gfP2) Conjugate(a *gfP2) *gfP2 {
  76         e.y.Set(a.y)
  77         e.x.Neg(a.x)
  78         return e
  79 }
  80
  81 func (e *gfP2) Negative(a *gfP2) *gfP2 {
  82         e.x.Neg(a.x)
  83         e.y.Neg(a.y)
  84         return e
  85 }
  86
  87 func (e *gfP2) Add(a, b *gfP2) *gfP2 {
  88         e.x.Add(a.x, b.x)
  89         e.y.Add(a.y, b.y)
  90         return e
  91 }
  92
  93 func (e *gfP2) Sub(a, b *gfP2) *gfP2 {
  94         e.x.Sub(a.x, b.x)
  95         e.y.Sub(a.y, b.y)
  96         return e
  97 }
  98
  99 func (e *gfP2) Double(a *gfP2) *gfP2 {
 100         e.x.Lsh(a.x, 1)
 101         e.y.Lsh(a.y, 1)
 102         return e
 103 }
 104
 105 func (c *gfP2) Exp(a *gfP2, power *big.Int, pool *bnPool) *gfP2 {
 106         sum := newGFp2(pool)
 107         sum.SetOne()
 108         t := newGFp2(pool)
 109
 110         for i := power.BitLen() - 1; i >= 0; i-- {
 111                 t.Square(sum, pool)
 112                 if power.Bit(i) != 0 {
 113                         sum.Mul(t, a, pool)
 114                 } else {
 115                         sum.Set(t)
 116                 }
 117         }
 118
 119         c.Set(sum)
 120
 121         sum.Put(pool)
 122         t.Put(pool)
 123
 124         return c
 125 }
 126
 127 // See "Multiplication and Squaring in Pairing-Friendly Fields",
 128 // http://eprint.iacr.org/2006/471.pdf
 129 func (e *gfP2) Mul(a, b *gfP2, pool *bnPool) *gfP2 {
 130         tx := pool.Get().Mul(a.x, b.y)
 131         t := pool.Get().Mul(b.x, a.y)
 132         tx.Add(tx, t)
 133         tx.Mod(tx, p)
 134
 135         ty := pool.Get().Mul(a.y, b.y)
 136         t.Mul(a.x, b.x)
 137         ty.Sub(ty, t)
 138         e.y.Mod(ty, p)
 139         e.x.Set(tx)
 140
 141         pool.Put(tx)
 142         pool.Put(ty)
 143         pool.Put(t)
 144
 145         return e
 146 }
 147
 148 func (e *gfP2) MulScalar(a *gfP2, b *big.Int) *gfP2 {
 149         e.x.Mul(a.x, b)
 150         e.y.Mul(a.y, b)
 151         return e
 152 }
 153
 154 // MulXi sets e=ξa where ξ=i+3 and then returns e.
 155 func (e *gfP2) MulXi(a *gfP2, pool *bnPool) *gfP2 {
 156         // (xi+y)(i+3) = (3x+y)i+(3y-x)
 157         tx := pool.Get().Lsh(a.x, 1)
 158         tx.Add(tx, a.x)
 159         tx.Add(tx, a.y)
 160
 161         ty := pool.Get().Lsh(a.y, 1)
 162         ty.Add(ty, a.y)
 163         ty.Sub(ty, a.x)
 164
 165         e.x.Set(tx)
 166         e.y.Set(ty)
 167
 168         pool.Put(tx)
 169         pool.Put(ty)
 170
 171         return e
 172 }
 173
 174 func (e *gfP2) Square(a *gfP2, pool *bnPool) *gfP2 {
 175         // Complex squaring algorithm:
 176         // (xi+b)² = (x+y)(y-x) + 2*i*x*y
 177         t1 := pool.Get().Sub(a.y, a.x)
 178         t2 := pool.Get().Add(a.x, a.y)
 179         ty := pool.Get().Mul(t1, t2)
 180         ty.Mod(ty, p)
 181
 182         t1.Mul(a.x, a.y)
 183         t1.Lsh(t1, 1)
 184
 185         e.x.Mod(t1, p)
 186         e.y.Set(ty)
 187
 188         pool.Put(t1)
 189         pool.Put(t2)
 190         pool.Put(ty)
 191
 192         return e
 193 }
 194
 195 func (e *gfP2) Invert(a *gfP2, pool *bnPool) *gfP2 {
 196         // See "Implementing cryptographic pairings", M. Scott, section 3.2.
 197         // ftp://136.206.11.249/pub/crypto/pairings.pdf
 198         t := pool.Get()
 199         t.Mul(a.y, a.y)
 200         t2 := pool.Get()
 201         t2.Mul(a.x, a.x)
 202         t.Add(t, t2)
 203
 204         inv := pool.Get()
 205         inv.ModInverse(t, p)
 206
 207         e.x.Neg(a.x)
 208         e.x.Mul(e.x, inv)
 209         e.x.Mod(e.x, p)
 210
 211         e.y.Mul(a.y, inv)
 212         e.y.Mod(e.y, p)
 213
 214         pool.Put(t)
 215         pool.Put(t2)
 216         pool.Put(inv)
 217
 218         return e
 219 }