Ҳисобкунаки санҷиши соддагии Миллер-Рабин

Дар бораи ин ҳисобкунак

Санҷиши Миллер-Рабин содда будани ададро бо навиштани n − 1 ҳамчун 2ˢ·d бо d тоқ месанҷад, сипас месанҷад, ки оё пояи шоҳид a ба aᵈ ≡ 1 (mod n) ё a^(2ʳ·d) ≡ −1 (mod n) барои баъзе r < s мувофиқат мекунад. Як шоҳиди ягона танҳо натиҷаи эҳтимолиро медиҳад, аммо санҷиш бо маҷмӯи хурд ва исботшудаи пояҳои собити шоҳид (масалан, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37) санҷишро барои ҳар адади бутун аз тақрибан 3,18 × 10²³ камтар детерминистӣ мекунад — хеле дуртар аз он, ки аксари барномаҳо ҳамеша лозим доранд.

Криптографҳо ва таҳиягарони нармафзор дақиқан чунин санҷишро ҳангоми тавлиди номзадҳои бузурги ададҳои сода барои калидҳои RSA ё Diffie-Hellman истифода мебаранд, ва донишҷӯёни илмҳои компютерӣ онро барои дидани он дар ададҳои воқеӣ истифода мебаранд, ки чаро Миллер-Рабин барои санҷидани сода будани адади бутуни калон аз тақсими озмоишӣ ин қадар беҳтар миқёс мегирад.