Особенности вычислений в простых полях Галуа

Сложение

В результате вычислений искомый результат находится в пределах 0£ d < c.

Если (a+b)³c, то d приравнивается к остатку от целочисленного деления суммы (a+b) на c

Например:

1+1 mod 2 = 0;

3+5 mod 7 = 1;

4+4 mod 5 = 3.

Вычитание

В результате вычислений искомый результат находится в пределах 0£ d < c.

Если (a-b)<0, то к разности прибавляется c приравнивается к остатку от целочисленного деления суммы (a+b) на c

Например:

2–1 mod 3 = 1;

3–5 mod 7 = 5;

4–4 mod 5 = 0.

Умножение

В результате вычислений искомый результат находится в пределах 0£ d < c.

Если (a´b)³c, то d приравнивается к остатку от целочисленного деления произведения (a´b) на c

Например:

1´1 mod 2 = 1;

3´5 mod 7 = 1;

4´4 mod 8 = 0.

Деление

Операция деления определена как операция обратная умножению и существует только в полях Галуа

В результате вычислений искомый результат находится в пределах 0£ d < c.

Конструктивного алгоритма вычисления частного в простом поле не существует, поэтому деление выполняется методом перебора так:

В качестве первого множителя фиксируется число a;

Цикл по d = от 0 до (C-1)

Выполняется умножение в поле ;

Если произведение равно b то результат найден

Конец цикла.

Возведение в степень

В результате вычислений искомый результат находится в пределах 0£ d < c.

Если (a^b)³c, то d приравнивается к остатку от целочисленного деления результата (a^b) на c

Например:

2⁴ mod 7 = 2;

4³ mod 11 = 9;

5⁴ mod 9 = 4.

При возведении в степень область значений степенной функции в поле Галуа или над кольцом может быть меньше, чем область значений аргументов степенной функции

Извлечение дискретного логарифма

Операция дискретного логарифмирования определена как операция обратная возведению в степень. Найти обозначает найти такое число d, что при возведении a в эту степень получим число b.

В результате вычислений искомый результат находится в пределах 0£ d < c.

Конструктивного алгоритма вычисления логарифма в простом поле не существует, поэтому логарифмирование выполняется методом перебора так:

В качестве основания логарифма фиксируется число a;

Цикл по d = от 0 до (C-1)

Выполняется возведение в степень[1] ;

Если показательная функция равна b то результат найден

Конец цикла.

Следует отметить, что дискретный логарифм существует не всегда. Так например:

log₄9 mod 11 = 3;

log₄8 mod 11 – не существует потому что 4 в любой степени (от 0 до 10 по модулю 11) никогда не равно 8.