Тест простоти — алгоритм перевірки, чи є дане число простим. Важливо наголосити на різниці між тестуванням простоти та факторизацією цілих чисел. Станом на 2009 рік, факторизація є обчислювально важкою проблемою, у той час як тестування простоти є порівняно простішим (має поліноміальну складність).
Наївні методи
Найпростіший тест простоти полягає в такому: коли задане число n, перевірити чи якесь ціле m від 2 до n-1 ділить n. Якщо n ділиться на певне m, то n складене, в іншому разі воно просте. Замість перевірки всіх m до n-1, досить лише перевірити m до : якщо n складене, то його можна розкласти на два множники, принаймні один з яких не перевищує . Можна також покращити ефективність, пропускаючи всі парні m , за винятком 2, бо коли якесь парне число ділить n , то 2 також ділить. Можна далі вдосконалити зауважуючи, що всі прості числа, за винятком 2 та 3, мають вигляд 6k ± 1. Дійсно, всі цілі можна подати як (6k + i) для деякого k та для i = -1, 0, 1, 2, 3, або 4; 2 ділить (6k + 0), (6k + 2), (6k + 4); а 3 ділить (6k + 3). Спочатку перевіряємо чи n ділиться на 2 або 3, тоді пробігаємо всі числа вигляду 6k ± 1. Це у 3 рази швидше від попереднього методу. Насправді, всі прості мають вигляд c#k + i для i<c# де і належить до чисел, взаємно простих з c# (прайморіал). Фактично, коли кількість значень, які c#k + i може набувати в певному діапазоні, зменшується, а, отже, час тестування зменшується. Для цього методу, слід ділити на всі прості менші ніж c. Спостереження, аналогічні до попереднього, можна застосувати рекурсивно, отримуючи решето Ератосфена. Вдалим способом пришвидшення цих методів (і всіх інших згаданих далі) є попередній обрахунок і зберігання списку всіх простих до певної межі, скажімо всіх простих до 200. (Такий список можна обчислити за допомогою решета Ератосфена). Тоді, перед тестуванням n на простоту з використанням серйозного методу, спочатку перевіряємо чи n не ділиться на якесь просте із цього списку.
Імовірнісні тести
Найпопулярнішими тестами простоти є ймовірнісні тести. Ці тести використовують, крім тестованого числа n, деякі інші числа a , які випадково вибираються з певного набору; звичні рандомізовані тести простоти ніколи не оголошують прості числа складеними, але можливе для складених чисел оголошення їх простими. Імовірність помилки можна зменшити, повторюючи тест з різними незалежно вибраними a; для двох найчастіше вживаних тестів, для будь-якого складеного n принаймні половина a визначає складеність n , тому k повторень зменшують імовірність помилки до щонайбільше 2−k. Останню величину можна зробити як завгодно малою, збільшуючи k.
Базова структура рандомізованих тестів простоти є такою:
- Випадково вибрати число a.
- Перевірити певну рівність, що містить a та задане число n. Якщо рівність не виконується, то число n — складене. a називають свідком[] складеності, і тест зупиняється.
- Виконувати крок 1, поки не буде досягнуто потрібної певності.
Після низки повторень, якщо не отримано, що n — складене число, то його можна оголосити .
Найпростішим імовірнісним тестом простоти є тест простоти Ферма. Це лише евристичний тест; складені числа Кармайкла будуть «імовірно простими» незалежно від того, яке число a обрати для тестування. Проте, іноді його застосовують з метою швидкої перевірки, наприклад, на фазі генерації ключів RSA.
Тест простоти Міллера — Рабіна та тест простоти Соловея-Штрассена є вдосконаленими варіантами, які визначають усі складені числа (це означає: для кожного складеного числа n, принаймні 3/4 (Міллер-Рабін) або 1/2 (Соловей-Штрассен) чисел a є свідками складеності n). На ці методи часто падає вибір, бо вони набагато швидші, ніж інші загальні тести простоти.
Леонард Адлеман та Хуанг запропонували варіант без помилки (але лише з очікуваним поліноміальним часом виконання) . На відміну від інших імовірнісних тестів, цей алгоритм дає сертифікат простоти, а тому може бути застосований для доведення простоти числа. Однак, алгоритм надто повільний на практиці.
Швидкі детерміновані тести
Близько початку 20 сторіччя дослідження показали, що тези з малої теореми Ферма можна використовувати для перевірки на простоту. Це призвело до появи тесту на простоту Поклінґтона. Однак, через те, що цей тест вимагає часткову факторизацію його часова складність у найгіршому випадку все ще дуже велика. Першим детермінованим тестом простоти значно швидшим, ніж наївні методи, був ; для часу його виконання отримано оцінку O((log n)clog(log(log(n)))), де n тестоване на простоту число, а c константа, незалежна від n. Це повільніше, ніж поліноміальний час.
Для можна отримати оцінку O((log n)6), але лише коли використовуємо деякі ще не доведені (але які як правило припускаються вірними) положення аналітичної теорії чисел. Це один з найчастіше вживаних на практиці детермінованих тестів.
Реалізація цих двох методів досить важка, бо є великий ризик помилок при програмуванні; це одна з причин, чому їм не віддають перевагу.
Якщо вважається вірною узагальнена гіпотеза Рімана, то тест Міллера-Рабіна можна звести до детермінованої версії з часом виконання O((log n)4). На практиці, цей алгоритм повільніший, ніж два інших для величин чисел, з якими можна реально оперувати.
У 2002, Маніндра Агравал, Нітін Саксена та Нірай Кайал описали новий детермінований тест простоти, AKS тест простоти, який як доведено виконується за O((log n)12). Крім того, якщо вірна , яку вважають справедливою, то він виконується за O((log n)6). Отже, маємо перший детермінований тест простоти з доведеним поліноміальним часом виконання. На практиці, цей алгоритм повільніший, ніж імовірнісні методи.
Складність
У теорії складності обчислень, формальну мову, яка відповідає простим числам, позначають PRIMES. Неважко показати, що PRIMES належить до Co-NP: її доповнення COMPOSITES належить до NP, бо можна показати складеність недетерміновано вгадуючи дільник.
У 1975 показав існування сертифікату простоти, який перевіряється за поліноміальний час, і значить PRIMES належить до NP, а тому й до NP ? coNP. Деталі дивись у .
Подальше відкриття алгоритмів Соловея-Штрассена та Міллера-Рабіна показало належність PRIMES до . У 1992 алгоритм Адлемана-Хуанга звузив складність до = RP ? coRP, що є заміщенням результату Пратта.
Циклотомічний тест Адлемана, та Рамлі 1983 р. показав належність PRIMES до QP (), для якого невідоме порівняння із згаданими раніше класами.
Існування AKS тесту простоти, який остаточно розв'язав цю давню проблему, означає, що PRIMES належить до .
Теоретико-числові методи
Існують певні теоретико-числові методи для тестування чи є число простим, зокрема та . Як правило, для цих тестів потрібний розклад n + 1, n − 1, або аналогічних чисел, а це означає, що вони не підходять для тестування простоти чисел загального вигляду, проте часто є досить потужним засобом, коли тестуємо число n спеціального вигляду.
Тест Лукаса-Лемера спирається на факт, що числа a за модулем n дорівнює n − 1 для простого n, якщо a примітивний корінь за модулем n. Коли можемо показати, що a примітивний корінь для n, то можемо довести простоту n.
Зовнішні зв’язки
- Distinguishing prime numbers from composite numbers, D.J. Bernstein
- The Prime Pages
- Big Primes Database
Література
- Richard Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective. 2nd edition, Springer, 2005. . Chapter 3: Recognizing Primes and Composites, pp.109–158. Chapter 4: Primality Proving, pp.159–190. Section 7.6: Elliptic curve primality proving (ECPP), pp.334–340.
- Donald Knuth. The Art of Computer Programming, Volume 2: Seminumerical Algorithms, Third Edition. Addison-Wesley, 1997. . Pages 391–396 of section 4.5.4.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 31.8: Primality testing, pp.887–896.
- Manindra Agrawa], Neeraj Kayal, Nitin Saxena, , Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
Див. також
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Test prostoti algoritm perevirki chi ye dane chislo prostim Vazhlivo nagolositi na riznici mizh testuvannyam prostoti ta faktorizaciyeyu cilih chisel Stanom na 2009 rik faktorizaciya ye obchislyuvalno vazhkoyu problemoyu u toj chas yak testuvannya prostoti ye porivnyano prostishim maye polinomialnu skladnist Nayivni metodiNajprostishij test prostoti polyagaye v takomu koli zadane chislo n pereviriti chi yakes cile m vid 2 do n 1 dilit n Yaksho n dilitsya na pevne m to n skladene v inshomu razi vono proste Zamist perevirki vsih m do n 1 dosit lishe pereviriti m do n displaystyle sqrt n yaksho n skladene to jogo mozhna rozklasti na dva mnozhniki prinajmni odin z yakih ne perevishuye n displaystyle sqrt n Mozhna takozh pokrashiti efektivnist propuskayuchi vsi parni m za vinyatkom 2 bo koli yakes parne chislo dilit n to 2 takozh dilit Mozhna dali vdoskonaliti zauvazhuyuchi sho vsi prosti chisla za vinyatkom 2 ta 3 mayut viglyad 6k 1 Dijsno vsi cili mozhna podati yak 6k i dlya deyakogo k ta dlya i 1 0 1 2 3 abo 4 2 dilit 6k 0 6k 2 6k 4 a 3 dilit 6k 3 Spochatku pereviryayemo chi n dilitsya na 2 abo 3 todi probigayemo vsi chisla viglyadu 6k 1 displaystyle leq n displaystyle sqrt n Ce u 3 razi shvidshe vid poperednogo metodu Naspravdi vsi prosti mayut viglyad c k i dlya i lt c de i nalezhit do chisel vzayemno prostih z c prajmorial Faktichno koli c displaystyle c rightarrow infty kilkist znachen yaki c k i mozhe nabuvati v pevnomu diapazoni zmenshuyetsya a otzhe chas testuvannya n displaystyle n zmenshuyetsya Dlya cogo metodu slid diliti na vsi prosti menshi nizh c Sposterezhennya analogichni do poperednogo mozhna zastosuvati rekursivno otrimuyuchi resheto Eratosfena Vdalim sposobom prishvidshennya cih metodiv i vsih inshih zgadanih dali ye poperednij obrahunok i zberigannya spisku vsih prostih do pevnoyi mezhi skazhimo vsih prostih do 200 Takij spisok mozhna obchisliti za dopomogoyu resheta Eratosfena Todi pered testuvannyam n na prostotu z vikoristannyam serjoznogo metodu spochatku pereviryayemo chi n ne dilitsya na yakes proste iz cogo spisku Imovirnisni testiNajpopulyarnishimi testami prostoti ye jmovirnisni testi Ci testi vikoristovuyut krim testovanogo chisla n deyaki inshi chisla a yaki vipadkovo vibirayutsya z pevnogo naboru zvichni randomizovani testi prostoti nikoli ne ogoloshuyut prosti chisla skladenimi ale mozhlive dlya skladenih chisel ogoloshennya yih prostimi Imovirnist pomilki mozhna zmenshiti povtoryuyuchi test z riznimi nezalezhno vibranimi a dlya dvoh najchastishe vzhivanih testiv dlya bud yakogo skladenogo n prinajmni polovina a viznachaye skladenist n tomu k povtoren zmenshuyut imovirnist pomilki do shonajbilshe 2 k Ostannyu velichinu mozhna zrobiti yak zavgodno maloyu zbilshuyuchi k Bazova struktura randomizovanih testiv prostoti ye takoyu Vipadkovo vibrati chislo a Pereviriti pevnu rivnist sho mistit a ta zadane chislo n Yaksho rivnist ne vikonuyetsya to chislo n skladene a nazivayut svidkom ustalenij termin skladenosti i test zupinyayetsya Vikonuvati krok 1 poki ne bude dosyagnuto potribnoyi pevnosti Pislya nizki povtoren yaksho ne otrimano sho n skladene chislo to jogo mozhna ogolositi Rozglyanemo skladene chislo n 65 5 13 Brehuni Ferma dlya 65 1 8 12 14 18 21 27 31 34 38 44 47 51 53 57 64 Brehuni Ojlera dlya 65 1 8 14 18 47 51 57 64 todi yak silni brehuni dlya 65 1 8 18 47 57 64 Najprostishim imovirnisnim testom prostoti ye test prostoti Ferma Ce lishe evristichnij test skladeni chisla Karmajkla budut imovirno prostimi nezalezhno vid togo yake chislo a obrati dlya testuvannya Prote inodi jogo zastosovuyut z metoyu shvidkoyi perevirki napriklad na fazi generaciyi klyuchiv RSA Test prostoti Millera Rabina ta test prostoti Soloveya Shtrassena ye vdoskonalenimi variantami yaki viznachayut usi skladeni chisla ce oznachaye dlya kozhnogo skladenogo chisla n prinajmni 3 4 Miller Rabin abo 1 2 Solovej Shtrassen chisel a ye svidkami skladenosti n Na ci metodi chasto padaye vibir bo voni nabagato shvidshi nizh inshi zagalni testi prostoti Leonard Adleman ta Huang zaproponuvali variant bez pomilki ale lishe z ochikuvanim polinomialnim chasom vikonannya Na vidminu vid inshih imovirnisnih testiv cej algoritm daye sertifikat prostoti a tomu mozhe buti zastosovanij dlya dovedennya prostoti chisla Odnak algoritm nadto povilnij na praktici Shvidki determinovani testiBlizko pochatku 20 storichchya doslidzhennya pokazali sho tezi z maloyi teoremi Ferma mozhna vikoristovuvati dlya perevirki na prostotu Ce prizvelo do poyavi testu na prostotu Poklingtona Odnak cherez te sho cej test vimagaye chastkovu faktorizaciyu n 1 displaystyle n 1 jogo chasova skladnist u najgirshomu vipadku vse she duzhe velika Pershim determinovanim testom prostoti znachno shvidshim nizh nayivni metodi buv dlya chasu jogo vikonannya otrimano ocinku O log n clog log log n de n testovane na prostotu chislo a c konstanta nezalezhna vid n Ce povilnishe nizh polinomialnij chas Dlya mozhna otrimati ocinku O log n 6 ale lishe koli vikoristovuyemo deyaki she ne dovedeni ale yaki yak pravilo pripuskayutsya virnimi polozhennya analitichnoyi teoriyi chisel Ce odin z najchastishe vzhivanih na praktici determinovanih testiv Realizaciya cih dvoh metodiv dosit vazhka bo ye velikij rizik pomilok pri programuvanni ce odna z prichin chomu yim ne viddayut perevagu Yaksho vvazhayetsya virnoyu uzagalnena gipoteza Rimana to test Millera Rabina mozhna zvesti do determinovanoyi versiyi z chasom vikonannya O log n 4 Na praktici cej algoritm povilnishij nizh dva inshih dlya velichin chisel z yakimi mozhna realno operuvati U 2002 Manindra Agraval Nitin Saksena ta Niraj Kajal opisali novij determinovanij test prostoti AKS test prostoti yakij yak dovedeno vikonuyetsya za O log n 12 Krim togo yaksho virna yaku vvazhayut spravedlivoyu to vin vikonuyetsya za O log n 6 Otzhe mayemo pershij determinovanij test prostoti z dovedenim polinomialnim chasom vikonannya Na praktici cej algoritm povilnishij nizh imovirnisni metodi SkladnistU teoriyi skladnosti obchislen formalnu movu yaka vidpovidaye prostim chislam poznachayut PRIMES Nevazhko pokazati sho PRIMES nalezhit do Co NP yiyi dopovnennya COMPOSITES nalezhit do NP bo mozhna pokazati skladenist nedeterminovano vgaduyuchi dilnik U 1975 pokazav isnuvannya sertifikatu prostoti yakij pereviryayetsya za polinomialnij chas i znachit PRIMES nalezhit do NP a tomu j do NP coNP Detali divis u Podalshe vidkrittya algoritmiv Soloveya Shtrassena ta Millera Rabina pokazalo nalezhnist PRIMES do U 1992 algoritm Adlemana Huanga zvuziv skladnist do RP coRP sho ye zamishennyam rezultatu Pratta Ciklotomichnij test Adlemana ta Ramli 1983 r pokazav nalezhnist PRIMES do QP dlya yakogo nevidome porivnyannya iz zgadanimi ranishe klasami Isnuvannya AKS testu prostoti yakij ostatochno rozv yazav cyu davnyu problemu oznachaye sho PRIMES nalezhit do Teoretiko chislovi metodiIsnuyut pevni teoretiko chislovi metodi dlya testuvannya chi ye chislo prostim zokrema ta Yak pravilo dlya cih testiv potribnij rozklad n 1 n 1 abo analogichnih chisel a ce oznachaye sho voni ne pidhodyat dlya testuvannya prostoti chisel zagalnogo viglyadu prote chasto ye dosit potuzhnim zasobom koli testuyemo chislo n specialnogo viglyadu Test Lukasa Lemera spirayetsya na fakt sho chisla a za modulem n dorivnyuye n 1 dlya prostogo n yaksho a primitivnij korin za modulem n Koli mozhemo pokazati sho a primitivnij korin dlya n to mozhemo dovesti prostotu n Zovnishni zv yazkiDistinguishing prime numbers from composite numbers D J Bernstein The Prime Pages Big Primes DatabaseLiteraturaRichard Crandall and Carl Pomerance Prime Numbers A Computational Perspective 2nd edition Springer 2005 ISBN 0 387 25282 7 Chapter 3 Recognizing Primes and Composites pp 109 158 Chapter 4 Primality Proving pp 159 190 Section 7 6 Elliptic curve primality proving ECPP pp 334 340 Donald Knuth The Art of Computer Programming Volume 2 Seminumerical Algorithms Third Edition Addison Wesley 1997 ISBN 0 201 89684 2 Pages 391 396 of section 4 5 4 Thomas H Cormen Charles E Leiserson Ronald L Rivest and Clifford Stein Introduction to Algorithms Second Edition MIT Press and McGraw Hill 2001 ISBN 0 262 03293 7 Section 31 8 Primality testing pp 887 896 Manindra Agrawa Neeraj Kayal Nitin Saxena Annals of Mathematics 160 2004 no 2 pp 781 793 Div takozhAKS test prostoti