galoisfield.go raw

   1  package utils
   2  
   3  // GaloisField encapsulates galois field arithmetics
   4  type GaloisField struct {
   5  	Size    int
   6  	Base    int
   7  	ALogTbl []int
   8  	LogTbl  []int
   9  }
  10  
  11  // NewGaloisField creates a new galois field
  12  func NewGaloisField(pp, fieldSize, b int) *GaloisField {
  13  	result := new(GaloisField)
  14  
  15  	result.Size = fieldSize
  16  	result.Base = b
  17  	result.ALogTbl = make([]int, fieldSize)
  18  	result.LogTbl = make([]int, fieldSize)
  19  
  20  	x := 1
  21  	for i := 0; i < fieldSize; i++ {
  22  		result.ALogTbl[i] = x
  23  		x = x * 2
  24  		if x >= fieldSize {
  25  			x = (x ^ pp) & (fieldSize - 1)
  26  		}
  27  	}
  28  
  29  	for i := 0; i < fieldSize; i++ {
  30  		result.LogTbl[result.ALogTbl[i]] = int(i)
  31  	}
  32  
  33  	return result
  34  }
  35  
  36  func (gf *GaloisField) Zero() *GFPoly {
  37  	return NewGFPoly(gf, []int{0})
  38  }
  39  
  40  // AddOrSub add or substract two numbers
  41  func (gf *GaloisField) AddOrSub(a, b int) int {
  42  	return a ^ b
  43  }
  44  
  45  // Multiply multiplys two numbers
  46  func (gf *GaloisField) Multiply(a, b int) int {
  47  	if a == 0 || b == 0 {
  48  		return 0
  49  	}
  50  	return gf.ALogTbl[(gf.LogTbl[a]+gf.LogTbl[b])%(gf.Size-1)]
  51  }
  52  
  53  // Divide divides two numbers
  54  func (gf *GaloisField) Divide(a, b int) int {
  55  	if b == 0 {
  56  		panic("divide by zero")
  57  	} else if a == 0 {
  58  		return 0
  59  	}
  60  	return gf.ALogTbl[(gf.LogTbl[a]-gf.LogTbl[b])%(gf.Size-1)]
  61  }
  62  
  63  func (gf *GaloisField) Invers(num int) int {
  64  	return gf.ALogTbl[(gf.Size-1)-gf.LogTbl[num]]
  65  }
  66