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

UptoLike

ВУЗ: 

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

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

Рубрика: 

27
log ((α + 2)(2α + 1))= log(α + 2) + log(2α + 1) = 7 + 3 = 10 ≡ 2 mod 8.
Что соответствует элементу α + 1.
log ((α + 1)/( 2α + 2)) = 2 – 6 = – 4 ≡ 4 mod 8, что соответствует
элементу 2.
Можно проверить, что кроме элемента α образующими также явля-
ются элементы 2α + 1, α + 2 и 2α. Если s = p
h
– 1 есть наименьшая
положительная степень, удовлетворяющая уравнению β
s
= 1, то β явля-
ется образующей. Поэтому число образующих элементов поля равно
ϕ(p
h
–1), где ϕ – функция Эйлера. Для нашего примера ϕ (8) = 4.
Рассмотрим вспомогательную задачу. Пусть имеется рюкзачный
вектор A = (a
1
a
2
a
3
...a
i
... a
n
). Рассмотрим различные суммы элемен-
тов, состоящие из h компонент. Задача состоит в том, чтобы для задан-
ных n и h построить вектор A такой, чтобы все суммы из h элементов
были бы попарно различны. Для рюкзаков низкой плотности это сде-
лать легко: a
i
= h
i–1
, 1 ≤ i ≤ n. Например,
A = (1 2 4 8 16 32 64), h = 2, n = 7;
A = (1 3 9 27 81 243 729 2187 6561), h = 3, n = 9.
Легко проверяется, что любые пары в первом векторе различны и
любые тройки во втором также различны.
Такое построение векторов A соответствует рюкзакам низкой плот-
ности, так как они являются сверхрастущими.
Пусть n = p – простое число. Показано, что для простого p и целого
h ≥ 2 всегда можно построить рюкзачный вектор A = (a
1
a
2
a
3
...a
i
... a
P
),
удовлетворяющий следующим условиям:
a) 1 ≤ a
i
≤ p
h
–1, для 1 ≤ i ≤ p.
б) Если x
i
и y
i
– неотрицательные целые числа, такие, что (x
1
, x
2
, ...,
x
p
) ≠ (y
1
, y
2
, ..., y
p
), но ∑x
i
= ∑y
i
= h, тогда
∑ x
i
a
i
≠ ∑ y
i
a
i
(*)
При построении вектора A можно взять a
i
= log
g
(α + i–1), 1 ≤ i ≤ p,
где α– корень неприводимого многочлена; g – образующая группы F⋅(p
h
).
Аналогичное построение может быть выполнено для n = p
s
, где p –
простое; s – целое. Кроме того, неравенство (*) может быть заменено
на более сильное:
∑x
i
a
i
≡
∑y
i
a
i
mod (p
h
–1).
При построении криптосистемы исходный текст должен состоять из
p-разрядных блоков, в каждом из которых сумма элементов равняется
h. Для того чтобы обеспечить это условие, необходимо после кодирова-

Страницы