Введение
В этой статье будет рассмотрена тема построения и работы с конечными полями (или полями Галуа), которые используются в криптографии, теории информации и кодирования и других науках, т.е. имеют широкое практическое применение.
Сухую теорию о группах/кольцах/полях можно прочитать по ссылке Поля Галуа, а здесь будет больше практики и реализации на языке Scala.
Типы и ограничения
Для начала следует обсудить технические проблемы связанные с представлением полиномов в памяти, с учетом размеров типа Int в языке Scala. Требования сформулированы в списке ниже.
- Тип Int в Scala/Java имеет размер 32 бита
- Использовать можно биты: 0..30 — 31, поскольку 32-ой бит является знаковым
- Полиномы должны быть представлены числами в диапозоне 0..29
- Неприводимые полиномы (или модули) имеют диапозон 1..30
- Конечное поле имеет
элементов
Реализация
Сначала опишем класс Polynomial, который реализует полином и 4 операции.
Этот вид полинома является «полуфабрикатом» и не привязан к конечному полю.
Читать дальше →
Поле Галуа на Scala
Source: habrahabr