потрібно після зведення в -ю ступінь отримати пару залишків . Оскільки прообразів кожного числа з однакову кількість, ймовірність отримання пари не вище .
Нехай .
Оскільки - непарне, , тобто знайдеться таке , , що , а або .
Будемо доводити, що з імовірністю не менш в цьому місці перевірка 2 алгоритму виявить, що - складене. У даному випадку , так що потрібно зрозуміти, з якою ймовірністю не дорівнює . Розглянемо два випадки. Одне з множин , одно . Нехай, наприклад, . У цьому випадку можна стверджувати, що (залишку при діленні на відповідає пара залишків при діленні на ).
Можна міркувати так само, як і у випадку 1. З імовірністю не менш отримаємо пару залишків , .
Обидва безлічі містять принаймні два елементи, нехай , . У цьому випадку може вийти як , так і , але ймовірність цього не перевершує .
Зауваження 3.3. Крок 2 в алгоритмі надлишковий, додатковими міркуваннями встановлюється, що і для чисел виду перевірки 1, 2 дають правильну відповідь зі значною вероятностью.і схемна складність.
Теорема 3.3. .
Доказ. Ідея докази полягає в тому, щоб посилити оцінки ймовірностей з до . Число має бути настільки мало, щоб можна було вибрати таке випадкове слово , при якому розглянутий предикат з BPP співпадає з .
Суть тут у тому, що повторення дослідів за поліноміальний час експоненціально зменшує оцінку ймовірності помилки , але не змінює розмір входу . Тому можна домогтися в...
