ガロア拡大体における加算

gistfile1.scala

class GaloisField private (val gf_index: Int) {
  private val gf_bit: Int =
    if (gf_index == 4) (1 << 1) | 1
    else if (gf_index == 8) (1 << 4) | (1 << 3) | (1 << 2) | 1
    else sys.error("undefined")

  private val pow_table = Array.fill(256)(0)
  private val root_table = Array.fill(256)(0)

  locally {
    val max = math.pow(2, gf_index).toInt
    var element = 1
    val upper_bit = max / 2 // 10000000
    val mask = max - 1 // 11111111

    for (i <- 0 until max) {
      pow_table(i) = element
      // because 255 = 0 
      if (i != max - 1)
        root_table(element) = i

      element = (if ((element & upper_bit) != 0) gf_bit else 0) ^ ((element << 1) & mask)
    }
    root_table(0) = -1 //infnity
  }

  def pow(x: Int) = pow_table(x)

  def root(r: Int) =
    if(r == 0)
      throw new IllegalArgumentException
    else
      root_table(r)
}


object GaloisField {
  val a4 = new GaloisField(4)
  val a8 = new GaloisField(8)

  def test = {
    println("a^15 + a^10 = a^" + a8.root(a8.pow(15) ^ a8.pow(10)))
  }
}