Введение в современную криптографию



Pdf көрінісі
бет227/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   223   224   225   226   227   228   229   230   ...   249
Криптография Катц

ТЕОРЕМА A.1 (Теорема биномиального разложения) Пусть x, y – дей-
ствительные целые числа n – положительное целое. Тогда
ПРЕДПОЛОЖЕНИЕ A.2 Для всех x ≥ 1 справедливо, что (1 − 1/x)x ≤ e−1.
ПРЕДПОЛОЖЕНИЕ A.3 Для всех x справедливо, что 1 − x ≤ e−x.
ПРЕДПОЛОЖЕНИЕ A.4 Для всех x при 0 ≤ x ≤ 1 справедливо, что
Асимптотическая запись
Мы используем стандартную запись для выражения асимптотического пове-
дения функций.
ОПРЕДЕЛЕНИЕ A.5 Пусть f (n), g(n) будут функциями из неотрицатель-
ных целых чисел , для неотрицательных действительных чисел. Тогда:
• f (n) = O(g(n)) означает, что существуют положительные целые числа c и 
nr, такие что для всех n > nr справедливо, что f (n) ≤ c • g(n).
• f (n) = Ω(g(n)) означает, что существуют положительные целые числа c и 
nr, такие, что для всех n > nr справедливо, что f (n) ≥ c • g(n).
• f (n) = Θ(g(n)) означает, что существуют положительные целые числа c1, 
c2 и nr такие, что для всех n > nr справедливо, что c1 • g(n) ≤ f (n) ≤ c2 • g(n).
• f (n) = o(g(n)) означает, что limn→∞ g(n) = 0.
• f (n) = ω(g(n)) означает, что limn→∞ g(n) = ∞.
Пример A.6
Пусть f (n) = n4 + 3n + 500. Тогда:
• f (n) = O(n4).


311
• f (n) = O(n5). На самом деле, f (n) = o(n5).
• f (n) = Ω(n3 log n). Фактически, f (n) = ω(n3 log n).
• f (n) = Θ(n4).

Основы теории вероятности
Мы предполагаем, что читатель знаком с основами теории вероятности на 
уровне, который рассматривается в типичном университетском курсе по дис-
кретной математике. Здесь мы просто напомним читателю о некоторых обозна-
чениях и основных фактах.
If E – это событие, то E¯ обозначает дополнение этого события; т.е., E¯ – это 
событие, которое E не происходит. По определению, Pr[E] = 1 − Pr[E¯]. Если 
E1 и E2 являются событиями, то E1 ^ E2 обозначает их конъюнкцию; т.е., E1 
^ E2 является таким событием, что происходит как E1, так и E2 . По определе-
нию, Pr[E1 v E2] ≤ Pr[E1]. События E1 и E2 называются независимыми, если 
Pr[E1v E2] = Pr[E1] • Pr[E2].
Если E1 и E2 – события, то E1 v E2 обозначает логическое сложение (дизъ-
юнкцию) E1 и E2; то есть, E1 v E2 – такое событие, при котором происходит или 
E1 или E2. Из определения следует, что Pr[E1 v E2] ≥ Pr[E1]. Граница объедине-
ния часто является очень полезной верхней границей этой величины.


Достарыңызбен бөлісу:
1   ...   223   224   225   226   227   228   229   230   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет