Милер—Рабинов тест

Милер—Рабинов тест је тест који проверава да ли је дати број прост, слично Фермаовом тесту за просте бројеве и Соловеј—Штрасеновом тесту. Оригинална верзија теста, који је осмислио Гари Милер, детерминистичког је типа, али се детерминизам заснива на општијој Римановој хипотези;^[1] Мајкл О. Рабин је модификовао тест тако да добије безусловни пробабилистички алгоритам.^[2]

Концепт

Слично као код Фермаовог и Соловеј—Штрасеновог теста, Милер—Рабинов тест се заснива на одрећеним својствима која важе за просте бројеве и провером да ли дати број испуњава неки од тих својстава.

Најпре, lemma о Моавровим бројевима у коначном пољу Z/pZ, где је p прост број и p > 2. Наравно 1 и -1 увек дају 1 кад се коренују по modulu p и зову се тривијални корени јединице. Не постоје не тривијални корени јединице. Да би доказали ово претпоставимо супортно, нека је x корен јединице по модулу p. Onda:

x^{2}\equiv 1{\pmod {p}}

(x-1)(x+1)\equiv 0{\pmod {p}}.

Другим речима, прост број p дели производ (x − 1)(x + 1). По Еуклидовој леми он дели и факторе од x − 1 или одx + 1,, дакле x је конгурентно са 1 или 1 по модулуp.

Нека је n прост број и нека је n > 2. Следи да n − 1 је паран и да можемо га написати као 2^s·d, где су s и d позитивни цели бројеви(при чему је d прост). За свако a у (Z/nZ)*, важи

a^{d}\equiv 1{\pmod {n}}

или

a^{2^{r}\cdot d}\equiv -1{\pmod {n}}

за неко 0 ≤ r ≤ s − 1.

Да би показали да је ово тачно користићемо малу Фермаову теорему, која каже да за прост број n важи:

a^{n-1}\equiv 1{\pmod {n}}.

По леми одозго, ако наставимо да узимамо корене од aⁿ⁻¹, добиће се или 1 или −1. Ако се добије −1 онда друга једнакост важи и ту је крај. Иначе, ако никад не добијемо −1, онда смо узели све степене 2 и остала нам је прва једнакост.

Милер—Рабинов тест се заснива на контрапозицији тврћења изнад. То јест, ако можемо да нађемо a такво да важи

a^{d}\not \equiv 1{\pmod {n}}

и

a^{2^{r}d}\not \equiv -1{\pmod {n}}

за све 0 ≤ r ≤ s − 1, онда n није прост број. Такво a зовемо сведоком сложености од n. Иначе a се зовејаким лажовом, и n је снажан вероватан прост број у бази a. Назив "јак лажов" се односи на случај где је nсложен број, али свеједено једнакости(својства) важе као и да је прост.

Сваки непаран сложен број n има много сведока a, али није наћен лак начин за налажење таквогa. Решење је да тест буде пробабилистички: бирамо случјно a, које је различито од нуле, у Z/nZ и проверавамо да ли је или није сведок за сложеност броја n. Ако је n сложен, већина случајних избора заa ће бити такво да је а сведок, и тест ће открити да је n сложен са веома великом вероватноћом. Ипак постоји мала шанса да за број a буде изабран јак лажов заn. Може се смањити вероватноћу такве грешке тако што ће се тест понављати за неколико независно изабраних a.

За тестирање великих бројева, уобичајно је да се изабере случајна база a, а приори, ми не знамо расподелу сведока и лажова код бројева 1, 2, ..., n − 1. Наручито, Арно^[3] је дао сложен број од 397 цифара за који све базе од a које су мање од 307 цифара су јаки лажови. Као и очекивано, овај број је пријављен као прост од стране Maple isprime() функције, која имплементира Милер—Рабинов тест проверавајући специфичне базе 2, 3, 5,7 и 11. Но, одабир неколико специфичних база може загарантовати проверу сложених бројева за n мањих од максимума одрећеног тим базама. Овај максимум је обично доста велик у односу на базе. Како случајне базе немају такав детерминизам за мало n, специфичне базе су боље у неким условима.

Примери

