Основні поняття й ознаки теорії складності
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
Основні поняття й означення теорії складності
У теоретичній криптографії існує два основних підходи до визначення стійкості криптографічних систем і протоколів теоретично-інформаційний та теоретично-складносний.
Теоретично-інформаційний підхід передбачає, що супротивник, атакуючий криптографічну систему, не має навіть теоретичної можливості отримати інформацію, достатню для досягнення своїх цілей. Класичний приклад шифр Вернама з одноразовими ключами, абсолютно стійкий проти пасивного супротивника. Цей шифр є абсолютно надійним.
Нагадаємо, що шифр Вернама (одноразового блокноту) був винайдений в 1917 році Гілбертом Вернамом. У ньому була використана операція побітового додавання за модулем 2. Перед шифруванням повідомлення подають у двійковій формі. Ключем є будь-яке двійкове слово, однакової з довжини. Криптотекст отримують таким шляхом: . Розшифрування в шифрі одноразового блокноту збігається із шифруванням . Це зрозуміло, оскільки
Якщо супротивник не знає ключа , то з підслуханого криптотексту він абсолютно нічого не дізнається про повідомлення . Для супротивника усі ключі є рівноймовірними. Двійкове слово може бути криптотекстом для будь-якого іншого повідомлення , якщо б шифрування відбувалось з використанням якогось іншого ключа , а саме . Наприклад, запишемо слово „БАНАН” у двійковій формі: 000001 000000 010001 000000 010001.
Нехай ключем буде двійкова послідовність
.
Отримуємо криптотекст
.
Але такий самий криптотекст ми отримаємо, якщо зашифруємо повідомлення „ГРУША” ключем
.
Теорія складності є методикою аналізу обчислювальної складності різних криптографічних методів і алгоритмів. Вона порівнює криптографічні методи та алгоритми і визначає їх надійність. Теорія інформації стверджує можливість злому всіх криптографічних алгоритмів (окрім одноразових блокнотів). Теорія складності повідомляє, чи можна їх зламати до того, як настане теплова загибель Всесвіту.
Складність алгоритму визначається обчислювальними потужностями, необхідними для його виконання. Обчислювальну складність алгоритму часто визначають двома параметрами: Т (часова складність) та S (просторова складність або вимоги до памяті). Як Т так і S звичайно відображуються як функції від , де розмір вхідних даних (існують також інші міри складності: число випадкових бітів, наскільки широкий канал звязку, обєм даних тощо).
Обчислювальну складність алгоритму звичайно виражають через символ „О велике”, що вказує порядок величини обчислювальної складності. Це просто член розкладення функції складності, що найшвидше зростає за умови зростання ; всі члени нищого порядку ігноруються. Наприклад, якщо часова складність порядку , то вона виражається як .
Часова складність, виміряна подібним чином, не залежить від реалізації.
Не потрібно знати ні точного часу виконання окремих інструкцій, ні числа бітів, які являють різні змінні, ні навіть швидкості процесора. Один компютер може бути на 50% швидший від іншого, а в третього ширина шини даних може бути вдвічі більше, проте складність алгоритму, що оцінена порядком величини, не зміниться. І це не є хитрим трюком. Під час оцінки доволі складних алгоритмів усім іншим можна знехтувати (з точністю до постійного множника).
Оцінка обчислювальної складності наочно демонструє, як обєм вхідних даних впливає на вимоги до часу та обєму памяті.
Наприклад, якщо , подвоєння вхідних даних подвоїть і час виконання алгоритму. Якщо , додання лише одного біту до вхідних даних подвоїть час виконання алгоритму.
Головною ціллю теорії складності є забезпечення механізмів класифікації обчислювальних задач згідно з ресурсами, необхідних для їх розвязання. Класифікація не має залежати від конкретної обчислювальної моделі, а скоріше оцінювати внутрішню складність задачі.
Ресурси, що оцінюються, як уже було зазначено раніше, можуть бути такими: час, простір памяті, випадкові біти, кількість процесорів, тощо, але зазвичай головним фактором є час, а іноді й простір.
Теорія розглядає мінімальний час і обєм памяті для розвязання найскладнішого варіанта задачі на теоретичному компютері, відомому як машина Тьюринга. Машина Тьюрінга є кінцевим автоматом з безкінечною магнітною стрічкою памяті для читання/запису. Це означає, що машина Тьюрінга реалістична обчислювальна модель.
Задачі, які можна розвязати за допомогою алгоритмів з поліноміальним часом, називають такими, що можуть бути розвязані, оскільки за умов нормальних вхідних даних вони можуть бути розвязані за прийнятний час (точне визначення "прийнятності" залежить від конкретних умов).
Задачі, які можуть бути вирішені тільки за допомогою суперполіноміальних алгоритмів з поліноміальним часом, є обчислювально складними навіть за відносно малими значеннями .
Що ще гірше, Алан Тьюрінг доказав, що деякі задачі неможливо розвязати. Навіть без урахування часової складності алгоритму, створити алгоритм для їх розвязання неможливо.
Задачі можна розбити на класи у відповідності зі складністю їх розвязання. Найважливіші класи й очікувані співвідношення між ними показані на рис. 1.
Клас , що є найнижчим, містить усі задачі, які можна розвязати за поліноміальний час. До класу входять усі задачі, які можна розвязати за поліноміальний час