Математические основы криптологии. Галуев Г.А. - 12 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

23
надлежащей классу
NP, то NP=PSPACE, или если эта задача
окажется в
P, то PSPACE=P.
Таким образом, выбор наиболее сложных задач, для кото-
рых известно решение, и использование их в основе построения
криптосистемы, позволяет создавать практически устойчивые
шифры, раскрытие которых в принципе возможно, но для этого
потребуется столько времени, что эта процедура дешифрования
теряет практический смысл. Более подробно об этом речь пойдет
на следующих лекциях.
Задача выполнимости заключается в проверке существо-
вания выполняющего набора булевых переменных
V
1
,…,V
an
для
набора дизъюнкций (операция «или») над этим множеством эле-
ментов.
24
3. Элементы теории чисел: основные понятия и
теоремы.
В дальнейшем изложении будем использовать следующие
понятия и обозначения:
N - множество натуральных чисел: целые положительные
числа вида 1,2,…
Z - множество целых чисел: числа вида n, -n и 0, где n - на-
туральное число.
Q - множество рациональных чисел: числа вида p/q, где p и
q - целые числа и
0
≠
q
. Класс рациональных чисел включает в
себя все целые числа Z, которые в свою очередь включают в се-
бя все натуральные числа
N.
R - множество действительных чисел: этот класс включает
все рациональные числа и все числа не являющиеся таковыми
т.е. все иррациональные числа.
Рассмотрим
множество целых чисел, которые обозначим
через
Z. На множестве целых чисел рассмотрим операции сло-
жения + и умножения
×
. Операция деления, обратная операции
умножения, выполняется не для всех пар чисел из
Z. (Напомним
Z - целые числа).
Число
а делится на число b
≠
0, если существует число q
такое, что
bqaилиq
b
a
==
В этом случае говорят, что число
b делит число a.
При этом число
b - делитель числа а, число а - кратное
числа
b, число q - частное от деления а на b. Число 0 делится
на любое целое
0
≠
b
. Если
0
≠
a
, то очевидно, что множество
всех делителей числа
а конечно.
Утверждение о том, что
b делит а обозначают символом
ab/
. Если b не делит а, то этот факт обозначают ab/ .
Лемма 1. Если bc / и ab/ , то ac / .
Доказательство: по определению из bc / и ab/ имеем,

Страницы