иклад, схема множення чисел, стовпчиком має розмір, зростаючий квадратично від довжини входу. Хоча квадрат від довжини входу вже досить малий, щоб бути поліноміальним, зауважимо, що для множення-значних чисел є і більш економні схеми розміру. p> У модулярної арифметиці (арифметиці залишків за модулем заданого числа) можна обчислити за модулем схемою поліноміальною розміру від довжини входу (у звичайній арифметиці навіть результат зведення в ступінь може мати експонентний розмір). Для цього потрібно обчислити залишки від ступенів послідовним зведенням в квадрат і потім перемножити ті з отриманих чисел, яким відповідають 1 у двійковій запису числа. p> Найбільший спільний дільник двох чисел можна знайти, користуючись алгоритмом Евкліда, що використовують рекурсивно рівність. Якщо ділити більше число на менше, то за кожні два кроки довжина запису меншого числа зменшується на константу. p> Існує також алгоритм перевірки того, що з числа витягується без остачі корінь-го ступеня. Це можна зробити, знайшовши досить точно наближене значення кореня і звівши найближчим до нього ціле число в-ю ступінь. Знайти наближене значення можна за допомогою рекурентної послідовності
В
якщо вибрати відповідне значення. Деталі цього (полиномиального) алгоритму залишаються читачеві для самостійного обдумування. p> Зауважимо, що всі схеми, про які йшла мова вище, можуть бути побудовані МТ за поліноміальний час. Так що всі перераховані завдання належать класу P.
Тема 3.2 Алгоритм перевірки простоти
Вхід: число .
Крок 1. Перевіряємо парність . Якщо , то відповідь " - просте", якщо - парне і більше 2, то відповідь " - складене", в іншому випадку переходимо до кроку 2.
Крок 2. Перевіряємо, витягується чи з остачі корінь -го ступеня при . Якщо витягується, то відповідь " - складене", інакше переходимо до кроку 3.
Крок 3. Записуємо у вигляді , де , а - непарне.
Крок 4. Вибираємо випадкове серед чисел від до .
Крок 5. Обчислюємо за модулем .
Перевірка 1. Якщо , то відповідь " - складене".
Перевірка 2. Якщо знайдено таке , для якого
