Ẹ̀rọ Ìdánwò Òǹkà Àkọ́kọ́ Miller-Rabin

Nípa ẹ̀rọ ìṣirò yìí

Ìdánwò Miller-Rabin ń ṣàyẹ̀wò bóyá òǹkà jẹ́ àkọ́kọ́ nípa kíkọ n − 1 bí 2ˢ·d pẹ̀lú d jẹ́ àìdọ́gba, lẹ́yìn náà ó ń dán an wò bóyá ìpìlẹ̀ ẹlẹ́rìí a ń tẹ́ aᵈ ≡ 1 (mod n) tàbí a^(2ʳ·d) ≡ −1 (mod n) fún r kan tí r < s. Ẹlẹ́rìí kan ṣoṣo ń fún ni èsì ìṣeéṣe nìkan, ṣùgbọ́n dídán an wò pẹ̀lú àkójọ kékeré àwọn ìpìlẹ̀ ẹlẹ́rìí tí a ti fi hàn pé ó dájú (fún àpẹẹrẹ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) ń mú kí ìdánwò náà jẹ́ onídájú fún gbogbo odindi tí ó kéré ju nǹkan bí 3.18 × 10²³ lọ — ó jìnnà ju ohun tí ọ̀pọ̀ ohun èlò yóò nílò lọ.

Àwọn onímọ̀ cryptography àti àwọn olùgbéjáde sọ́fítíwia ń lo irú ìdánwò yìí gan-an nígbà tí wọ́n bá ń dá àwọn olùdíje àkọ́kọ́ ńlá fún àwọn kọ́kọ́rọ́ RSA tàbí Diffie-Hellman, àwọn akẹ́kọ̀ọ́ sáyẹ́ǹsì kọ̀ǹpútà sì ń lò ó láti rí lórí àwọn òǹkà gidi bí Miller-Rabin ṣe dára ju pípín ìgbìyànjú lọ fún ṣíṣàyẹ̀wò bóyá odindi ńlá jẹ́ àkọ́kọ́.