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