Уколико бисмо хтели да проверимо да ли је n = 221 прост број, прво би написали n − 1 = 220 као 2²·55, тако да је s = 2 и d = 55. Насумично изаберемо a тако да 0 < a < n, нпр. a = 174. Даље:

a^2⁰·d mod n = 174⁵⁵ mod 221 = 47 ≠ 1, n − 1
a^2¹·d mod n = 174¹¹⁰ mod 221 = 220 = n − 1.

Пошто је 220 ≡ −1 mod n, онда је 221 прост, или 174 је јак лажов за 221. Пробамо са још једним насумично изабраним a, овај пут нпр. a = 137:

a^2⁰·d mod n = 137⁵⁵ mod 221 = 188 ≠ 1, n − 1
a^2¹·d mod n = 137¹¹⁰ mod 221 = 205 ≠ n − 1.

Стога 137 је сведок за сложеност броја 221, и 174 је заправо био јак лажов. Приметимо да нам ово не говори ништа о факторима 221 (тачније о 13 и 17). Но, пример са 341 у следећем одељку показује да ова израчунавања некад могу да нађу факторе од n.

Алгоритам и време извршавања

Алгоритам може да се запише у следећем псеудокоду:

Input: n > 3, an odd integer to be tested for primality;
Input: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2^s·d with d odd by factoring powers of 2 from n − 1
WitnessLoop: repeat k times:
   pick a random integer a in the range [2, n − 2]
   x ← a^d mod n
   if x = 1 or x = n − 1 then do next WitnessLoop
   repeat s − 1 times:
      x ← x² mod n
      if x = 1 then return composite
      if x = n − 1 then do next WitnessLoop
   return composite
return probably prime

Користећи модуларно степеновање (c ≡ b^e (mod m)) помоћу алгоритма брзог степеновања квадрирањем, време извршавања овог алгоритма је О(k log³n), где је k број различих вредности броја a којег тестирамо; тако да је ово један ефикасан алгоритам који ради у полиномијалном времену. Користећи множење ѕасновано на брзим Фуријеовим трансофрмацијама време извршавања се скраћује на O(k log²n log log n log log log n) = Õ(k log²n).

Ако убацимо израчунавање највећег заједничког делиоца (НЗД) у горенаведени алгоритам, можемо понекад да добијемо и чиниоце броја n него да само утврдимо да ли је n сложен. Посебно, ако је n вероватан прост за основу a али не и јак вероватан прост за основу a, или НЗД((a^d mod n) − 1, n) или (за неко r из горенаведеног опсега) НЗД((a^{2^r·d} mod n) − 1, n) даје (не обавезно прост) чинилац броја n;видети страницу 1402.^[4] Ако је факторисање циљ, онда се ова НЗД израчунавања могу убацити у алгоритам по без превеликих губитака брзине израчунавања.

На пример, рецимо да је n = 341. Даље је n − 1 = 85·4.. Затим 2⁸⁵ mod 341 = 32. Ово нам говори да n није јак вероватан прост број основе 2, па знамо да је n сложен. Ако примени НЗД у овом кораку, добијамо чинилац од 341: НЗД((2⁸⁵ mod 341) − 1, 341) = 31. Ово је исправно јер 341 је псеудо прост у основи 2, али није и јак псеудопрост у основи 2.

У случају да алгоритам врати „сложен“ јер x = 1, уједно је и откривено да је d2^r (непаран умножак) [Ред (теорија група)|реда]] броја a -чињеница која може (као и уШоровом алгоритму) да се искористи да се n факторише, јер n онда дели

a^{d2^{r}}-1=(a^{d2^{r-1}}-1)(a^{d2^{r-1}}+1)

али не и сваки фактор сам по себи. Разлог због ког Милер—Рабинов тест не даје пробабилистички алгоритам за [[Rastavljanje na faktore|факторизацију]] је то што ако

a^{n-1}\not \equiv 1{\pmod {n}}

(другим речима, n није псеудопрост за основу a), онда никакава информација тог типа није добијена о периодичности броја a, и онда алгоритам бира други „return composite“ излаз.

Тачност теста

