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.
Література
Зовнішні посилання
- 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)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
AKS test prostoti takozh vidomij yak test prostoti Agraval Kajal Saksena abo ciklotomichnij AKS test determinovanij algoritm dovedennya prostoti rozroblenij ta opublikovanij troma indijskimi naukovcyami ta 6 serpnya 2002 r v statti PRIMES is in P Perevirka prostoti nalezhit do klasu P 1 Avtori otrimali za cyu robotu u 2006 premiyu Gedelya Algoritm yakij nevdovzi buv vdoskonalenij inshimi viznachaye chi ye chislo prostim chi skladenim i vikonuyetsya za polinomialnij chas VazhlivistKlyuchove znachennya AKS polyagaye v tomu sho ce pershij opublikovanij algoritm yakij odnochasno ye polinomialnim determinovanim ta ne spirayetsya ni na yaki nedovedeni pripushennya Tobto maksimalnij chas vikonannya algoritmu mozhna viraziti yak polinom vid chisla rozryadiv testovanogo chisla vin garantuye virishennya zadachi ye chislo prostim chi skladenim a ne otrimannya jmovirnisnogo rezultatu i jogo korektnist ne zalezhit vid korektnosti yakoyis dopomizhnoyi nedovedenoyi gipotezi napriklad gipotezi Rimana Pidgruntya testuAKS test gruntuyetsya na kongruenciyi x a n xn a modn displaystyle x a n equiv x n a pmod n yaka vikonuyetsya todi j tilki todi koli n proste Ce uzagalnennya maloyi teoremi Ferma poshirenoyi na polinomi Yiyi mozhna legko dovesti vikoristovuyuchi binomialnu teoremu ta fakt sho nk 0 modn displaystyle n choose k equiv 0 pmod n dlya vsih 0 lt k lt n yaksho n proste Hoch cya rivnist sama po sobi ye testom prostoti yiyi perevirka potrebuye eksponencijnogo chasu Tomu AKS vikoristovuye pov yazanu z poperednoyu kongruenciyu x a n xn a modn xr 1 displaystyle x a n equiv x n a pmod n x r 1 yaku mozhna pereviriti za polinomialnij chas Prote cya kongruenciya vikonuyetsya ne tilki dlya vsih prostih chisel ale j dlya deyakih skladenih Dovedennya korektnosti AKS polyagaye v takomu pokazati isnuvannya vidpovidnogo malogo r ta vidpovidnoyi maloyi mnozhini cilih chisel A takih sho koli kongruenciya vikonuyetsya dlya vsih a v A to n maye buti prostim Algoritm testuvannya prostoti deyakogo cilogo chisla n skladayetsya z dvoh chastin Pershij krok znahodit take vidpovidne proste r kq 1 displaystyle r kq 1 sho P r 1 q displaystyle P r 1 q de P x displaystyle P x najbilshij prostij dilnik chisla x displaystyle x q 4rlog2 n displaystyle q geq 4 sqrt r log 2 n nk 1 modr displaystyle n k not equiv 1 pmod r Pid chas cogo kroku vazhlivo pereviriti sho n ne dilitsya ni na yake proste p r displaystyle p leq r yaksho ce ne tak to algoritm mozhna negajno zavershiti z povidomlennyam n skladene Na drugomu kroci vikonuyetsya nizka perevirok v skinchennomu poli GF nr displaystyle GF n r kozhen raz pereviryayetsya rivnist dvoh polinomiv nad cim polem yaksho x a n xn a modn xr 1 displaystyle x a n equiv x n a pmod n x r 1 dlya vsih dodatnih cilih chisel a z a 2rlog2 n displaystyle a leq 2 sqrt r log 2 n to n garantovano ye prostim U vsih inshih vipadkah vono skladene Yak i dlya inshih takih algoritmiv stattya stosuyetsya vstanovlennya dvoh faktiv dovedennya korektnosti algoritmu ta ocinki jogo asimptotichnoyi chasovoyi skladnosti Ce dosyagnuto dovedennyam dvoh klyuchovih faktiv po pershe pokazano sho pidhozhe r mozhna zavzhdi znajti j vstanovlennyam verhnoyi granici jogo velichini po druge pokazano sho perevirki nizki rivnostej u drugij chastini algoritmu dostatno dlya garantuvannya rozriznyuvannya n proste chi skladene Oskilki chas vikonannya obidvoh chastin algoritmu povnistyu zalezhit vid velichini r otrimannya verhnoyi granici dlya r bulo dostatnim shob pokazati sho asimptotichna chasova skladnist algoritmu rivna O log12 ϵ n displaystyle log 12 epsilon n de e male dijsne chislo Inshimi slovami algoritm potrebuye menshe chasu nizh konstanta pomnozhena na dvanadcyatij plyus e stepin chisla rozryadiv v n Prote dovedena v roboti verhnya mezha znachno zavishena naspravdi vikonannya pripushennya pro rozpodil prostih chisel Sofi Zhermen negajno zmenshilo b ocinku do O log6 ϵ n displaystyle log 6 epsilon n U nastupni pislya vidkrittya misyaci z yavilisya novi varianti Lenstra 2002 Pomerance 2002 Berizbejtia 2003 Cheng 2003 Bernshtejn 2003a b Lenstra ta Pomerance 2003 yaki pokrashili shvidkist na kilka poryadkiv Cherez isnuvannya bagatoh variantiv Krandel ta Papadopoulos posilayutsya na AKS klas algoritmiv u svoyij naukovij roboti On the implementation of AKS class primality tests Pro realizaciyu testiv prostoti z AKS klasu opublikovanij u berezni 2003 r Onovlenij AKSU vidpovid na deyaki z cih variantiv ta inshi zauvazhennya stattya PRIMES is in P bula povtorno opublikovana z novim formulyuvannyam AKS algoritmu ta dovedennyam jogo korektnosti Hocha osnovna ideya zalishilasya tiyeyu zh r vibirayetsya po inshomu j dovedennya korektnosti vikonano bilsh prozoro Poperednye dovedennya spiralosya na bagato riznih metodiv a nova versiya vikoristovuye majzhe viklyuchno povedinku ciklotomichnih polinomiv nad skinchennimi polyami AKS algoritm znovu skladayetsya z dvoh chastin i pershij polyagaye v znahodzhenni vidpovidnogo r prote u novij versiyi r ye takim najmenshim dodatnim cilim sho or n gt log2 n displaystyle o r n gt log 2 n Na drugomu kroci znovu pereviryayetsya kongruenciya x a n xn a modn xr 1 displaystyle x a n equiv x n a pmod n x r 1 U comu razi dlya vsih dodatnih cilih menshih vid ϕ r log2 n displaystyle sqrt phi r log 2 n de ϕ r displaystyle phi r znachennya funkciyi Ejlera dlya r Ci zmini sprostili hid dovedennya korektnosti Voni takozh dozvolili zmenshiti granicyu chasovoyi skladnosti yaka vidtodi ocinyuyetsya yak O log10 5 n displaystyle log 10 5 n Lenstra ta Pomerance pokazali 2 yak vibrati polinomi v testi shob dosyagti chasovoyi granici O log6 n displaystyle log 6 n Literatura 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 Zovnishni posilannyaR Crandall Apple ACG and J Papadopoulos March 18 2003 On the implementation of AKS class primality tests PDF Article by Borneman mistit foto j informaciyu pro troh indijskih vchenih 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