nockchain-grpc/crypto/bpoly.go

package crypto

type Bpoly struct {
	Value []Belt
}

func (p *Bpoly) IsZero() bool {
	length := len(p.Value)
	if length == 0 {
		return true
	}
	if length == 1 && p.Value[0].IsZero() {
		return true
	}

	for _, i := range p.Value {
		if !i.IsZero() {
			return false
		}
	}
	return true

}

func (p *Bpoly) Degree() uint32 {
	for i := len(p.Value) - 1; i >= 0; i-- {
		if !p.Value[i].IsZero() {
			return uint32(i)
		}
	}
	return 0
}

func (p *Bpoly) Add(other Bpoly) Bpoly {
	min := Bpoly{}
	max := Bpoly{}
	if len(p.Value) <= len(other.Value) {
		min = *p
		max = other
	} else {
		min = other
		max = *p
	}

	res := Bpoly{Value: make([]Belt, len(max.Value))}
	for i := range max.Value {
		if i < len(min.Value) {
			res.Value[i] = min.Value[i].Add(max.Value[i])
		} else {
			res.Value[i] = max.Value[i]
		}
	}
	return res
}

func (p *Bpoly) Sub(other Bpoly) Bpoly {
	resLen := len(p.Value)
	if len(other.Value) > resLen {
		resLen = len(other.Value)
	}
	res := Bpoly{Value: make([]Belt, resLen)}

	for i := 0; i < resLen; i++ {
		if i < len(p.Value) && i < len(other.Value) {
			res.Value[i] = p.Value[i].Sub(other.Value[i])
		} else if i < len(p.Value) {
			res.Value[i] = p.Value[i]
		} else {
			res.Value[i] = other.Value[i].Neg()
		}
	}
	return res
}

func (p *Bpoly) Mul(other Bpoly) Bpoly {
	resLen := len(p.Value) + len(other.Value) - 1
	res := Bpoly{Value: make([]Belt, resLen)}
	for i := range res.Value {
		res.Value[i] = BELT_ZERO
	}

	if p.IsZero() || other.IsZero() {
		return res
	}

	for i := 0; i < len(p.Value); i++ {
		if p.Value[i].IsZero() {
			continue
		}
		for j := 0; j < len(other.Value); j++ {
			res.Value[i+j] = res.Value[i+j].Add(p.Value[i].Mul(other.Value[j]))
		}
	}
	return res
}

func (p *Bpoly) ScalarMul(scalar Belt, resLen int) Bpoly {
	res := Bpoly{Value: make([]Belt, resLen)}
	for i := range res.Value {
		res.Value[i] = p.Value[i].Mul(scalar)
	}
	return res
}

func Dvr(a Bpoly, b Bpoly) (Bpoly, Bpoly) {
	degA := a.Degree()
	degB := b.Degree()

	degQ := uint32(0)
	if degA >= degB {
		degQ = degA - degB
	}

	lenQ := degQ + 1
	lenR := degB + 1
	q := Bpoly{Value: make([]Belt, lenQ)}
	res := Bpoly{Value: make([]Belt, lenR)}

	for i := range q.Value {
		q.Value[i] = BELT_ZERO
	}
	for i := range res.Value {
		res.Value[i] = BELT_ZERO
	}
	if a.IsZero() {
		return q, res
	} else if b.IsZero() {
		panic("division by zero")
	}

	r := a
	i := degA
	degR := degA
	qIdx := degQ
	for degR >= degB {
		coeff := r.Value[i].Div(b.Value[degB])
		q.Value[qIdx] = coeff
		for k := 0; k <= int(degB); k++ {
			if k <= int(degA) && k < len(b.Value) && k <= int(i) {
				r.Value[i-uint32(k)] = r.Value[i-uint32(k)].Sub(coeff.Mul(b.Value[degB-uint32(k)]))
			}
		}
		if degR >= 1 {
			degR--
		}
		if qIdx >= 1 {
			qIdx--
		}
		if degR == 0 && r.Value[0].IsZero() {
			break
		}
		i--
	}

	rLen := int(degR) + 1
	for i := 0; i < rLen; i++ {
		res.Value[i] = r.Value[i]
	}
	return q, res
}

func Egcd(a Bpoly, b Bpoly) (Bpoly, Bpoly, Bpoly) {
	m1u := Bpoly{Value: []Belt{BELT_ZERO}}
	m2u := Bpoly{Value: []Belt{BELT_ONE}}
	m1v := Bpoly{Value: []Belt{BELT_ONE}}
	m2v := Bpoly{Value: []Belt{BELT_ZERO}}

	// length of d is at most min(len a, len b) + 1
	dLen := min(len(a.Value), len(b.Value)) + 1
	// length of u is at most deg(b)
	uLen := b.Degree()
	// length of u is at most deg(a)
	vLen := a.Degree()

	d := Bpoly{Value: make([]Belt, dLen)}
	u := Bpoly{Value: make([]Belt, uLen)}
	v := Bpoly{Value: make([]Belt, vLen)}

	for i := range d.Value {
		d.Value[i] = BELT_ZERO
	}
	for i := range u.Value {
		u.Value[i] = BELT_ZERO
	}
	for i := range v.Value {
		v.Value[i] = BELT_ZERO
	}

	aCopy := a
	bCopy := b

	for !bCopy.IsZero() {
		degQ := uint32(0)
		if aCopy.Degree() >= bCopy.Degree() {
			degQ = aCopy.Degree() - bCopy.Degree()
		}
		qLen := degQ + 1
		rLen := bCopy.Degree() + 1
		q := Bpoly{Value: make([]Belt, qLen)}
		r := Bpoly{Value: make([]Belt, rLen)}
		for i := range q.Value {
			q.Value[i] = BELT_ZERO
		}
		for i := range r.Value {
			r.Value[i] = BELT_ZERO
		}

		q, r = Dvr(aCopy, bCopy)
		aCopy = bCopy
		bCopy = r

		res1 := q.Mul(m1u)
		res2 := m2u.Sub(res1)

		m2u = m1u
		m1u = res2

		res1 = q.Mul(m1v)
		res3 := m2v.Sub(res1)

		m2v = m1v
		m1v = res3
	}

	d.Value = aCopy.Value
	u.Value = m2u.Value
	v.Value = m2v.Value
	return d, u, v
}