gfp12.go 2.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161
  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. import (
  6. "math/big"
  7. )
  8. // gfP12 implements the field of size p¹² as a quadratic extension of gfP6
  9. // where ω²=τ.
  10. type gfP12 struct {
  11. x, y gfP6 // value is xω + y
  12. }
  13. func (e *gfP12) String() string {
  14. return "(" + e.x.String() + "," + e.y.String() + ")"
  15. }
  16. func (e *gfP12) Set(a *gfP12) *gfP12 {
  17. e.x.Set(&a.x)
  18. e.y.Set(&a.y)
  19. return e
  20. }
  21. func (e *gfP12) SetZero() *gfP12 {
  22. e.x.SetZero()
  23. e.y.SetZero()
  24. return e
  25. }
  26. func (e *gfP12) SetOne() *gfP12 {
  27. e.x.SetZero()
  28. e.y.SetOne()
  29. return e
  30. }
  31. func (e *gfP12) IsZero() bool {
  32. return e.x.IsZero() && e.y.IsZero()
  33. }
  34. func (e *gfP12) IsOne() bool {
  35. return e.x.IsZero() && e.y.IsOne()
  36. }
  37. func (e *gfP12) Conjugate(a *gfP12) *gfP12 {
  38. e.x.Neg(&a.x)
  39. e.y.Set(&a.y)
  40. return e
  41. }
  42. func (e *gfP12) Neg(a *gfP12) *gfP12 {
  43. e.x.Neg(&a.x)
  44. e.y.Neg(&a.y)
  45. return e
  46. }
  47. // Frobenius computes (xω+y)^p = x^p ω·ξ^((p-1)/6) + y^p
  48. func (e *gfP12) Frobenius(a *gfP12) *gfP12 {
  49. e.x.Frobenius(&a.x)
  50. e.y.Frobenius(&a.y)
  51. e.x.MulScalar(&e.x, xiToPMinus1Over6)
  52. return e
  53. }
  54. // FrobeniusP2 computes (xω+y)^p² = x^p² ω·ξ^((p²-1)/6) + y^p²
  55. func (e *gfP12) FrobeniusP2(a *gfP12) *gfP12 {
  56. e.x.FrobeniusP2(&a.x)
  57. e.x.MulGFP(&e.x, xiToPSquaredMinus1Over6)
  58. e.y.FrobeniusP2(&a.y)
  59. return e
  60. }
  61. func (e *gfP12) FrobeniusP4(a *gfP12) *gfP12 {
  62. e.x.FrobeniusP4(&a.x)
  63. e.x.MulGFP(&e.x, xiToPSquaredMinus1Over3)
  64. e.y.FrobeniusP4(&a.y)
  65. return e
  66. }
  67. func (e *gfP12) Add(a, b *gfP12) *gfP12 {
  68. e.x.Add(&a.x, &b.x)
  69. e.y.Add(&a.y, &b.y)
  70. return e
  71. }
  72. func (e *gfP12) Sub(a, b *gfP12) *gfP12 {
  73. e.x.Sub(&a.x, &b.x)
  74. e.y.Sub(&a.y, &b.y)
  75. return e
  76. }
  77. func (e *gfP12) Mul(a, b *gfP12) *gfP12 {
  78. tx := (&gfP6{}).Mul(&a.x, &b.y)
  79. t := (&gfP6{}).Mul(&b.x, &a.y)
  80. tx.Add(tx, t)
  81. ty := (&gfP6{}).Mul(&a.y, &b.y)
  82. t.Mul(&a.x, &b.x).MulTau(t)
  83. e.x.Set(tx)
  84. e.y.Add(ty, t)
  85. return e
  86. }
  87. func (e *gfP12) MulScalar(a *gfP12, b *gfP6) *gfP12 {
  88. e.x.Mul(&e.x, b)
  89. e.y.Mul(&e.y, b)
  90. return e
  91. }
  92. func (c *gfP12) Exp(a *gfP12, power *big.Int) *gfP12 {
  93. sum := (&gfP12{}).SetOne()
  94. t := &gfP12{}
  95. for i := power.BitLen() - 1; i >= 0; i-- {
  96. t.Square(sum)
  97. if power.Bit(i) != 0 {
  98. sum.Mul(t, a)
  99. } else {
  100. sum.Set(t)
  101. }
  102. }
  103. c.Set(sum)
  104. return c
  105. }
  106. func (e *gfP12) Square(a *gfP12) *gfP12 {
  107. // Complex squaring algorithm
  108. v0 := (&gfP6{}).Mul(&a.x, &a.y)
  109. t := (&gfP6{}).MulTau(&a.x)
  110. t.Add(&a.y, t)
  111. ty := (&gfP6{}).Add(&a.x, &a.y)
  112. ty.Mul(ty, t).Sub(ty, v0)
  113. t.MulTau(v0)
  114. ty.Sub(ty, t)
  115. e.x.Add(v0, v0)
  116. e.y.Set(ty)
  117. return e
  118. }
  119. func (e *gfP12) Invert(a *gfP12) *gfP12 {
  120. // See "Implementing cryptographic pairings", M. Scott, section 3.2.
  121. // ftp://136.206.11.249/pub/crypto/pairings.pdf
  122. t1, t2 := &gfP6{}, &gfP6{}
  123. t1.Square(&a.x)
  124. t2.Square(&a.y)
  125. t1.MulTau(t1).Sub(t2, t1)
  126. t2.Invert(t1)
  127. e.x.Neg(&a.x)
  128. e.y.Set(&a.y)
  129. e.MulScalar(e, t2)
  130. return e
  131. }