Поле Галуа на Scala

Введение


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

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


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


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

Реализация


Сначала опишем класс 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
  }
}

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


Алгоритм следующий:
  1. если требуемый порядок deg равен 1, то просто возвратить готовый список неприводимых полиномов степени 1
  2. в случае, когда требуемый порядок более 1:
    1. сгенерировать все полиномы порядка deg (пусть P множество этих полиномов)
    2. находим список неприводимых полиномов степени aae33dd145b30b627dae495137cda206.gif (пусть G множество этих неприводимых полиномов)
    3. если полином 7f40ebf5361c2e7d3074b1bb9001787c.gif не делится без остатка ни на один полином 07969c7332bd9d8b2869d69e411663c8.gif, то он является неприводимым, значит нужно добавить 7f40ebf5361c2e7d3074b1bb9001787c.gif в результирующий список полиномов-модулей


    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’е

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

© Habrahabr.ru