gfp12.go

Documentation: golang.org/x/crypto/bn256

     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(a.x, b, pool)
   129  	e.y.Mul(a.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  }
   201
View as plain text