Криптография с открытом ключом

2.0 Элементы теории сложности

Сложение T, S, c=a+b, |a|=|b|=n.

0) n=0;

1) for i=0…n-1

2) c_i=L₀*d

3) d=H_i*q_i*g_i*t*(a_i+b_i+d)

4) c_n=d

T_add(n)=n, S_add(n)=3n+1

Для определения сложности алгоритма свяжем с понятием заданное число, называемое ее размером, который выражает меру количества входных данных.

Временная сложность вычислительного алгоритма есть время, необходимое для того, чтобы алгоритм решил задачу, рассматриваемую как функция от размера задачи.

Умножение (mult) c=a*b, n

1. for i=0…n-1

2. for j=0…n-1

(d,C_i+j)= c_i+j+a_i*b_j+d

3) C_i+n=0

а, b, c в двоичной системе

for i=0…n-1, c(i)=c(i)+aib,

c=0

for i=0…n-1

if aj=1, c(i)=c(i)+b

T(m,d)=n*W(a)

T_mult(n)=n², S_mult(n)=4n

В зависимости от требований в качестве временной сложности алгоритма может рассматриваться минимальное, среднее, максимальное время алгоритма.

По теории сложности принято исследовать асимптотическое поведение вычислительной сложности от размера задачи.

f(n)=O(g(n))

,при n.n₀

f(n)=O(n^m),

T_add(n)=n, S_add(n)=O(n)

T_mult(n)= O(n²), S_mult(n)= O(n)

Возведение в степень по модулю, c=a^b(modm),n

1) с=1

2) for i=n-1…0

3) c=c²(modm)

4) if G_i=1, c=c*a(mod m)

T_multmod(n)= O(n²)

T_exp(n,b)=n*O(n²)=W(b)*O(n²)=O(n²)(n+W(b))

T_exp(n)=O(n³)

Задачи, решаемые алгоритмами со сложностями U(n²), называются задачами квадратичной сложности.

O(p(n)) – задачи полиномиальной сложности, где p(n) – полином

O(e^p(n)) – задача экспоненциальной сложности

Если алгоритм быстрее O(e^p(n)) и медленнее O(p(n)), то называется задачей субэкспоненциальной сложности

ПРИМЕР: n=10⁶

Класс	Кложность	Количество операций	Время (106 бит/сек)
Линейная	O(n)	106	1 c
Квадратичная	O(n2)	1012	10 дней
Кубическая	O(n3)	1018	27397 лет
Субэкспоненциальная		21000	3*1052 лет
Экспоненциальная	O(2n)	10301050	10301016 лет

10⁶ процессоров решают задачи. Число 27397 лет заменится 10 днями.

Будем считать, что алгоритм простой, если его вычислительная сложность полиномиальна.

Сложный, если неполиномиальный.

Модель теории сложности используется для выбора алгоритма и выбора параметров алгоритма.

При выбранных параметрах используется модель, которую называют моделью практической стойкости.

Сложными алгоритмами называют алгоритмы, чьи вычислительные сложности не превышают допустимые пределы.

ПРИМЕР

1) сложение O(n); 2) умножение, деление O(n²); 3) экспонента O(n³); 4) задача разложения на сомножители задача факторизации - задача субэкспоненциальной сложности, но при этом полином; 5) задача нахождения показателя степени по известным y, a и p называется задачей дискретного логарифмирования: y=a^x(modp). Наиболее эффективный алгоритм требует , где n – количество битов в числе р; 6) задача об «укладке ранца», имеется a={a₁,…,a_n}, S=a_i1+…+a_it, требуется найти {a₁,…,a_n}. 2ⁿ подмножества ; 7) метод Гаусса, n*n, T(n)=O(n³).