Тест простоти AKS

AKS-тест простоти (також відомий як тест простоти Агравал-Кайал-Саксена або циклотомічний AKS-тест) — детермінований алгоритм доведення простоти, розроблений та опублікований трьома індійськими науковцями Маніндрою Агравалом, Ніраєм Кайалом та Нітіном Саксеною 6 серпня 2002 р. в статті «PRIMES is in P» («Перевірка простоти належить до класу P»). Автори отримали за цю роботу у 2006 премію Геделя.

Алгоритм, який невдовзі був вдосконалений іншими, визначає чи є число простим чи складеним і виконується за поліноміальний час.

Важливість

Ключове значення AKS полягає в тому, що це перший опублікований алгоритм, який одночасно є поліноміальним, детермінованим та не спирається ні на які недоведені припущення. Тобто, максимальний час виконання алгоритму можна виразити як поліном від числа розрядів тестованого числа; він ґарантує вирішення задачі: є число простим чи складеним (а не отримання ймовірнісного результату); і його коректність не залежить від коректності якоїсь допоміжної недоведеної гіпотези (наприклад, гіпотези Рімана).

Підґрунтя тесту

AKS-тест ґрунтується на конгруенції

,

яка виконується тоді й тільки тоді, коли n просте. Це узагальнення малої теореми Ферма, поширеної на поліноми. Її можна легко довести, використовуючи біноміальну теорему та факт, що для всіх 0 < k < n, якщо n просте. Хоч ця рівність сама по собі є тестом простоти, її перевірка потребує експоненційного часу. Тому AKS використовує пов'язану з попередньою конгруенцію

,

яку можна перевірити за поліноміальний час. Проте ця конгруенція виконується не тільки для всіх простих чисел, але й для деяких складених. Доведення коректності AKS полягає в такому: показати існування відповідного малого r та відповідної малої множини цілих чисел A таких, що коли конгруенція виконується для всіх a в A, то n має бути простим. Алгоритм тестування простоти деякого цілого числа n складається з двох частин. Перший крок знаходить таке відповідне просте , що:

  • де  — найбільший простий дільник числа ,

Під час цього кроку важливо перевірити, що n не ділиться ні на яке просте ; якщо це не так, то алгоритм можна негайно завершити з повідомленням: n складене. На другому кроці виконується низка перевірок в скінченному полі , кожен раз перевіряється рівність двох поліномів над цим полем: якщо

для всіх додатних цілих чисел a з

то n ґарантовано є простим. У всіх інших випадках воно складене. Як і для інших таких алгоритмів, стаття стосується встановлення двох фактів: доведення коректності алгоритму та оцінки його асимптотичної часової складності. Це досягнуто доведенням двох ключових фактів, по-перше, показано, що підхоже r можна завжди знайти й встановленням верхньої границі його величини, по-друге, показано, що перевірки низки рівностей у другій частині алгоритму достатньо для гарантування розрізнювання: n просте чи складене. Оскільки час виконання обидвох частин алгоритму повністю залежить від величини r, отримання верхньої границі для r було достатнім, щоб показати, що асимптотична часова складність алгоритму рівна O, де ε — мале дійсне число. Іншими словами, алгоритм потребує менше часу, ніж константа, помножена на дванадцятий (плюс ε) степінь числа розрядів в n. Проте доведена в роботі верхня межа значно завищена, насправді, виконання припущення про розподіл простих чисел Софі Жермен негайно зменшило б оцінку до O. У наступні після відкриття місяці з'явилися нові варіанти (Ленстра 2002, Померанце 2002, Берізбейтіа 2003, Ченг 2003, Бернштейн 2003a/b, Ленстра та Померанце 2003), які покращили швидкість на кілька порядків. Через існування багатьох варіантів Крандел та Пападопоулос посилаються на «AKS-клас» алгоритмів у своїй науковій роботі «On the implementation of AKS-class primality tests» («Про реалізацію тестів простоти з AKS-класу»), опублікованій у березні 2003 р.

Оновлений AKS

У відповідь на деякі з цих варіантів та інші зауваження стаття «PRIMES is in P» була повторно опублікована з новим формулюванням AKS-алгоритму та доведенням його коректності. Хоча основна ідея залишилася тією ж, r вибирається по-іншому й доведення коректності виконано більш прозоро. Попереднє доведення спиралося на багато різних методів, а нова версія використовує майже виключно поведінку циклотомічних поліномів над скінченними полями. AKS-алгоритм знову складається з двох частин, і перший полягає в знаходженні відповідного r; проте у новій версії r є таким найменшим додатним цілим, що: На другому кроці знову перевіряється конгруенція

У цьому разі для всіх додатних цілих менших від де  — значення функції Ейлера для r. Ці зміни спростили хід доведення коректності. Вони також дозволили зменшити границю часової складності, яка відтоді оцінюється як O.

Ленстра та Померанце показали як вибрати поліноми в тесті, щоб досягти часової границі O.

Література

  1.  Manindra Agrawal, Neeraj Kayal, Nitin Saxena, «PRIMES is in P», Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
  2.  H. W. Lenstra, Jr. and Carl Pomerance, «Primality Testing with Gaussian Periods», preliminary version July 20, 2005.

Зовнішні посилання

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.