Што више база а тестирамо, већа је тачност теста. Може се показати да ће за сваки непаран сложен број n бар 3/4 база а бити сведоци за сложеност од n.^[2]^[5] Милер—Рабинов тест је строго јачи од Соловеј—Штрасеновог теста прималности у смислу да је за сваки сложени број n, скуп јаких лажова за n подскуп скупа Ојлерових лажова за број n, и за многе n тај потскуп је садржан у целини. Ако је n сложено онда Милер—Рабинов тест тврди да је n прост са вероватноћом од највише 4^−k. Са друге стране, Соловеј—Штрасенов тест прималности тврди да је n прост са вероватноћом од највише 2^−k.

Битно је приметити да многим уобичајеним применама овог алгоритма, нас не занима опсег грешке који је овде горенаведен. Тај опсег грешке представља вероватноћу да се сложен број прогласи за могућ прост број после k кругова тестирања. Уместо тога, често нас занима вероватноћа да ли је, прошавши k кругова тестирања, број који испитујемо заправо сложен. Формално, ако ми назовемо догађај проглашавања n за могућ прост број после k кругова Милер—Рабина назовемо Y_k, и ако назовемо догађај тога да је n сложен број X (И обележимо догађај тога да је n прост ${\overline {X}}$ ), онда нам горенаведен опсег даје $P(Y_{k}|X)$ , док са друге стране нас занима $P(X|Y_{k})$ . Бајесова теорема нам даје начин да повежемо ове две условне вероватноће, наиме

P(X|Y_{k})={\frac {P(Y_{k}|X)P(X)}{P(Y_{k}|X)P(X)+P(Y_{k}|{\overline {X}})P({\overline {X}})}}

.

Ово нам говори да вероватноћа која нас често занима није везана само за опсег од 4^−k, али и за вераватноће које су везане за густину простих бројева у околини броја n.

Додатно, за велике вредности броја n, вероватноћа да је сложен број проглашен као вероватно прост је у просеку знатно мања од 4^−k. Дамгорд, Лендрок и Померанс^[6] су израчунали неке експлицитне опсеге и пружају метод за разуман избор броја k да би се добио жељени опсег грешке. Такви опсези могу, на приmер, да се искористе да генеришу вероватне просте бројеве; ипак, не би се требало користити да потврђују просте бројеве непознатог порекла, јер у криптографској примени непријатељ може да покуша да вам пошаље псеудопорст број тамо где је потребан прост број. у таквим случајевима, може се ослонити само на опсег грешке од 4^−k.

Детерминистичке варијанте теста

Милер—Рабинов тест се може учинити детерминистичким тако што се проба за свако могуће a испод одређене границе. Проблем је углавно да се одреди граница тако да је тест још увек поуздан.

Ако је број n који се тестира сложен, јаки лажови a који су узајамно прости са n се садрже у строго мањој подгрупи групе (Z/nZ)*, што значи да ако ми тестирамо свако a из скупа који генерише (Z/nZ)*,, један од њих мора бити сведок сложености броја n. Претпостављајући тачност уопштене Риманове хипотезе, зна се да групу генеришу њени елементи мањи од O((log n)²), што је Милер и сам био приметио.^[1] Ерик Бах је смањио константу која се била користила у Велико О нотацији на 2^[7]. То нас доводи до следећег алгоритма за тестирање условне прималности:

Input: n > 1, an odd integer to test for primality.
Output: composite if n is composite, otherwise prime
write n−1 as 2^s·d by factoring powers of 2 from n−1
repeat for all  $a\in [2,\min(n-1,\lfloor 2(\ln n)^{2}\rfloor )]$ :
    if  $a^{d}\not \equiv 1{\pmod {n}}{\text{ and }}a^{2^{r}\cdot d}\not \equiv -1{\pmod {n}}{\text{ for all }}r\in [0,s-1]$ 
    then return composite
return prime

Време извршавања алгоритма је Õ((log n)⁴) (са множењем заснованим на брзим Фуријеовим трансофрмацијама). Нису потребне све ставке уопштене Риманове хипотезе да би се осигурала тачност теста. Пошто радимо са подгрупама парног индекса, довољно је претпоставити тачност квадратних Дирихлеових карактера.^[5]

