Дискретная математика. Математические вопросы криптографии. Ерош И.Л. - 26 стр.

UptoLike

ВУЗ: 

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

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

Рубрика: 

26
на P(x). Все p
h
элементов поля F(p
h
) могут быть представлены
в виде
∑ c
j
α
i
,
где 0 ≤ c
j
≤ p–1; 0 ≤ i ≤ h–1.
При вычислениях степень α
s
, где s ≥ h заменяется на меньшую в
соответствии с уравнением P(α) = 0.
Пусть, например, p = 3 , h = 2 и α удовлетворяет уравнению x
2
– x – 1 =
= 0. Элементы поля F(3
2
) можно выразить как:
0, 1, 2, α, α + 1, α+ 2, 2α, 2α + 1, 2α + 2.
В вычислениях понижение степеней производится с использованием
равенства α
2
= α + 1. Например, (2α + 1)(α+ 2) = 2α
2
+ α+ 4α+ 2 = 2(α+
+ 1) + 5α + 2 = 7α + 4 = α + 1.
Элемент β ≠ 0 поля F(p
h
) называется образующей F⋅(p
h
) мультипли-
кативной группы ненулевых элементов поля F(p
h
), если степени β
i
, i =
=1, 2, 3, ..., p
h
– 1 пробегают все ненулевые элементы поля F(p
h
). Обра-
зующая может рассматриваться как основание log. Такие логарифмы
называются дискретными логарифмами. Рассмотрим, например, все 8
степеней корня α в приведенном примере и запишем результат в виде
таблицы:
E !" #$% &
α
E
αα+
+α α α+
α+
Из таблицы видно, что α является образующей. Эта таблица может
быть представлена как таблица дискретных логарифмов. Для этого в
верхней строке запишем упорядоченные элементы поля, а в нижней –
значения степеней образующего элемента, при которых получаем дан-
ный элемент поля:
O 12
αα+1 α+2
2α 2α+12 +α 2
gol
α
O
84
1275
3
6
Считается, что вычисление дискретных логарифмов является труд-
ной задачей, как и задача факторизации (разложения на множители).
Таблица логарифмов может использоваться для выполнения умноже-
ния и деления элементов поля. Заметим, что операции выполняются по
модулю p
h
– 1, в данном примере по модулю 3
2
– 1 = 8. Для примера:

Страницы