Наступним в ієрархії складності йде клас PSPACE. Проблеми класу PSPACE можуть бути вирішені в поліноміальному просторі, але не обов'язково за поліноміальний час. PSPACE включає NP, але ряд проблем PSPACE здаються складнішими, ніж NP. Звичайно, і це поки не доведено. Існує клас проблем, так званих PSPACE-повних, що володіють наступною властивістю: якщо кожна з них є NP-проблемою, то PSPACE=NP, і якщо кожна з них є Р-проблемою, то PSPACE=Р. [1]
І, нарешті, існує клас проблем EXPTIME. Ці проблеми вирішуються за експоненціальний час. Може бути дійсно доведено, що EXPTIME-повні проблеми не можуть бути вирішені за детермінований поліноміальний час. Також показано, що Р≠EXPTIME.
Приведемо для прикладу деякі NP-повні проблеми [6]:
- Проблема подорожуючого комівояжера. Подорожуючому комівояжерові потрібно відвідати різні міста, використовуючи тільки один бак з пальним (існує максимальна відстань, що він може проїхати). Чи існує маршрут, що дозволяє йому відвідати кожне місто тільки один раз, використовуючи цей єдиний бак з пальним.
- Проблема потрійного шлюбу. У кімнаті п чоловіків, п жінок і п чиновників. Є список дозволених шлюбів, запис якого складається з одного чоловіка, однієї жінки й одного чиновника, що реєструє. Дано цей список трійок, чи можливо побудувати п шлюбів так, що б будь-який або сполучився шлюбом тільки з одною людиною або реєстрував тільки один шлюб?
- Потрійна виконавчість. Є список п логічних виразів, кожне з трьома перемінними. Наприклад: якщо (х и у) то z, (х и w) або (не z), якщо ((не y і не х) або (z і (y або не x))) то (не z і x) або х), і т.д. Чи існують правильні значення всіх перемінних, щоб усі твердження були вірними?
Автори викладають лише основні відомості з теорії чисел, необхідні при вивчені алгоритмів з відкритим ключем. Теорія чисел і її застосування в криптографії розглядаються в [1, 6, 10]. Академічними виданнями з теорії чисел та обчислювальної математики є [11, 12].
Визначення 3.1.1. Нехай a, n Î Z. Число а поділяється на число n якщо найдеться таке число q Î Z, що а = qn. Синоніми: а кратний n; n – дільник а.
Запис: а 
n або n | a. [11]
Легко перевіряється наступна властивість:
Властивість 3.1.1. Нехай а1+а2+…+аn = c1+c2+…+ck – рівність сум цілих чисел. Якщо всі доданки в цій рівності, крім одного, кратні n, то і доданок, що залишився, зобов'язано бути кратним n. [11]
Теорема 3.1.1. Для даного цілого відмінного від нуля числа n, усяке ціле число а єдиним чином можна представити у вигляді а = nq+r, де 0 £ r < |n|. [11]
Визначення 3.1.1. Число q називається неповною часткою, а число r – залишком від ділення а на n. [11]
Арифметика залишків дуже схожа на звичайну арифметику: вона комутативна, асоціативна і дистрибутивна. Крім того, приведення кожного проміжного результату по модулю n дає той же результат, як і виконання всього обчислення з наступним приведенням кінцевого результату по модулю п.[1]
(а+b) mod п=((a mod п)+(b mod n)) mod n
(а – b) mod п=((a mod n) – (b mod n)) mod п
(а×b) mod п = ((а mod п) × (b mod n)) mod п
(а×(b+c)) mod п = (((a×b) mod п)+((а×с) mod n)) mod п
Обчислення mod n часто використовується в криптографії, тому що обчислення дискретних логарифмів і квадратних коренів mod n може бути нелегкою проблемою. Арифметика відрахувань, до того ж, легше реалізується на комп'ютерах, оскільки вона обмежує діапазон проміжних значень і результату. Для k-бітових відрахувань n, проміжні результати будь-якого додавання, вирахування або множення будуть не довше, ніж 2k біт. Тому в арифметиці відрахувань ми можемо виконати зведення в ступінь без величезних проміжних результатів. Обчислення ступеня деякого числа по модулю іншого числа,
являє собою просто послідовність множень і ділень, але існують прийоми, що прискорюють ці дії. Один з таких прийомів мінімізує кількість множень по модулю, інший – оптимізує окремі множення по модулю. Через те що операції дистрибутивні, швидше виконати зведення в ступінь як потік послідовних множень, щораз одержуючи відрахування. [1]
Приклад 3.1.1. Обчислити a8 mod n.
Виконаємо три множення і три приведення по модулю:
a8 mod n = ((a2 mod n)2 mod n)2 mod n
Аналогічно,
a16 mod n = (((а2 mod n)2 mod n)2 mod n)2 mod n
Обчислення ax, де х не є ступенем 2, ненабагато складніше. Бінарний запис представляє х у вигляді суми ступенів 2:25 – це бінарне 11001, тому 25 = 24+23+20. Маємо:
a25 mod n = (а×а24) mod n = (а×а8×а16) mod n = (а× (( а2)2)2×(((а2)2)2)2) mod n = (а× (((а×а2)2)2)2) mod n
Ось як даний метод буде виглядати у вигляді програми мовою C++:
unsigned long PowerMod(unsigned long Base,unsigned long Exp,unsigned long Mod)
{
unsigned long s,t,u;
s=1;t=Base;u=Exp;
while(u)
{
if(u&1)s=(s*t)%Mod;
u>>=1;
t=(t*t)%Mod;
}
return s;
}
Такий прийом називається ланцюжком додавань, або методом бінарних квадратів і множення. Він використовує простий і очевидний ланцюжок додавань, в основі якого лежить бінарне представлення числа. [6]
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.