power.go raw

   1  package mlsbset
   2  
   3  import "fmt"
   4  
   5  // Power is a valid exponent produced by the MLSBSet encoding algorithm.
   6  type Power struct {
   7  	set Encoder // parameters of code.
   8  	s   []int32 // set of signs.
   9  	b   []int32 // set of digits.
  10  	c   int     // carry is {0,1}.
  11  }
  12  
  13  // Exp is calculates x^k, where x is a predetermined element of a group G.
  14  func (p *Power) Exp(G Group) EltG {
  15  	a, b := G.Identity(), G.NewEltP()
  16  	for e := int(p.set.p.E - 1); e >= 0; e-- {
  17  		G.Sqr(a)
  18  		for v := uint(0); v < p.set.p.V; v++ {
  19  			sgnElt, idElt := p.Digit(v, uint(e))
  20  			G.Lookup(b, v, sgnElt, idElt)
  21  			G.Mul(a, b)
  22  		}
  23  	}
  24  	if p.set.IsExtended() && p.c == 1 {
  25  		G.Mul(a, G.ExtendedEltP())
  26  	}
  27  	return a
  28  }
  29  
  30  // Digit returns the (v,e)-th digit and its sign.
  31  func (p *Power) Digit(v, e uint) (sgn, dig int32) {
  32  	sgn = p.bit(0, v, e)
  33  	dig = 0
  34  	for i := p.set.p.W - 1; i > 0; i-- {
  35  		dig = 2*dig + p.bit(i, v, e)
  36  	}
  37  	mask := dig >> 31
  38  	dig = (dig + mask) ^ mask
  39  	return sgn, dig
  40  }
  41  
  42  // bit returns the (w,v,e)-th bit of the code.
  43  func (p *Power) bit(w, v, e uint) int32 {
  44  	if !(w < p.set.p.W &&
  45  		v < p.set.p.V &&
  46  		e < p.set.p.E) {
  47  		panic(fmt.Errorf("indexes outside (%v,%v,%v)", w, v, e))
  48  	}
  49  	if w == 0 {
  50  		return p.s[p.set.p.E*v+e]
  51  	}
  52  	return p.b[p.set.p.D*(w-1)+p.set.p.E*v+e]
  53  }
  54  
  55  func (p *Power) String() string {
  56  	dig := ""
  57  	for j := uint(0); j < p.set.p.V; j++ {
  58  		for i := uint(0); i < p.set.p.E; i++ {
  59  			s, d := p.Digit(j, i)
  60  			dig += fmt.Sprintf("(%2v,%2v) = %+2v %+2v\n", j, i, s, d)
  61  		}
  62  	}
  63  	return fmt.Sprintf("len: %v\ncarry: %v\ndigits:\n%v", len(p.b)+len(p.s), p.c, dig)
  64  }
  65