просте число, х є N, р не ділить х та у2 = x(mod р). Тоді
у = ±xm+l (mod р)є Zр* при = 4m + 3;
у = ±xm+l(mod р) при р = 8т+ 5 та x2m+l ? 1 (mod p);
у = ±xm+l 22m+l(mod p) при p=8m+ 5 ma x2m+1 ?-l (mod p).
Тести простоти
Розглянемо таку задачу, яка виникає в разі побудови криптографічних систем з відкритим ключем. Маємо натуральне число л. Треба перевірити, чи п є простим чис-лом. Алгоритми розв'язування цієї задачі називають тестами простоти. їх поділяють на дві групи: ймовірнісні та детерміновані.
Спочатку розглянемо ймовірнісні тести. Ці тести простоти потребують менших обчислювальних затрат, проте дають відповідь щодо простоти числа з певною похиб-кою, ймовірність якої можна оцінити.
На підставі малої теореми Ферма wp-1 = l(mod р) для кожного простого р і w < p. Кажемо, що w < п є основою простоти для п (або в іншій термінології: п є простим за основою w), якщо wp-1 = l(mod n). У випадку, якщо п - просте число, всі числа w < п є основами простоти для п.
Тест Ферма: к разів незалежно виконуємо тест (к вибирає користувач):
вибираємо випадкове число w<n і обчислюємо НСД(w, n);
якщо НСД(w, п) > 1, то л є складеним числом;
обчислюємо u = wn-1(mod n);
якщо u?1,то п є складеним числом.
Якщо під час жодного з k тестів не ствердимо, що п- складене число, то відпо-відь звучить так: "п є простим числом".
Твердження 3.10. Нехай S позначає множину чисел, взаємно простих з п. Тоді zoo кожен елемент S є основою простоти для п, або щонайменше половина елементів
- с основами простоти для п.
Із твердження 3.10 випливає таке: якщо для складеного числа п існує число w, що не є основою простоти для л, то з імовірністю 1/2 в одиничному тесті знайдемо число, гкі не є основою простоти для л. Ймовірність для k спроб становить 1/2 .
Проблема полягає в тому, що існують складені числа п, для яких усі елементи S є основами простоти для п. Для них тест Ферма завжди дає хибну відповідь. Такі числа називають числами Кармайкла. Найменшим з них є число 561 = 3* 11* 17. Лише порівняно недавно (1994) доведено, що множина таких чисел нескінченна. Складено таблицю для всіх чисел Кармайкла, менших від числа 25- 109.
Тест Ферма можна модифікувати так, щоб отримати справді ймовірнісний тест простоти чисел.
Тест Міллера-Рабіна дослідження числа п на простоту. Нехай п – 1=28* т, де 28
- найвищий степінь двійки, який ділить п-1, т непарне. Нехай k - задане натуральне число. Незалежно k разів виконуємо тест:
вибираємо випадково число х у межах: 1 < х < п;
якщо НСД(x,п) не дорівнює 1, то "п є складеним " і кінець алгоритму, інакше переходимо до наступного пункту;
обчислюємо y0 = х m(mod n);
якщо уо= l(mod n), то припиняємо обчислення і стверджуємо, що "п просте ", інакше переходимо до наступного пункту;
обчислюємо у? yi-12(mod n), перериваючи обчислення, якщо у, = ±l(mod n);
якщо уі= l(mod n), то стверджуємо, що "п складене", якщо уi = -1(тоd п),
то стверджуємо, що "п просте".
Тест Міллера-Рабіна ґрунтується на такому: якщо п просте й х2= l(mod n), то х = l(mod п) або x = -l(mod n) , а кожен елемент уi-1 є коренем з уi за модулем п, де 0<і<s
Твердження 3.11. Якщо п складене, то ймовірність, що випадково вибране х < п не є основою простоти для п, становить щонайменше 3/4.
Із твердження 3.11 випливає, що k-разове застосування тесту Міллера-Рабіна дасть хибну відповідь для складеного числа з ймовірністю, не більшою ніж 1/4k.
Детерміновані тести простоти потребують більших обчислювальних затрат, ніж імовірнісні тести, проте дають точну відповідь щодо простоти числа.
Здавна відомі тести простоти, які є одночасно алгоритмами факторизації. Вони потребують занадто великих обсягів обчислень, і тому сьогодні їх практично не використовують.
Сучасні детерміновані тести простоти залучають складні побудови сучасної абстрактної алгебри. Використовують обчислення та критерії в алгебричних структурах, відмінних від кільця цілих чисел за модулем, а саме:
кільцях Z[Ј,,], де Ј, - корінь з одиниці степеня р;
групах точок еліптичних кривих, заданих над певним скінченим полем.
У 2002 р. М.Агравал, Н.Кайал та Н.Саксена запропонували порівняно простий детермінований алгоритм AKS, що не опирається ні на які недоведені припущення. Ключовою для алгоритму AKS є така проста модифікація малої теореми Ферма.
Твердження 3.12. Нехай а ір - взаємно прості цілі числа (р > 1); р просте тоді і тільки тоді, коли (х- а)р = (xp - a)(mod p).
Конгруенція (х-а)р = {хр -a)(modр) означає, що коефіцієнти наведених много-членів дорівнюють за модулем р.
Справді, якщо р просте, то р ділить біноміальні коефіцієнти Сpr для r= 1,2,...,р-1. Звідси випливає (х-1)р = (хp -ap)(mod р), і наведений у твердженні результат є наслідком малої теореми Ферма. З іншого боку, якщо р > 1 є складеним числом, то воно має простий дільник q. Нехай k - найбільший степінь числа q, що ділить число р. Тоді qk не ділить Сpr і є взаємно простим числом з аp-q. Отже, коефіцієнт при хq у лівій частині порівняння (х - а)p= (хр - a)(mod р) є ненульовим, а коефіцієнт при хq y його правій частині є нульовим.
Наведене у твердженні порівняння надто важко використати практично, оскільки для великих значень р