You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

76 lines
1.8KB

  1. package main
  2. //import "fmt"
  3. import "math/big"
  4. //import "crypto/rand"
  5. //import "encoding/hex"
  6. import "github.com/clearmatics/bn256"
  7. //import "golang.org/x/crypto/sha3"
  8. type Polynomial struct {
  9. coefficients []*big.Int
  10. }
  11. func NewPolynomial(input []*big.Int) *Polynomial {
  12. if input == nil {
  13. return &Polynomial{coefficients: []*big.Int{new(big.Int).SetInt64(1)}}
  14. }
  15. return &Polynomial{coefficients: input}
  16. }
  17. func (p *Polynomial) Length() int {
  18. return len(p.coefficients)
  19. }
  20. func (p *Polynomial) Mul(m *Polynomial) *Polynomial {
  21. var product []*big.Int
  22. for i := range p.coefficients {
  23. product = append(product, new(big.Int).Mod(new(big.Int).Mul(p.coefficients[i], m.coefficients[0]), bn256.Order))
  24. }
  25. product = append(product, new(big.Int)) // add 0 element
  26. if m.coefficients[1].IsInt64() && m.coefficients[1].Int64() == 1 {
  27. for i := range product {
  28. if i > 0 {
  29. tmp := new(big.Int).Add(product[i], p.coefficients[i-1])
  30. product[i] = new(big.Int).Mod(tmp, bn256.Order)
  31. } else { // do nothing
  32. }
  33. }
  34. }
  35. return NewPolynomial(product)
  36. }
  37. type dummy struct {
  38. list [][]*big.Int
  39. }
  40. func RecursivePolynomials(list [][]*big.Int, accum *Polynomial, a, b []*big.Int) (rlist [][]*big.Int) {
  41. var d dummy
  42. d.recursivePolynomialsinternal(accum, a, b)
  43. return d.list
  44. }
  45. func (d *dummy) recursivePolynomialsinternal(accum *Polynomial, a, b []*big.Int) {
  46. if len(a) == 0 {
  47. d.list = append(d.list, accum.coefficients)
  48. return
  49. }
  50. atop := a[len(a)-1]
  51. btop := b[len(b)-1]
  52. left := NewPolynomial([]*big.Int{new(big.Int).Mod(new(big.Int).Neg(atop), bn256.Order), new(big.Int).Mod(new(big.Int).Sub(new(big.Int).SetInt64(1), btop), bn256.Order)})
  53. right := NewPolynomial([]*big.Int{atop, btop})
  54. d.recursivePolynomialsinternal(accum.Mul(left), a[:len(a)-1], b[:len(b)-1])
  55. d.recursivePolynomialsinternal(accum.Mul(right), a[:len(a)-1], b[:len(b)-1])
  56. }