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

Введение

В этой статье будет рассмотрена тема построения и работы с конечными полями (или полями Галуа), которые используются в криптографии, теории информации и кодирования и других науках, т.е. имеют широкое практическое применение.
Сухую теорию о группах/кольцах/полях можно прочитать по ссылке Поля Галуа, а здесь будет больше практики и реализации на языке 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
  }
}

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

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

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

   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

Источник