vendor/golang.org/x/crypto/bn256/gfp12.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 // gfP12 implements the field of size p¹² as a quadratic extension of gfP6
  16 // where ω²=τ.
  17 type gfP12 struct {
  18         x, y *gfP6 // value is xω + y
  19 }
  20
  21 func newGFp12(pool *bnPool) *gfP12 {
  22         return &gfP12{newGFp6(pool), newGFp6(pool)}
  23 }
  24
  25 func (e *gfP12) String() string {
  26         return "(" + e.x.String() + "," + e.y.String() + ")"
  27 }
  28
  29 func (e *gfP12) Put(pool *bnPool) {
  30         e.x.Put(pool)
  31         e.y.Put(pool)
  32 }
  33
  34 func (e *gfP12) Set(a *gfP12) *gfP12 {
  35         e.x.Set(a.x)
  36         e.y.Set(a.y)
  37         return e
  38 }
  39
  40 func (e *gfP12) SetZero() *gfP12 {
  41         e.x.SetZero()
  42         e.y.SetZero()
  43         return e
  44 }
  45
  46 func (e *gfP12) SetOne() *gfP12 {
  47         e.x.SetZero()
  48         e.y.SetOne()
  49         return e
  50 }
  51
  52 func (e *gfP12) Minimal() {
  53         e.x.Minimal()
  54         e.y.Minimal()
  55 }
  56
  57 func (e *gfP12) IsZero() bool {
  58         e.Minimal()
  59         return e.x.IsZero() && e.y.IsZero()
  60 }
  61
  62 func (e *gfP12) IsOne() bool {
  63         e.Minimal()
  64         return e.x.IsZero() && e.y.IsOne()
  65 }
  66
  67 func (e *gfP12) Conjugate(a *gfP12) *gfP12 {
  68         e.x.Negative(a.x)
  69         e.y.Set(a.y)
  70         return a
  71 }
  72
  73 func (e *gfP12) Negative(a *gfP12) *gfP12 {
  74         e.x.Negative(a.x)
  75         e.y.Negative(a.y)
  76         return e
  77 }
  78
  79 // Frobenius computes (xω+y)^p = x^p ω·ξ^((p-1)/6) + y^p
  80 func (e *gfP12) Frobenius(a *gfP12, pool *bnPool) *gfP12 {
  81         e.x.Frobenius(a.x, pool)
  82         e.y.Frobenius(a.y, pool)
  83         e.x.MulScalar(e.x, xiToPMinus1Over6, pool)
  84         return e
  85 }
  86
  87 // FrobeniusP2 computes (xω+y)^p² = x^p² ω·ξ^((p²-1)/6) + y^p²
  88 func (e *gfP12) FrobeniusP2(a *gfP12, pool *bnPool) *gfP12 {
  89         e.x.FrobeniusP2(a.x)
  90         e.x.MulGFP(e.x, xiToPSquaredMinus1Over6)
  91         e.y.FrobeniusP2(a.y)
  92         return e
  93 }
  94
  95 func (e *gfP12) Add(a, b *gfP12) *gfP12 {
  96         e.x.Add(a.x, b.x)
  97         e.y.Add(a.y, b.y)
  98         return e
  99 }
 100
 101 func (e *gfP12) Sub(a, b *gfP12) *gfP12 {
 102         e.x.Sub(a.x, b.x)
 103         e.y.Sub(a.y, b.y)
 104         return e
 105 }
 106
 107 func (e *gfP12) Mul(a, b *gfP12, pool *bnPool) *gfP12 {
 108         tx := newGFp6(pool)
 109         tx.Mul(a.x, b.y, pool)
 110         t := newGFp6(pool)
 111         t.Mul(b.x, a.y, pool)
 112         tx.Add(tx, t)
 113
 114         ty := newGFp6(pool)
 115         ty.Mul(a.y, b.y, pool)
 116         t.Mul(a.x, b.x, pool)
 117         t.MulTau(t, pool)
 118         e.y.Add(ty, t)
 119         e.x.Set(tx)
 120
 121         tx.Put(pool)
 122         ty.Put(pool)
 123         t.Put(pool)
 124         return e
 125 }
 126
 127 func (e *gfP12) MulScalar(a *gfP12, b *gfP6, pool *bnPool) *gfP12 {
 128         e.x.Mul(e.x, b, pool)
 129         e.y.Mul(e.y, b, pool)
 130         return e
 131 }
 132
 133 func (c *gfP12) Exp(a *gfP12, power *big.Int, pool *bnPool) *gfP12 {
 134         sum := newGFp12(pool)
 135         sum.SetOne()
 136         t := newGFp12(pool)
 137
 138         for i := power.BitLen() - 1; i >= 0; i-- {
 139                 t.Square(sum, pool)
 140                 if power.Bit(i) != 0 {
 141                         sum.Mul(t, a, pool)
 142                 } else {
 143                         sum.Set(t)
 144                 }
 145         }
 146
 147         c.Set(sum)
 148
 149         sum.Put(pool)
 150         t.Put(pool)
 151
 152         return c
 153 }
 154
 155 func (e *gfP12) Square(a *gfP12, pool *bnPool) *gfP12 {
 156         // Complex squaring algorithm
 157         v0 := newGFp6(pool)
 158         v0.Mul(a.x, a.y, pool)
 159
 160         t := newGFp6(pool)
 161         t.MulTau(a.x, pool)
 162         t.Add(a.y, t)
 163         ty := newGFp6(pool)
 164         ty.Add(a.x, a.y)
 165         ty.Mul(ty, t, pool)
 166         ty.Sub(ty, v0)
 167         t.MulTau(v0, pool)
 168         ty.Sub(ty, t)
 169
 170         e.y.Set(ty)
 171         e.x.Double(v0)
 172
 173         v0.Put(pool)
 174         t.Put(pool)
 175         ty.Put(pool)
 176
 177         return e
 178 }
 179
 180 func (e *gfP12) Invert(a *gfP12, pool *bnPool) *gfP12 {
 181         // See "Implementing cryptographic pairings", M. Scott, section 3.2.
 182         // ftp://136.206.11.249/pub/crypto/pairings.pdf
 183         t1 := newGFp6(pool)
 184         t2 := newGFp6(pool)
 185
 186         t1.Square(a.x, pool)
 187         t2.Square(a.y, pool)
 188         t1.MulTau(t1, pool)
 189         t1.Sub(t2, t1)
 190         t2.Invert(t1, pool)
 191
 192         e.x.Negative(a.x)
 193         e.y.Set(a.y)
 194         e.MulScalar(e, t2, pool)
 195
 196         t1.Put(pool)
 197         t2.Put(pool)
 198
 199         return e
 200 }