Составители:
1. Все элементы поля Галуа имеют конечный размер, деление
элементов не имеет каких-либо ошибок округления.
2. Сложение и вычитание элементов поля GF(2
n
) не требует деления
на модуль.
3. Алгоритмы вычислений в поле GF(2
n
) допускают параллельную
реализацию.
4. Для поля GF(2
n
) обычно применяют в качестве модуля трёхчлен
P(x
n
) = x
n
+ x + 1.
Кроме того, длинная строка нулей между коэффициентами при x
n
и x
обеспечивает более простую реализацию быстрого умножения (с
приведением по модулю). Трёхчлен P(x
n
) должен быть неприводимым и
примитивным.
Трёхчлен P(x
n
) = x
n
+ x + 1 является примитивным для следующих
значений n (n < 1000):
1, 3, 4, 6, 9, 15, 22, 28, 30, 46, 60, 63, 127, 153, 172, 303, 471, 532, 865, 900.
Вычисления в GF(2
n
) можно быстро реализовать аппаратно с помощью
регистров сдвига с линейной обратной связью. По этой причине
вычисления над GF(2
n
) часто выполняются быстрее, чем вычисления
над GF(p).
П.5. Образующие
Если p – простое число и g меньше, чем p, то g называется
образующей по модулю p, если для каждого числа a от 1 до p - 1
существует такое число x, g
x
≡ a (mod p).
Иногда g называют также примитивным корнем по модулю p.
Например [22], если p = 11, то 2 – это образующая по модулю 11:
2
10
= 1024 ≡ 1(mod 11); 2
1
= 2 ≡ 2(mod 11); 2
8
= 256 ≡ 3(mod 11);
2
2
=4 ≡ 4(mod 11); 2
4
=16 ≡ 5(mod 11); 2
9
= 512 ≡ 6(mod 11);
2
7
= 128 ≡ 7(mod 11); 2
3
=8 ≡ 8(mod 11); 2
6
= 64 ≡ 9(mod 11);
2
5
= 32 ≡ 10(mod 11).
163
Страницы
- « первая
- ‹ предыдущая
- …
- 159
- 160
- 161
- 162
- 163
- …
- следующая ›
- последняя »
