Автори алгоритму AKS на підставі порівняння (х - а)p = (хр - a)(modxr - 1, р) за-пропонували такий алгоритм.

Для реалізації і випробування тестів простоти треба мати прості числа з до-статньо великою кількістю цифр. Деякі найбільші з відомих простих чисел наведені в табл. 3.2.

Зокрема, число Люка, яке було найбільшим відомим простим числом протягом 75 років, у десятковому зображенні має вигляд:

2127- 1 = 170141183460469231731687303715884105727.

Твердження 3.13 (Люка). Число Мк = 2k - 1 (к > 2) тоді і тільки тоді є простим, якщо числоLk-1 i ділиться на Mk де L1 = 4, Ln+1 = Ln2-2, (L2 = 14, L3 = 194, L4 = 37634,...).

Зазначимо, що прості числа вигляду 2k- 1 (k також є простим числом) називають числами Мерсена, а прості числа вигляду 2k + 1 (к = 2т) - числами Ферма.

Афінні шифри

Найпростішими представниками асиметричних алгоритмів є афінні шифри. Нехай п - кількість літер абетки, нумерація яких починається від 0. Тоді можна збудувати такі шифри.

Шифр зсуву.

Ключ: s:0?s?n.

Шифрування. У повідомленні кожну літеру х заміняють на

Е(х) ? (х + s)mod n.

Дешифрування. У криптограмі кожну літеру х' заміняють на

D(x’)?(x’+s’)mod n,

де s' = п - s є ключем дешифрування.

Лінійний шифр.

Ключ: а:0<а<п та НСД(а, n) = 1.

Шифрування. У повідомленні кожну літеру х заміняють на

Е(х) ? (ax)mod n

Дешифрування. У криптограмі кожну літеру х' заміняють на

D(x') ? (a'x’)mod n,

де а' ? а-1 mod n є ключем дешифрування.

Афінний шифр.

Ключ: a, s:0?s?n,0 <а<п та НСД(а, п) = 1.

Шифрування. У повідомленні кожну літеру x заміняють на

Е(х) ? (ах + s)mod n.

Дешифрування. У криптограмі кожну літеру х' заміняють на

D(x') ? (ах + s')mod n,

де пара а' = а-1 mod n і s' ? (-a's) mod n є ключем дешифрування.

Приклад3.11. Нехай п = 33 і маємо афінний шифр з ключем а = 2, s=1. Припустимо, що явний текст є послідовністю цифр 9, 0, 2, 22, 20, 0. Тоді криптограма афінного шифру буде послідовністю цифр 19, 1,5, 12, 8, 1. Легко перевірити, що а'?2-1 mod 33 ? 17 та s' ? (-17*1) mod 33 ? 16.

Складність обчислень

Якщо функції f(n) > 0, g(n) > 0 є такими, що

то кажуть, що f є порядку О велике від g" і записують f= O(g). Наприклад, 4n2 + 2n + 5 = О(п2). Якщо ця границя дорівнює нулю, то пишуть f= o(g) і кажуть, що " f є порядку о мале від g".

Довжина числа n - це кількість бітів, потрібних для його запису: довжина (п) = 1 + [log2 n] = 1 + [In n / In 2], і цю величину можна оцінити як О(ln п). А, наприклад, довжина (п!) < п (довжина (n)) = О(п In n), оскільки всі числа, які множимо, мають довжину, не більшу, ніж довжина (п).

Кажуть, що алгоритм А є поліноміальним алгоритмом, якщо існує стале ціле число d таке, що число бітових операцій для виконання алгоритму А на даних дов-жиною k є порядку O(kd). Звичайні арифметичні операції є прикладами поліноміальних алгоритмів.

Алгоритм А є експоненційним, якщо на кожних даних довжини k він робить не більше ніж 0(ехр(kc)) бітових операцій, де с < 1 - деяка стала.

Приклад 3.12. Для заданих двох цілих чисел а > b > 0 час відшукання найбіль-шого спільного дільника чисел а і b та розв'язування відносно и і v рівняння au-bv =1можна оцінити як O(lna lnb). Оскільки а > b, то загальний час виконання алгоритму Евкліда можна оцінити як 0(ln2 а).

Задача належить до класу Р, якщо існує стала d й такий алгоритм, що коли варіант задачі має задані довжини не більше k, то алгоритм відповідає на питання, яке є суттю задачі, за час O(kd), тобто за поліноміальний час. Наприклад, час роботи ймо-вірнісного алгоритму тесту простоти Міллера-Рабіна - О(k3), тобто цей алгоритм нале-жить до класу Р.

Зазначимо, що час виконання алгоритму AKS оцінюють як O(k12f[log k)), де f - деякий поліном, k - кількість розрядів числа, яке перевіряють на простоту. Головна трудність практичного тестування чисел за допомогою цього алгоритму зумовлена значеннями сталих, що є у виразі для функції f. Крім того, сьогодні не відомо його порівняльних характеристик з іншими алгоритмами, що оперують цілими числами з великою кількістю розрядів.

Задача належить до класу NP, якщо для кожного варіанта задачі особа, яка має необмежену обчислювальну потужність, може не лише відповісти на питання, що є суттю задачі, а й у випадку, коли відповідь звучить "так", може навести аргументи, які інша особа зможе використати для перевірки правильності відповіді за поліноміальний час.

Задачу Q класу NP називають NP - повною задачею, якщо будь-яку іншу задачу класу NP можна звести до Q за поліноміальний час.

Проблема: чи P&NP, є однією з проблем, яку Clay Institute of Cambridge, Massachusetts у 2000 p. зачислив до семи найважливіших невирішених