Тест простоти AKS
AKS-тест простоти (також відомий як тест простоти Агравал-Кайал-Саксена або циклотомічний AKS-тест) — детермінований алгоритм доведення простоти, розроблений та опублікований трьома індійськими науковцями Маніндрою Агравалом, Ніраєм Кайалом та Нітіном Саксеною 6 серпня 2002 р. в статті «PRIMES is in P» («Перевірка простоти належить до класу P»).[1] Автори отримали за цю роботу у 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.
Ленстра та Померанце показали[2] як вибрати поліноми в тесті, щоб досягти часової границі O.
Література
- ↑ Manindra Agrawal, Neeraj Kayal, Nitin Saxena, «PRIMES is in P», Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
- ↑ H. W. Lenstra, Jr. and Carl Pomerance, «Primality Testing with Gaussian Periods», preliminary version July 20, 2005.
Зовнішні посилання
- R. Crandall, Apple ACG, and J. Papadopoulos (March 18, 2003): On the implementation of AKS-class primality tests (PDF)
- Article by Borneman, містить фото й інформацію про трьох індійських вчених (PDF)
- Andrew Granville: It is easy to determine whether a given integer is prime
- The Prime Facts: From Euclid to AKS, by Scott Aaronson (PDF)
- The «PRIMES is in P» FAQ
- п
- о
- р
- AKS
- APR[en]
- Бейлі–PSW[en]
- На еліптичних кривих[en]
- Поклінґтона
- Ферма
- Люка
- Люка–Лемера
- Люка–Лемера–Райзела[en]
- Теорема Прота[en]
- Пепіна
- Квадратичний Фробеніуса[en]
- Соловея — Штрассена
- Міллера — Рабіна
- Решето Ератосфена
- Решето Сундарама
- Решето Прітчарда[en]
- Колесна факторизація
- Решето Аткіна
- Пробне ділення[en]
- Метод Ферма
- Ейлера[en]
- Лемана
- Діксона
- Ланцюгових дробів[en]
- Квадратичних форм Шенкса
- Ленстри на еліптичних кривих[en]
- ρ-Полларда
- p − 1[en]
- p + 1[en]
- Квадратичне решето
- Спеціальне решето числового поля[en]
- Загальне решето числового поля
- Раціональне решето[en]
- Шора
- Єгипетське
- Великих чисел[en]
- Карацуби
- Тоома – Кука[en]
- Шьонхаге — Штрассена
- Фюрера[en]
- Часткових лишків[en]
- Фур'є[en]
- Голдшмідта[en]
- Ньютона — Рефсона[en]
- Великих чисел
- Малих чисел[en]
- SRT[en]
- Маленький крок — великий крок[en]
- ρ-Полларда[en]
- Кенгуру Полларда[en]
- Поліґа—Геллмана
- Числення індексів[en]
- Функційне решето поля[en]
- Евклідів
- Розширений Евкліда
- Двійковий
- Лемера[en]
- Циполи[en]
- Поклінгтона[en]
- Тонеллі-Шенкса[en]
- Берлекемпа[en]
- Кунерта[en]
- Чакравали[en]
- Корначія[en]
- Швидке піднесення до степеня
- Цілочисельний квадратний корінь
- Алгоритм цілочисельного відношення (LLL[en]; KZ[en])
- Піднесення до степеня за модулем[en]
- Редукція Барретта
- Редукція Монгомері[en]
- Алгоритм Шуфа
- Курсивом показано алгоритми для чисел спеціального виду