gfp6.go 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214
  1. package bn256
  2. // For details of the algorithms used, see "Multiplication and Squaring on
  3. // Pairing-Friendly Fields, Devegili et al.
  4. // http://eprint.iacr.org/2006/471.pdf.
  5. // gfP6 implements the field of size p⁶ as a cubic extension of gfP2 where τ³=ξ
  6. // and ξ=i+3.
  7. type gfP6 struct {
  8. x, y, z gfP2 // value is xτ² + yτ + z
  9. }
  10. func (e *gfP6) String() string {
  11. return "(" + e.x.String() + ", " + e.y.String() + ", " + e.z.String() + ")"
  12. }
  13. func (e *gfP6) Set(a *gfP6) *gfP6 {
  14. e.x.Set(&a.x)
  15. e.y.Set(&a.y)
  16. e.z.Set(&a.z)
  17. return e
  18. }
  19. func (e *gfP6) SetZero() *gfP6 {
  20. e.x.SetZero()
  21. e.y.SetZero()
  22. e.z.SetZero()
  23. return e
  24. }
  25. func (e *gfP6) SetOne() *gfP6 {
  26. e.x.SetZero()
  27. e.y.SetZero()
  28. e.z.SetOne()
  29. return e
  30. }
  31. func (e *gfP6) IsZero() bool {
  32. return e.x.IsZero() && e.y.IsZero() && e.z.IsZero()
  33. }
  34. func (e *gfP6) IsOne() bool {
  35. return e.x.IsZero() && e.y.IsZero() && e.z.IsOne()
  36. }
  37. func (e *gfP6) Neg(a *gfP6) *gfP6 {
  38. e.x.Neg(&a.x)
  39. e.y.Neg(&a.y)
  40. e.z.Neg(&a.z)
  41. return e
  42. }
  43. func (e *gfP6) Frobenius(a *gfP6) *gfP6 {
  44. e.x.Conjugate(&a.x)
  45. e.y.Conjugate(&a.y)
  46. e.z.Conjugate(&a.z)
  47. e.x.Mul(&e.x, xiTo2PMinus2Over3)
  48. e.y.Mul(&e.y, xiToPMinus1Over3)
  49. return e
  50. }
  51. // FrobeniusP2 computes (xτ²+yτ+z)^(p²) = xτ^(2p²) + yτ^(p²) + z
  52. func (e *gfP6) FrobeniusP2(a *gfP6) *gfP6 {
  53. // τ^(2p²) = τ²τ^(2p²-2) = τ²ξ^((2p²-2)/3)
  54. e.x.MulScalar(&a.x, xiTo2PSquaredMinus2Over3)
  55. // τ^(p²) = ττ^(p²-1) = τξ^((p²-1)/3)
  56. e.y.MulScalar(&a.y, xiToPSquaredMinus1Over3)
  57. e.z.Set(&a.z)
  58. return e
  59. }
  60. func (e *gfP6) FrobeniusP4(a *gfP6) *gfP6 {
  61. e.x.MulScalar(&a.x, xiToPSquaredMinus1Over3)
  62. e.y.MulScalar(&a.y, xiTo2PSquaredMinus2Over3)
  63. e.z.Set(&a.z)
  64. return e
  65. }
  66. func (e *gfP6) Add(a, b *gfP6) *gfP6 {
  67. e.x.Add(&a.x, &b.x)
  68. e.y.Add(&a.y, &b.y)
  69. e.z.Add(&a.z, &b.z)
  70. return e
  71. }
  72. func (e *gfP6) Sub(a, b *gfP6) *gfP6 {
  73. e.x.Sub(&a.x, &b.x)
  74. e.y.Sub(&a.y, &b.y)
  75. e.z.Sub(&a.z, &b.z)
  76. return e
  77. }
  78. func (e *gfP6) Mul(a, b *gfP6) *gfP6 {
  79. // "Multiplication and Squaring on Pairing-Friendly Fields"
  80. // Section 4, Karatsuba method.
  81. // http://eprint.iacr.org/2006/471.pdf
  82. v0 := (&gfP2{}).Mul(&a.z, &b.z)
  83. v1 := (&gfP2{}).Mul(&a.y, &b.y)
  84. v2 := (&gfP2{}).Mul(&a.x, &b.x)
  85. t0 := (&gfP2{}).Add(&a.x, &a.y)
  86. t1 := (&gfP2{}).Add(&b.x, &b.y)
  87. tz := (&gfP2{}).Mul(t0, t1)
  88. tz.Sub(tz, v1).Sub(tz, v2).MulXi(tz).Add(tz, v0)
  89. t0.Add(&a.y, &a.z)
  90. t1.Add(&b.y, &b.z)
  91. ty := (&gfP2{}).Mul(t0, t1)
  92. t0.MulXi(v2)
  93. ty.Sub(ty, v0).Sub(ty, v1).Add(ty, t0)
  94. t0.Add(&a.x, &a.z)
  95. t1.Add(&b.x, &b.z)
  96. tx := (&gfP2{}).Mul(t0, t1)
  97. tx.Sub(tx, v0).Add(tx, v1).Sub(tx, v2)
  98. e.x.Set(tx)
  99. e.y.Set(ty)
  100. e.z.Set(tz)
  101. return e
  102. }
  103. func (e *gfP6) MulScalar(a *gfP6, b *gfP2) *gfP6 {
  104. e.x.Mul(&a.x, b)
  105. e.y.Mul(&a.y, b)
  106. e.z.Mul(&a.z, b)
  107. return e
  108. }
  109. func (e *gfP6) MulGFP(a *gfP6, b *gfP) *gfP6 {
  110. e.x.MulScalar(&a.x, b)
  111. e.y.MulScalar(&a.y, b)
  112. e.z.MulScalar(&a.z, b)
  113. return e
  114. }
  115. // MulTau computes τ·(aτ²+bτ+c) = bτ²+cτ+aξ
  116. func (e *gfP6) MulTau(a *gfP6) *gfP6 {
  117. tz := (&gfP2{}).MulXi(&a.x)
  118. ty := (&gfP2{}).Set(&a.y)
  119. e.y.Set(&a.z)
  120. e.x.Set(ty)
  121. e.z.Set(tz)
  122. return e
  123. }
  124. func (e *gfP6) Square(a *gfP6) *gfP6 {
  125. v0 := (&gfP2{}).Square(&a.z)
  126. v1 := (&gfP2{}).Square(&a.y)
  127. v2 := (&gfP2{}).Square(&a.x)
  128. c0 := (&gfP2{}).Add(&a.x, &a.y)
  129. c0.Square(c0).Sub(c0, v1).Sub(c0, v2).MulXi(c0).Add(c0, v0)
  130. c1 := (&gfP2{}).Add(&a.y, &a.z)
  131. c1.Square(c1).Sub(c1, v0).Sub(c1, v1)
  132. xiV2 := (&gfP2{}).MulXi(v2)
  133. c1.Add(c1, xiV2)
  134. c2 := (&gfP2{}).Add(&a.x, &a.z)
  135. c2.Square(c2).Sub(c2, v0).Add(c2, v1).Sub(c2, v2)
  136. e.x.Set(c2)
  137. e.y.Set(c1)
  138. e.z.Set(c0)
  139. return e
  140. }
  141. func (e *gfP6) Invert(a *gfP6) *gfP6 {
  142. // See "Implementing cryptographic pairings", M. Scott, section 3.2.
  143. // ftp://136.206.11.249/pub/crypto/pairings.pdf
  144. // Here we can give a short explanation of how it works: let j be a cubic root of
  145. // unity in GF(p²) so that 1+j+j²=0.
  146. // Then (xτ² + yτ + z)(xj²τ² + yjτ + z)(xjτ² + yj²τ + z)
  147. // = (xτ² + yτ + z)(Cτ²+Bτ+A)
  148. // = (x³ξ²+y³ξ+z³-3ξxyz) = F is an element of the base field (the norm).
  149. //
  150. // On the other hand (xj²τ² + yjτ + z)(xjτ² + yj²τ + z)
  151. // = τ²(y²-ξxz) + τ(ξx²-yz) + (z²-ξxy)
  152. //
  153. // So that's why A = (z²-ξxy), B = (ξx²-yz), C = (y²-ξxz)
  154. t1 := (&gfP2{}).Mul(&a.x, &a.y)
  155. t1.MulXi(t1)
  156. A := (&gfP2{}).Square(&a.z)
  157. A.Sub(A, t1)
  158. B := (&gfP2{}).Square(&a.x)
  159. B.MulXi(B)
  160. t1.Mul(&a.y, &a.z)
  161. B.Sub(B, t1)
  162. C := (&gfP2{}).Square(&a.y)
  163. t1.Mul(&a.x, &a.z)
  164. C.Sub(C, t1)
  165. F := (&gfP2{}).Mul(C, &a.y)
  166. F.MulXi(F)
  167. t1.Mul(A, &a.z)
  168. F.Add(F, t1)
  169. t1.Mul(B, &a.x).MulXi(t1)
  170. F.Add(F, t1)
  171. F.Invert(F)
  172. e.x.Mul(C, F)
  173. e.y.Mul(B, F)
  174. e.z.Mul(A, F)
  175. return e
  176. }