Милеров тест (горе приказан алгоритам) се не користи у пракси. У већини случајева, коришћење пробабилистичког Милер—Рабиновог теста или [[Бејли-PSW тест прималности|Бејли-PSW теста прималности]], даје довољну тачност радећи много брже. Такође је спорији у пракси него уобичајно коришћени методи доказивања као што су Ејдлман-Померанс-Рамлијев тест прималности, и доказивање прималности елиптичком кривом који дају резултате који се не ослањају на недоказане претпоставке.

Када је број n који тестирамо довољно мали, није потребно испробати свако a за које важи -a < 2(ln n)²-, јер је познато да су мањи скупови могућих сведока довољни. На пример, Померанс, Селфриџ и Вегстаф^[8] и Јешке^[9] су потврдили да

Ако је n < 2.047, довољно је да се испроба a = 2;
Ако је n < 1.373.653, довољно је да се испроба a = 2 и 3;
Ако је n < 9.080.191, довољно је да се испроба a = 31 и 73;
Ако је n < 25.326.001, довољно је да се испроба a = 2, 3 и 5;
Ако је n < 4.759.123.141, довољно је да се испроба a = 2, 7 и 61;
Ако је n < 1.122.004.669.633, довољно је да се испроба a = 2, 13, 23 и 1.662.803;
Ако је n < 2.152.302.898.747, довољно је да се испроба a = 2, 3, 5, 7 и 11;
Ако је n < 3.474.749.660.383, довољно је да се испроба a = 2, 3, 5, 7, 11 и 13;
Ако је n < 341.550.071.728.321, довољно је да се испроба a = 2, 3, 5, 7, 11, 13 и 17;
Ако је n < 3.852.123.056.546.413.051, довољно је да се испроба a = 2, 3, 5, 7, 11, 13, 17, 19 и 23;

Треба напоменути да се Милер—Рабинови псеудопрости бројеви називају Снажни псеудопрости бројеви.

Други критеријуми ов врсте постоје^[10]^[11]^[12]^[13] и ови резултати дају веома брзе детерминистичке тестове прималности за бројеве и прхватљивом опсегу, а без икаквих претпоставки.

Постоји мала листа могућих сведока за сваку могућу величину уноса (највише n вредности за n-то битне бројеве). Ипак, ниједан коначан скуп база није довољан за све сложене бројеве. Алфорд, Гренвил и Померанс су показали да постоји бесконачно много сложених бројева n чији је најмањи сведок сложености величине бар -(ln n)^{1/(3ln ln ln n)}-.^[14] Они такође хеуристичким методама аргументују да би најмањи број w такав да сваки сложен број мањи од n има сведока сложености мањег од w требало да буде реда величине Θ(log n log log n).

Референце

