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

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

Типи і обмеження
Для початку слід обговорити технічні проблеми пов'язані з поданням поліномів в пам'яті, з урахуванням розмірів типу Int у мові Scala. Вимоги сформульовані у списку нижче.
  • Тип Int Scala/Java має розмір 32 біта
  • можна Використовувати біти: 0..30 — 31, оскільки 32-ий біт є знаковим
  • Поліноми мають бути представлені числами в діапозоні 0..29
  • Непріводімие поліноми (або модулі) мають діапозон 1..30
  • Кінцеве поле має елементів


Реалізація
Спочатку опишемо клас Поліноміальні, який реалізує поліном і 4 операції.
Цей вид полінома є «напівфабрикатом» і не прив'язаний до кінцевого поля.

class Polynomial(_p: Int) {
val поліноміальні: Int = _p

def order: Int = = {
...
}

def mul(p: Поліноміальні): Поліноміальні = {
...
}
def div(p: Поліноміальні): (Int, Int) = {
...
}
def add(p: Поліноміальні): Поліноміальні = {
...
}
def sub(p: Поліноміальні): Поліноміальні = {
...
}

override def toString: String = Integer.toBinaryString(this.поліноміальні)
}

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

abstract class FiniteField(_initBitNumber: Int) {
type T <: Поліноміальні
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 поліномів of degree d
    val n = 1 << deg
    for(i <- 0 until n){
    val t = i ^ n // поліноміальні 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: Поліноміальні = ...
    
    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.поліноміальні == other.p.поліноміальні
    case _ => false
    }
    
    override protected val p = Polynomial(_p)
    
    def this(other: GFPolynomial){
    this(other.p.поліноміальні, bits)
    }
    override def self: GFPolynomial = this
    
    override def +(other: GFPolynomial): GFPolynomial = {
    GFPolynomial(this.p.поліноміальні ^ other.p.поліноміальні, bits)
    }
    override def -(other: GFPolynomial): GFPolynomial = { // In this case add and subtract are the same
    this + other
    }
    
    override def *(other: GFPolynomial): GFPolynomial = {
    val result: Поліноміальні = this.p mul other.p
    if (result.order >= bits){
    GFPolynomial((result div modulo)._2, bits)
    }
    else GFPolynomial(result.поліноміальні, bits)
    }
    
    override def mulInverse: GFPolynomial = {
    if (p.поліноміальні == 0)
    throw new NoSuchElementException("Error: there is no multiplicative inverse for zero")
    var r1: Поліноміальні = Polynomial(modulo.поліноміальні)
    var r2: Поліноміальні = 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.поліноміальні > 0){
    val q: Поліноміальні = 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.поліноміальні, bits)
    }
    }
    }
    

    Результат множення може «вилізти» за межі поля, тому іноді треба ділити результат на модуль поля.
    Зауважте як реалізовано поділ, воно є множення a мультиплікативну інверсію b.
    У свою чергу інверсія знаходиться з допомогою розподілу, визначеного у класі Поліноміальні.
    Висновок
    Вийшла саморобна реалізація полів Галуа, яка в подальшому може бути поліпшена шляхом збільшення можливого розміру поля (замість Int використовувати довгу арифметику або що то в цьому роді).
    Дана стаття може бути корисний студентам і всім кому цікава тема абстрактної алгебри, полів і теорії кодування.
    Повний код програми можна знайти на githab'е
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.