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

в 18:23, , рубрики: scala, абстрактная алгебра, конечные поля, математика, теория чисел

Введение

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

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

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

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

Реализация

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

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

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

  1. если требуемый порядок deg равен 1, то просто возвратить готовый список неприводимых полиномов степени 1
  2. в случае, когда требуемый порядок более 1:
    1. сгенерировать все полиномы порядка deg (пусть P множество этих полиномов)
    2. находим список неприводимых полиномов степени Поле Галуа на Scala - 3 (пусть G множество этих неприводимых полиномов)
    3. если полином Поле Галуа на Scala - 4 не делится без остатка ни на один полином Поле Галуа на Scala - 5, то он является неприводимым, значит нужно добавить Поле Галуа на Scala - 6 в результирующий список полиномов-модулей
    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'е

Автор: mathsatan

Источник

Поделиться

* - обязательные к заполнению поля