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

UptoLike

ВУЗ: 

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

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

Рубрика: 

137
Из п. 6.1.10 следует, что если e – показатель числа 2 по модулю A,
то число A порождает арифметический код длины n = e, исправляю
щий одиночные ошибки. Совершенный арифметический код, исправ
ляющий одиночные ошибки, может быть получен, если 2 является при
митивным корнем по модулю A, причем A в этом случае должен являть
ся простым числом.
Могут быть построены арифметические коды, исправляющие ошиб
ки более высокой кратности, однако их анализ затруднителен. Так,
для того, чтобы число A порождало код, исправляющий арифметичес
кие ошибки кратности t длины n, необходимо и достаточно, чтобы не
выполнялось сравнение
2
s
1
±2
s
2
…±2
s
t
º 2
k
1
±2
k
2
…±2
k
t
mod A, (6.4)
где все s
1
, s
2
, … s
t
, k
1
, k
2
, … k
t
– различные числа в диапазоне от 0 до
n–1.
Единственным результатом, который позволяет строить длинные
арифметические коды с большим кодовым расстоянием, удовлетворя
ющие условию (6.4), является набор теорем, доказанных И. Л. Еро
шем и С. Л. Ерошем в 1968 г. [6].
Примеры. Определите длины арифметических кодов, исправляю
щих одиночные ошибки, порождаемых числами A = 7, 9 11, 19, 23,
25, 27, 29.
6.3. Задачи для контрольной
1. Решите сравнение (19·10
153
+ 37·12
28
): (13·9) = 3X+13
2
mod 11.
2. Криптосистема с идеальной секретностью по Шеннону.
3. Проверьте формулу Эйлера для чисел m = 33, a = 5.
4. Решите сравнение (38·12
250
+23· 11
25
): (18·19) = 5X – 10 mod 13.
5. Криптосистема RSA. Примеры.
6. Решите сравнение (25·16
251
+ 11·15
25
): (8·29) = 12 + 3X mod 17.
7. Теорема Ферма. Примеры.
8. Формирование общего ключа (по Диффи и Хэллману). Примеры.
9. Решите сравнение (32·14
156
+ 18·12
218
): (23·29) = 25 + 3X mod 13.
10. Проверьте форму Эйлера для чисел m = 45, a = 4.
11. Найдите функцию Эйлера для чисел 215, 360, 2553.
12. Решите сравнение (16·17
21
+ 57·18
25
): (8·29) = 43X mod 19.
13. Решите сравнение (38·10
153
+ 66·12
28
): (13·9) = 13X mod 11.
14. Проверьте формулу Эйлера для чисел m = 63, a = 4.
15. Решите сравнение (42·12
250
+ 75·11
25
): (18·19) = 8X mod 13.
16. Решите сравнение (19·16
251
+ 18·15
25
): (8·29) = 5X mod 17.
17. Решите сравнение (22·14
156
+ 31·12
218
): (23·29) = 3X mod 13.

Страницы