Изворни код странице Милер–Рабинов тест

'''Милер–Рабинов тест''' је тест који проверава да ли је дати број прост, слично [[Фермаов тест за просте бројеве|Фермаовом тесту за просте бројеве]] и [[Соловеј–Штрасенов тест|Соловеј–Штрасеновом тесту]]. Оригинална верзија теста, који је осмислио [[Гари Милер (професор)|Гари Милер]], детерминистичког је типа, али се детерминизам заснива на општијој Римановој хипотези;<ref name="miller">{{Citation |last=Miller|first=Gary L. |year=1976 |title=Riemann's Hypothesis and Tests for Primality |journal=Journal of Computer and System Sciences |volume=13 |issue=3 |doi=10.1145/800116.803773| pages = 300–317}}</ref> [[Мајкл О. Рабин]] је модификовао тест тако да добије безусловни пробабилистички алгоритам.<ref name="rabin">{{Citation |last=Rabin|first=Michael O. |year=1980 |title=Probabilistic algorithm for testing primality |journal=Journal of Number Theory |volume=12 |issue=1 |doi=10.1016/0022-314X(80)90084-0| pages = 128–138}}</ref>

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

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

:<math>x^{2} \equiv 1\pmod{p} </math>
:<math> (x - 1)( x + 1) \equiv 0\pmod{p}.</math>
Другим речима, прост број ''p'' дели производ {{nowrap|(''x'' − 1)(''x'' + 1).}} По [[Еуклидова лема|Еуклидовој леми]] он дели и факторе од {{nowrap|''x'' − 1}} или од{{nowrap|''x'' + 1,}}, дакле ''x'' је конгурентно са 1 или 1 по модулу''p''.

Нека је ''n'' прост број и нека је ''n'' > 2. Следи да {{nowrap|''n'' − 1}} је паран и да можемо га написати као 2<sup>''s''</sup>·''d'', где су ''s'' и ''d'' позитивни цели бројеви (при чему је ''d'' прост). За свако ''a'' у ('''Z'''/''n'''''Z''')*, важи
:<math>a^{d} \equiv 1\pmod{n}</math>
или
:<math>a^{2^r\cdot d} \equiv -1\pmod{n}</math>
за неко 0 ≤ r ≤ ''s'' − 1.

Да би показали да је ово тачно користићемо [[мала Фермаова теорема|малу Фермаову теорему]], која каже да за прост број ''n'' важи:
:<math>a^{n-1} \equiv 1\pmod{n}.</math>

По леми одозго, ако наставимо да узимамо корене од ''a''<sup>''n''−1</sup>, добиће се или 1 или −1. Ако се добије −1 онда друга једнакост важи и ту је крај. Иначе, ако никад не добијемо −1, онда смо узели све степене 2 и остала нам је прва једнакост.

Милер–Рабинов тест се заснива на контрапозицији тврћења изнад. То јест, ако можемо да нађемо ''a'' такво да важи
:<math>a^{d} \not\equiv 1\pmod{n}</math>
и
:<math>a^{2^rd} \not\equiv -1\pmod{n}</math>
за све 0 ≤ r ≤ ''s'' − 1, онда ''n'' није прост број. Такво ''a'' зовемо сведоком сложености од ''n''. Иначе ''a'' се зове''јаким лажовом'', и ''n'' је снажан вероватан прост број у бази ''a''. Назив "јак лажов" се односи на случај где је ''n'' [[сложен број]], али свеједено једнакости(својства) важе као и да је прост.

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

За тестирање великих бројева, уобичајно је да се изабере случајна база ''a'', а приори, ми не знамо расподелу сведока и лажова код бројева 1, 2, ..., ''n'' − 1. Наручито, Арно<ref name="Arnault397Digit">{{cite journal|title=Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases |journal=Journal of Symbolic Computation|date=август 1995|volume=20|issue=2|author=F. Arnault |url=http://www.sciencedirect.com/science/article/pii/S0747717185710425 |doi=10.1006/jsco.1995.1042| pages = 151–161}}</ref> је дао сложен број од 397 цифара за који све базе од ''a'' које су мање од 307 цифара су јаки лажови. Као и очекивано, овај број је пријављен као прост од стране [[Maple (software)|Maple]] <code>isprime()</code> функције, која имплементира Милер–Рабинов тест проверавајући специфичне базе 2, 3, 5,7 и 11. Но, одабир неколико специфичних база може загарантовати проверу сложених бројева за ''n'' мањих од максимума одрећеног тим базама. Овај максимум је обично доста велик у односу на базе. Како случајне базе немају такав детерминизам за мало ''n'', специфичне базе су боље у неким условима.

== Примери ==
Уколико бисмо хтели да проверимо да ли је ''n''&nbsp;=&nbsp;221 прост број, прво би написали {{nowrap|''n'' − 1 {{=}} 220}} као 2<sup>2</sup>·55, тако да је ''s''&nbsp;=&nbsp;2 и ''d''&nbsp;=&nbsp;55. Насумично изаберемо ''a'' тако да 0&nbsp;<&nbsp;''a''&nbsp;<&nbsp;''n'', нпр. ''a'' = 174. Даље:
* ''a''<sup>2<sup>0</sup>·''d''</sup> mod ''n'' = 174<sup>55</sup> mod 221 = 47 ≠ 1, ''n'' − 1
* ''a''<sup>2<sup>1</sup>·''d''</sup> mod ''n'' = 174<sup>110</sup> mod 221 = 220 = ''n'' − 1.

Пошто је 220 ≡ −1 mod ''n'', онда је 221 прост, или 174 је јак лажов за 221. Пробамо са још једним насумично изабраним ''a'', овај пут нпр. ''a'' = 137:
* ''a''<sup>2<sup>0</sup>·''d''</sup> mod ''n'' = 137<sup>55</sup> mod 221 = 188 ≠ 1, ''n'' − 1
* ''a''<sup>2<sup>1</sup>·''d''</sup> mod ''n'' = 137<sup>110</sup> 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<sup>''s''</sup>·''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''<sup>''d''</sup> mod ''n''
    if ''x'' = 1 or ''x'' = ''n'' − 1 then do next WitnessLoop
    repeat ''s'' − 1 times:
       ''x'' ← ''x''<sup>2</sup> mod ''n''
       if ''x'' = 1 then return ''composite''
       if ''x'' = ''n'' − 1 then do next WitnessLoop
    return ''composite''
 return ''probably prime''
 
Користећи модуларно степеновање -{({{nowrap|''c'' ≡ ''b''<sup>''e''</sup> (mod ''m''}}))}- помоћу алгоритма брзог степеновања квадрирањем, време извршавања овог алгоритма је [[Велико О|О]]-{(''k''&nbsp;log<sup>3</sup>''n'')}-, где је ''-{k}-'' број различих вредности броја ''-{a}-'' којег тестирамо; тако да је ово један ефикасан алгоритам који ради у полиномијалном времену. Користећи [[множење]] засновано на [[Брза Фуријеова трансформација|брзим Фуријеовим трансофрмацијама]] време извршавања се скраћује на -{{{nowrap|O(''k'' log<sup>2</sup>''n'' log log ''n'' log log log ''n'')}} = Õ(''k''&nbsp;log<sup>2</sup>''n'')}-.
 
Ако убацимо израчунавање [[Највећи заједнички делилац|највећег заједничког делиоца]] (НЗД) у горенаведени алгоритам, можемо понекад да добијемо и чиниоце броја ''-{n}-'' него да само утврдимо да ли је ''-{n}-'' сложен. Посебно, ако је ''-{n}-'' вероватан прост за основу ''-{a}-'' али не и јак вероватан прост за основу ''-{a}-'', или {{nowrap|НЗД((-{''a''<sup>''d''</sup> mod ''n'') − 1, ''n''}-)}} или (за неко ''-{r}-'' из горенаведеног опсега) {{nowrap|НЗД-{((''a''<sup>2<sup>r</sup>·''d''</sup> mod ''n'') − 1, ''n'')}-}} даје (не обавезно прост) чинилац броја ''-{n}-'';видети страницу 1402.<ref name="baillie">{{cite journal|author2=[[Samuel S. Wagstaff, Jr.]]|title=Lucas Pseudoprimes|journal=Mathematics of Computation|date=октобар 1980|volume=35|issue=152|url=http://mpqs.free.fr/LucasPseudoprimes.pdf|last=Baillie|first=Robert| mr=583518| doi=10.1090/S0025-5718-1980-0583518-6| pages = 1391–1417}}</ref> Ако је факторисање циљ, онда се ова НЗД израчунавања могу убацити у алгоритам по без превеликих губитака брзине израчунавања.
 
На пример, рецимо да је ''-{n}-'' = 341. Даље је {{nowrap|''-{n}-'' − 1 {{=}} 85·4.}}. Затим {{nowrap|2<sup>85</sup> -{mod 341}- {{=}} 32.}} Ово нам говори да ''-{n}-'' није јак вероватан прост број основе 2, па знамо да је ''-{n}-'' сложен. Ако примени НЗД у овом кораку, добијамо чинилац од 341: {{nowrap|НЗД((2<sup>85</sup> -{mod}- 341) − 1, 341) {{=}} 31.}} Ово је исправно јер 341 је псеудо прост у основи 2, али није и јак псеудопрост у основи 2.
 
У случају да алгоритам врати „сложен“ јер ''-{x}-'' = 1, уједно је и откривено да је ''-{d}-''2<sup>''-{r}-''</sup> (непаран умножак) [[Ред (теорија група)|реда]] броја ''-{a}-'' -чињеница која може (као и у [[Шоров алгоритам|Шоровом алгоритму]]) да се искористи да се ''-{n}-'' факторише, јер ''-{n}-'' онда дели
:<math>a^{d 2^r} - 1 = (a^{d 2^{r-1}} - 1) (a^{d 2^{r-1}} + 1)</math>
али не и сваки фактор сам по себи. Разлог због ког Милер–Рабинов тест ''не даје'' пробабилистички алгоритам за [[Rastavljanje na faktore|факторизацију]] је то што ако
:<math>a^{n-1} \not\equiv 1 \pmod{n}</math>
(другим речима, ''-{n}-'' није псеудопрост за основу ''-{a}-''), онда никакава информација тог типа није добијена о периодичности броја ''-{a}-'', и онда алгоритам бира други „-{return composite}-“ излаз.

== Тачност теста ==
Што више база ''а'' тестирамо, већа је тачност теста. Може се показати да ће за сваки непаран сложен број ''-{n}-'' бар 3/4 база ''а'' бити сведоци за сложеност од ''-{n}-''.<ref name="rabin"/><ref name="schoof">{{Citation |last=Schoof|first=René |year=2004 |chapter=Four primality testing algorithms |title=Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography |publisher=Cambridge University Press |location= | url=http://www.mat.uniroma2.it/~schoof/millerrabinpom.pdf |isbn=978-0-521-80854-5|pages=}}</ref> Милер–Рабинов тест је строго јачи од Соловеј—Штрасеновог теста прималности у смислу да је за сваки сложени број ''-{n}-'', скуп јаких лажова за ''-{n}-'' подскуп скупа Ојлерових лажова за број ''-{n}-'', и за многе ''-{n}-'' тај потскуп је садржан у целини. Ако је ''-{n}-'' сложено онда Милер–Рабинов тест тврди да је ''-{n}-'' прост са вероватноћом од највише 4<sup>−''-{k}-''</sup>. Са друге стране, Соловеј—Штрасенов тест прималности тврди да је ''-{n}-'' прост са вероватноћом од највише 2<sup>−''-{k}-''</sup>.
 
Битно је приметити да многим уобичајеним применама овог алгоритма, нас не занима опсег грешке који је овде горенаведен. Тај опсег грешке представља вероватноћу да се сложен број прогласи за могућ прост број после ''-{k}-'' кругова тестирања. Уместо тога, често нас занима вероватноћа да ли је, прошавши ''-{k}-'' кругова тестирања, број који испитујемо заправо сложен. Формално, ако ми назовемо догађај проглашавања ''-{n}-'' за могућ прост број после ''-{k}-'' кругова Милер–Рабина назовемо ''Y<sub>k</sub>'', и ако назовемо догађај тога да је ''-{n}-'' сложен број ''-{X}-'' (И обележимо догађај тога да је ''-{n}-'' прост <math>\overline{X}</math>), онда нам горенаведен опсег даје <math>P(Y_k | X)</math>, док са друге стране нас занима <math>P(X | Y_k)</math>. [[Бајесова теорема]] нам даје начин да повежемо ове две условне вероватноће, наиме
:<math>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})}</math>.
 
Ово нам говори да вероватноћа која нас често занима није везана само за опсег од 4<sup>−''-{k}-''</sup>, али и за вераватноће које су везане за густину простих бројева у околини броја ''-{n}-''.
 
Додатно, за велике вредности броја ''-{n}-'', вероватноћа да је сложен број проглашен као ''вероватно прост'' је у просеку знатно мања од 4<sup>−''-{k}-''</sup>. Дамгорд, Лендрок и Померанс<ref>{{Citation |last=Damgård|first=I. |last2=Landrock |first2=P. |last3=Pomerance |first3=C. |lastauthoramp=yes |year=1993 |title=Average case error estimates for the strong probable prime test |journal=Mathematics of Computation |volume=61 |issue=203 |url=http://www.math.dartmouth.edu/~carlp/PDF/paper88.pdf |issn= |doi=10.2307/2152945| pages = 177–194}}</ref> су израчунали неке експлицитне опсеге и пружају метод за разуман избор броја ''-{k}-'' да би се добио жељени опсег грешке. Такви опсези могу, на приmер, да се искористе да ''генеришу'' вероватне просте бројеве; ипак, не би се требало користити да ''потврђују'' просте бројеве непознатог порекла, јер у [[Криптографија|криптографској]] примени ''непријатељ'' може да покуша да вам пошаље [[псеудопорст]] број тамо где је потребан прост број. у таквим случајевима, може се ослонити само на опсег грешке од 4<sup>−''-{k}-''</sup>.

== Детерминистичке варијанте теста ==
Милер–Рабинов тест се може учинити детерминистичким тако што се проба за свако могуће ''-{a}-'' испод одређене границе. Проблем је углавно да се одреди граница тако да је тест још увек поуздан.
 
Ако је број ''-{n}-'' који се тестира сложен, јаки лажови ''-{a}-'' који су узајамно прости са ''-{n}-'' се садрже у строго мањој подгрупи групе ('''-{Z}-'''/''-{n}-'''''-{Z}-''')*, што значи да ако ми тестирамо свако ''-{a}-'' из скупа који [[Генеришући подскуп|генерише]] ('''-{Z}-'''/''-{n}-'''''-{Z}-''')*,, један од њих мора бити сведок сложености броја ''-{n}-''. Претпостављајући тачност [[Уопштена Риманова хипотеза|уопштене Риманове хипотезе]], зна се да групу генеришу њени елементи мањи од -{O((log&nbsp;''n'')<sup>2</sup>)}-, што је Милер и сам био приметио.<ref name="miller"/> Ерик Бах је смањио константу која се била користила у [[Велико О|Велико О нотацији]] на 2<ref>{{Citation |last=Bach|first=Eric |year=1990 |title=Explicit bounds for primality testing and related problems |journal=Mathematics of Computation |volume=55 |issue=191 |doi=10.2307/2008811 |issn=| pages = 355–380}}</ref>. То нас доводи до следећег алгоритма за тестирање условне прималности:
 '''Input''': ''n'' > 1, an odd integer to test for primality.
 '''Output''': ''composite'' if ''n'' is composite, otherwise ''prime''
 write ''n''−1 as 2<sup>s</sup>·''d'' by factoring powers of 2 from ''n''−1
 repeat for all <math>a \in [2,\min(n-1,\lfloor2(\ln n)^2\rfloor)]</math>:
     if <math>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]</math>
     then return ''composite''
 return ''prime''
 
Време извршавања алгоритма је -{Õ((log&nbsp;''n'')<sup>4</sup>)}- (са множењем заснованим на [[Брза Фуријеова трансформација|брзим Фуријеовим трансофрмацијама]]). Нису потребне све ставке уопштене Риманове хипотезе да би се осигурала тачност теста. Пошто радимо са подгрупама парног [[Индекс (Теорија група)|индекса]], довољно је претпоставити тачност [[Лежандров симбол|квадратних]] [[Дирихлеов карактер|Дирихлеових карактера]].<ref name="schoof"/>
 
Милеров тест (горе приказан алгоритам) се не користи у пракси. У већини случајева, коришћење пробабилистичког Милер–Рабиновог теста или [[Бејли--{PSW}- тест прималности|Бејли--{PSW}- теста прималности]], даје довољну тачност радећи много брже. Такође је спорији у пракси него уобичајно коришћени методи доказивања као што су [[Ејдлман-Померанс-Рамли тест прималности|Ејдлман-Померанс-Рамлијев тест прималности]], и [[доказивање прималности елиптичком кривом]] који дају резултате који се не ослањају на недоказане претпоставке.
 
Када је број ''-{n}-'' који тестирамо довољно мали, није потребно испробати свако ''-{a}-'' за које важи -{{{nowrap|''a'' < 2(ln ''n'')<sup>2</sup>}}}-, јер је познато да су мањи скупови могућих сведока довољни. На пример, Померанс, Селфриџ и Вегстаф<ref name="PSW">{{cite journal|author2=[[John L. Selfridge]], [[Samuel S. Wagstaff, Jr.]]|title=The pseudoprimes to 25·10<sup>9</sup>|journal=Mathematics of Computation|date=јул 1980|volume=35|issue=151|url=http://www.math.dartmouth.edu/~carlp/PDF/paper25.pdf|last=Pomerance|first=Carl|authorlink=Carl Pomerance| doi=10.1090/S0025-5718-1980-0572872-7| pages = 1003–1026}}</ref> и Јешке<ref>{{Citation |last=Jaeschke|first=Gerhard |last2= |first2= |last3= |first3= |lastauthoramp= |year=1993 |title=On strong pseudoprimes to several bases |journal=Mathematics of Computation |volume=61 |issue=204 |doi=10.2307/2153262 |issn=| pages = 915–926}}</ref> су потврдили да
 
* Ако је ''-{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;
 
Треба напоменути да се Милер–Рабинови псеудопрости бројеви називају [[Снажни псеудопрости бројеви]].
 
Други критеријуми ов врсте постоје<ref>{{Citation |url=http://primes.utm.edu/prove/prove2_3.html |title=The Primes Page}}</ref><ref>{{Citation |last=Zhang|first=Zhenxiang |last2=Tang |first2=Min |lastauthoramp=yes |year=2003 |title=Finding strong pseudoprimes to several bases. II |journal=Mathematics of Computation |volume=72 |issue=44 |doi=10.1090/S0025-5718-03-01545-X| pages = 2085–2097}}</ref><ref>{{SloanesRef | sequencenumber=A014233 |name=Smallest odd number for which Miller-Rabin primality test on bases <= n-th prime does not reveal compositeness}}</ref><ref>{{Citation |url=//miller-rabin.appspot.com |title=SPRP Records}}</ref> и ови резултати дају веома брзе детерминистичке тестове прималности за бројеве и прхватљивом опсегу, а без икаквих претпоставки.
 
Постоји мала листа могућих сведока за сваку могућу величину уноса (највише ''-{n}-'' вредности за ''-{n}-''-то битне бројеве). Ипак, ниједан коначан скуп база није довољан за све сложене бројеве. Алфорд, Гренвил и Померанс су показали да постоји бесконачно много сложених бројева ''-{n}-'' чији је најмањи сведок сложености величине бар -{{{nowrap|(ln ''n'')<sup>1/(3ln ln ln ''n'')</sup>}}}-.<ref><nowiki>{{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=</nowiki>[[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=}</ref> Они такође хеуристичким методама аргументују да би најмањи број ''-{w}-'' такав да сваки сложен број мањи од ''-{n}-'' има сведока сложености мањег од ''-{w}-'' требало да буде реда величине {{nowrap|-{Θ}-(log ''n'' log log ''n'').| pages = 1–16}}

== Референце ==
{{reflist|2}}
 
== Спољашње везе ==
* {{MathWorld|urlname=Rabin-MillerStrongPseudoprimeTest|title=Rabin-Miller Strong Pseudoprime Test}}
* [http://gandraxa.com/miller_rabin_primality_test.xml Интерактивна онлајн имплементација детерминистичке варијанте] (Корак по корак приказ рада алгортима)
* [http://www.informationsuebertragung.ch/indexAlgorithmenRabinMiller.html Аплет(Немачки)]
* [http://stackoverflow.com/questions/4236673/sample-code-for-fast-primality-testing-in-c-sharp/4236870#4236870 Милер–Рабинов тест прималности у -{C#}-]
* [http://www.javascripter.net/math/primes/millerrabinprimalitytest.htm Милер–Рабинов тест прималности у Јаваскрипту користећи аритметику арбитрарне прецизности]

{{нормативна контрола}}

[[Категорија:Тестови прималитета]]
[[Категорија:Коначна поља]]