Дискретная математика. Ерош И.Л - 125 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

125
В вычислениях понижение степеней производится с использовани
ем равенства a
2
= a + 1. Например: (2a + 1)(a+ 2) = 2a
2
+ a+ 4a+ 2 =
= 2(a + 1) + 5a + 2 = 7a + 4 = a + 1.
Элемент b ¹ 0 поля F(p
h
) называется образующей F
*
(p
h
) мульти
пликативной группы ненулевых элементов поля F(p
h
), если степе
ни b
i
, i = 1, 2, 3,..., p
h
– 1 пробегают все ненулевые элементы поля
F(p
h
). Образующая может рассматриваться как основание log. Та
кие логарифмы называются дискретными логарифмами. Рассмот
рим, например, все 8 степеней (кроме нулевой) корня a в приведен
ном выше примере и запишем результат в виде таблицы:
i
12345678
a
i
aa1+
2a 1+22a 2a 2+
a 2+
1
Из таблицы видно, что a является образующей. Эта таблица может
быть представлена как таблица дискретных логарифмов. Для этого в
верхней строке запишем упорядоченные элементы поля, а в нижней –
значения степеней образующего элемента, при которых получаем дан
ный элемент поля:
y
12
a+a 1 +a 2
2a 2 +a 12 +a 2
gol
a
y 84127536
Считается, что вычисление дискретных логарифмов является
трудной задачей, как и задача факторизации (разложения на мно
жители), что является существенным в криптосистемах с открытым
распределением ключей. Таблица логарифмов может использовать
ся для выполнения умножения и деления элементов поля. Заметим,
что операции выполняются по модулю p
h
– 1, в данном примере – по
модулю 3
2
– 1 = 8.
Для примера: log ((a + 2)(2a + 1)) = log(a + 2) + log(2a + 1) = 7 + 3 =
= 10 º 2 mod 8. Что соответствует элементу a + 1. log ((a + 1)/(2a +
+ 2)) = 2 – 6 = – 4 º 4 mod 8, что соответствует элементу 2.
Можно проверить, что кроме элемента a образующими b также яв
ляются элементы 2a + 1, a + 2 и 2a. Если s = p
h
– 1 есть наименьшая
положительная степень, удовлетворяющая уравнению b
s
=
1, то b яв
ляется образующей. Поэтому число образующих элементов поля рав
но j(p
h
–1), где j – функция Эйлера. Для нашего примера j(8) = 4.
Упражнения.
Найдите количество образующих элементов для полей Галуа:
F(3
4
), F(5
2
), F(7
2
), F(11
5
), F(13
4
).

Страницы