gfp2.go 3.7 KB

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