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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Важливість[ред.ред. код]

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

Підґрунтя тесту[ред.ред. код]

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

(x - a)^{n} \equiv (x^{n} - a) \pmod{n}

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

(x - a)^{n} \equiv (x^{n} - a) \pmod{n, x^{r} - 1}

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

  • P(r - 1) = q де P(x) найбільший простий дільник числа x,
  • q \ge 4 \sqrt{r} \log_{2}(n),
  • n^k \not\equiv 1 \pmod{r}.

Під час цього кроку важливо перевірити, що n не ділиться ні на яке просте p \le r; якщо це не так, то алгоритм можна негайно перервати з повідомленням: n складене. На другому кроці, виконується низка перевірок в скінченному полі GF(n^r), кожен раз перевіряється рівність двох поліномів над цим полем: якщо

(x - a)^{n} \equiv (x^{n} - a) \pmod{n, x^{r} - 1}

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

 a \le 2 \sqrt{r} \log_{2}(n),

то n ґарантовано є простим. У всіх інших випадках воно складене. Як і для інших таких алгоритмів, стаття стосується встановлення двох фактів: доведення коректності алгоритму та оцінки його асимптотичної часової складності. Це досягнуто доведенням двох ключових фактів, по-перше, показано що підхоже r можна завжди знайти й встановленням верхньої границі його величини, по-друге, показано, що перевірки низки рівностей у другій частині алгоритму достатньо для гарантування розрізнювання: n просте чи складене. Оскільки час виконання обидвох частин алгоритму повністю залежить від величини r, отримання верхньої границі для r було достатнім, щоб показати, що асимптотична часова складність алгоритму рівна O(\log^{12+\epsilon}(n)), де ε мале дійсне число. Іншими словами, алгоритм потребує менше часу, ніж константа помножена на дванадцятий (плюс ε) степінь числа розрядів в n. Проте, доведена в роботі верхня межа значно завищена, насправді, виконання припущення про розподіл простих чисел Софі-Жермен негайно зменшило б оцінку до O(\log^{6+\epsilon}(n)). У наступні після відкриття місяці з’явилися нові варіанти (Ленстра 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 є таким найменшим додатнім цілим, що: o_r(n) > \log^2 n, На другому кроці знову перевіряється конгруенція

(x - a)^{n} \equiv (x^{n} - a) \pmod{n, x^{r} - 1}

У цьому разі для всіх додатніх цілих менших від \sqrt{\phi(r)} \log_{2}(n) де \phi(r) - значення функції Ейлера для r. Ці зміни спростили хід доведення коректності. Вони також дозволили зменшити границю часової складності, яка тепер рівна O(\log^{10.5}n).

Ленстра та Померанце показали[2] як вибрати поліноми в тесті, щоб досягти часової границі O(\log^6n).

Література[ред.ред. код]

  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.

Зовнішні зв’язки[ред.ред. код]