Поле Галуа на Scala07.01.2017 01:33

Введение

В этой статье будет рассмотрена тема построения и работы с конечными полями (или полями Галуа), которые используются в криптографии, теории информации и кодирования и других науках, т.е. имеют широкое практическое применение.
Сухую теорию о группах/кольцах/полях можно прочитать по ссылке Поля Галуа, а здесь будет больше практики и реализации на языке Scala.

Типы и ограничения

Для начала следует обсудить технические проблемы связанные с представлением полиномов в памяти, с учетом размеров типа Int в языке Scala. Требования сформулированы в списке ниже.

Тип Int в Scala/Java имеет размер 32 бита
Использовать можно биты: 0…30 — 31, поскольку 32-ой бит является знаковым
Полиномы должны быть представлены числами в диапозоне 0…29
Неприводимые полиномы (или модули) имеют диапозон 1…30
Конечное поле имеет элементов

Реализация

Сначала опишем класс Polynomial, который реализует полином и 4 операции.
Этот вид полинома является «полуфабрикатом» и не привязан к конечному полю.

class Polynomial(_p: Int) {
  val polynomial: Int = _p

  def order: Int =  = {
    ...
  }

  def mul(p: Polynomial): Polynomial = {
    ...
  }
  def div(p: Polynomial): (Int, Int)  = {
    ...
  }
  def add(p: Polynomial): Polynomial = {
    ...
  }
  def sub(p: Polynomial): Polynomial = {
    ...
  }

  override def toString: String = Integer.toBinaryString(this.polynomial)
}

Далее абстрактный класс FiniteField, который будет родителем полей Галуа
Внутри FiniteField содержится внутренний класс FiniteFieldPolynomial, такая структура позволяет обеспечить безопасность при проведении операций.
Безопасность заключается в том, что операции возможно производить только с полиномами из одного поля.
Обратите внимание на член modulo, это модуль (или же неприводимый полином) степени поля.

abstract class FiniteField(_initBitNumber: Int) {
  type T <: Polynomial
  type GFPolynomial <: FiniteFieldPolynomial

  protected val checkBitNumber: Int => Int = ???
  val modulo: T
  val bits: Int = checkBitNumber(_initBitNumber)

  protected def createModulo(): Option[Int]
  def createPolynomial(_initPolynomial: Int): FiniteFieldPolynomial

  abstract class FiniteFieldPolynomial {

    protected val p: T
    def +(other: GFPolynomial): GFPolynomial
    def -(other: GFPolynomial): GFPolynomial = {
      this + other
    }
    def *(other: GFPolynomial): GFPolynomial
    def /(other: GFPolynomial): GFPolynomial = this * other.mulInverse
    def addInverse: GFPolynomial = self
    def mulInverse: GFPolynomial
    def self: GFPolynomial
  }
}

Важным этапом построения поля Галуа есть вычисление неприводимых полиномов степени поля, а так же выбор одного из них. С математикой данного процесса можно ознакомиться по ссылке Неприводимые полиномы.
Неприводимый полином будет использоваться для операций умножения и деления, точно так же как простое число для числового поля .
Иными словами, неприводимыые полиномы играют ту же роль во множествах полиномов, что и простые числа во множествах целых чисел.
Упрощенный код для нахождения множества неприводимых полиномов представлен ниже.

Алгоритм следующий:

если требуемый порядок deg равен 1, то просто возвратить готовый список неприводимых полиномов степени 1

в случае, когда требуемый порядок более 1:

сгенерировать все полиномы порядка deg (пусть P множество этих полиномов)
находим список неприводимых полиномов степени (пусть G множество этих неприводимых полиномов)
если полином не делится без остатка ни на один полином , то он является неприводимым, значит нужно добавить в результирующий список полиномов-модулей

object IrreduciblePolynomials{