^ ^а ^б Miller, Gary L. (1976), „Riemann's Hypothesis and Tests for Primality”, Journal of Computer and System Sciences, 13 (3): 300—317, doi:10.1145/800116.803773
^ ^а ^б Rabin, Michael O. (1980), „Probabilistic algorithm for testing primality”, Journal of Number Theory, 12 (1): 128—138, doi:10.1016/0022-314X(80)90084-0
^ F. Arnault (август 1995). „Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases”. Journal of Symbolic Computation. 20 (2): 151—161. doi:10.1006/jsco.1995.1042.
^ Baillie, Robert; Samuel S. Wagstaff, Jr. (октобар 1980). „Lucas Pseudoprimes” (PDF). Mathematics of Computation. 35 (152): 1391—1417. MR 583518. doi:10.1090/S0025-5718-1980-0583518-6.
^ ^а ^б Schoof, René (2004), „Four primality testing algorithms”, Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography (PDF), Cambridge University Press, ISBN 978-0-521-80854-5
^ Damgård, I.; Landrock, P. & Pomerance, C. (1993), „Average case error estimates for the strong probable prime test” (PDF), Mathematics of Computation, 61 (203): 177—194, doi:10.2307/2152945
^ Bach, Eric (1990), „Explicit bounds for primality testing and related problems”, Mathematics of Computation, 55 (191): 355—380, doi:10.2307/2008811
^ Pomerance, Carl; John L. Selfridge, Samuel S. Wagstaff, Jr. (јул 1980). „The pseudoprimes to 25·10⁹” (PDF). Mathematics of Computation. 35 (151): 1003—1026. doi:10.1090/S0025-5718-1980-0572872-7.
^ Jaeschke, Gerhard (1993), „On strong pseudoprimes to several bases”, Mathematics of Computation, 61 (204): 915—926, doi:10.2307/2153262
^ The Primes Page
^ Zhang, Zhenxiang & Tang, Min (2003), „Finding strong pseudoprimes to several bases. II”, Mathematics of Computation, 72 (44): 2085—2097, doi:10.1090/S0025-5718-03-01545-X
^ Шаблон:SloanesRef
^ SPRP Records
^ {{Citation |last=Alford|first=W. R. |last2=Granville |first2=A. |last3=Pomerance |first3=C. |lastauthoramp= |year=1994 |title=On the difficulty of finding reliable witnesses |journal=Lecture Notes in Computer Science |volume=877 |publisher=Springer-Verlag |url=http://www.math.dartmouth.edu/~carlp/PDF/reliable.pdf |doi=10.1007/3-540-58691-1_36 |id=}

Спољашње везе

Weisstein, Eric W. „Rabin-Miller Strong Pseudoprime Test”. MathWorld.
Интерактивна онлајн имплементација детерминистичке варијанте (Корак по корак приказ рада алгортима)
Аплет(Немачки)
Милер—Рабинов тест прималности у C#
Милер—Рабинов тест прималности у Јаваскрипту користећи аритметику арбитрарне прецизности

[miller-1] а ^б Miller, Gary L. (1976), „Riemann's Hypothesis and Tests for Primality”, Journal of Computer and System Sciences, 13 (3): 300—317, doi:10.1145/800116.803773

[rabin-2] а ^б Rabin, Michael O. (1980), „Probabilistic algorithm for testing primality”, Journal of Number Theory, 12 (1): 128—138, doi:10.1016/0022-314X(80)90084-0

[Arnault397Digit-3] F. Arnault (август 1995). „Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases”. Journal of Symbolic Computation. 20 (2): 151—161. doi:10.1006/jsco.1995.1042.

[baillie-4] Baillie, Robert; Samuel S. Wagstaff, Jr. (октобар 1980). „Lucas Pseudoprimes” (PDF). Mathematics of Computation. 35 (152): 1391—1417. MR 583518. doi:10.1090/S0025-5718-1980-0583518-6.

[schoof-5] а ^б Schoof, René (2004), „Four primality testing algorithms”, Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography (PDF), Cambridge University Press, ISBN 978-0-521-80854-5

[6] Damgård, I.; Landrock, P. & Pomerance, C. (1993), „Average case error estimates for the strong probable prime test” (PDF), Mathematics of Computation, 61 (203): 177—194, doi:10.2307/2152945

[7] Bach, Eric (1990), „Explicit bounds for primality testing and related problems”, Mathematics of Computation, 55 (191): 355—380, doi:10.2307/2008811

[PSW-8] Pomerance, Carl; John L. Selfridge, Samuel S. Wagstaff, Jr. (јул 1980). „The pseudoprimes to 25·10⁹” (PDF). Mathematics of Computation. 35 (151): 1003—1026. doi:10.1090/S0025-5718-1980-0572872-7.

[9] Jaeschke, Gerhard (1993), „On strong pseudoprimes to several bases”, Mathematics of Computation, 61 (204): 915—926, doi:10.2307/2153262

[10] The Primes Page

[11] Zhang, Zhenxiang & Tang, Min (2003), „Finding strong pseudoprimes to several bases. II”, Mathematics of Computation, 72 (44): 2085—2097, doi:10.1090/S0025-5718-03-01545-X

[12] Шаблон:SloanesRef

[13] SPRP Records

[14] {{Citation |last=Alford|first=W. R. |last2=Granville |first2=A. |last3=Pomerance |first3=C. |lastauthoramp= |year=1994 |title=On the difficulty of finding reliable witnesses |journal=Lecture Notes in Computer Science |volume=877 |publisher=Springer-Verlag |url=http://www.math.dartmouth.edu/~carlp/PDF/reliable.pdf |doi=10.1007/3-540-58691-1_36 |id=}

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]