	private def check(p: Int, list: List[Int]): Boolean = {
		val pol = Polynomial(p)
		list.foreach((item: Int) => {
			val i = Polynomial(item)
			if ((pol div i)._2 == 0){
				return false
			}
		})
		true
	}

	def calcIrreducible(deg :Int): List[Int] = {
		if (deg == 1) return List[Int](2, 3)
		// d > 2
		var resultList = ListBuffer[Int]()
		// generate all polynomials of degree d
		val n = 1 << deg
		for(i <- 0 until n){
			val t = i ^ n		// polynomial of P set, for testing
			val list: List[Int] = calcIrreducible(deg >> 1)
			if (check(t, list)) resultList += t
		}
		resultList.toList
	}
}

Осталось реализовать конкретный класс-наследник FiniteField, который будет готовым конечным полем.

class GaloisField(_initBitNumber: Int = FiniteField.DEFAULT_BIT_NUMBER) extends FiniteField(_initBitNumber) {
  override val modulo: Polynomial = ...

  protected def createModulo(): Option[Int] = {
    val list = IrreduciblePolynomials(this.bits)
    list.headOption
  }

  def createPolynomial(_initPolynomial: Int): GFPolynomial = {
    ...
  }
  def createPolynomial(_binInitPolynomial: String): GFPolynomial = {
    ...
  }

  class GFPolynomial private[GaloisField](_p: Int, _m: Int) extends FiniteFieldPolynomial with Comparable[GFPolynomial]{
    override def equals(other: Any): Boolean = other match {
      case other: GFPolynomial => this.p.polynomial == other.p.polynomial
      case _ => false
    }

    override protected val p = Polynomial(_p)
	
    def this(other: GFPolynomial){
      this(other.p.polynomial, bits)
    }
    override def self: GFPolynomial = this

    override def +(other: GFPolynomial): GFPolynomial = {
      GFPolynomial(this.p.polynomial ^ other.p.polynomial, bits)
    }
    override def -(other: GFPolynomial): GFPolynomial = {  // In this case add and subtract are the same
      this + other
    }

    override def *(other: GFPolynomial): GFPolynomial = {
      val result: Polynomial = this.p mul other.p
      if (result.order >= bits){
        GFPolynomial((result div modulo)._2, bits)
      }
      else GFPolynomial(result.polynomial, bits)
    }

    override def mulInverse: GFPolynomial = {
      if (p.polynomial == 0)
        throw new NoSuchElementException("Error: there is no multiplicative inverse for zero")
      var r1: Polynomial = Polynomial(modulo.polynomial)
      var r2: Polynomial = this.p
      var s1 = Polynomial(1)
      var s2 = Polynomial(0)
      var t1 = Polynomial(0)
      var t2 = Polynomial(1)
      var t = Polynomial(0)
      var s = Polynomial(0)
      var r = Polynomial(0)
      while(r2.polynomial > 0){
        val q: Polynomial = Polynomial((r1 div r2)._1)
        r = r1 sub (q mul r2)
        r1 = r2; r2 = r
        s = s1 sub (q mul s2); s1 = s2; s2 = s
        t = t1 sub (q mul t2); t1 = t2; t2 = t
      }
      GFPolynomial(t1.polynomial, bits)
    }
  }
}

Результат умножения может «вылезти» за рамки поля, поэтому иногда надо делить результат на модуль поля.
Заметьте как реализовано деление, оно есть умножение a на мультипликативную инверсию b.
В свою очередь инверсия находится с помощью деления, определенного в классе Polynomial.

Вывод

Получилась самодельная реализация полей Галуа, которая в дальнейшем может быть улучшена путем увеличения возможного размера поля (вместо Int использовать длинную арифметику или что то в этом роде).
Данная статья может быть полезен студентам и всем кому интересна тема абстрактной алгебры, полей и теории кодирования.
Полный код приложения можно найти на githab’е

Поле Галуа на Scala07.01.2017 01:33

Введение

Типы и ограничения

Реализация

Вывод

Комментарии (0)