Jelaskan Uji primalitas Miller–Rabin dari Teorema kecil Fermat

Uji primalitas Miller–Rabin menggunakan ekstensi teorema kecil Fermat berikut:

Jika  adalah bilangan prima ganjil, dan , dengan  ganjil, lalu untuk setiap  prima hingga , yaitu , atau  sehingga  dan

Hasil ini dapat disimpulkan dari teorema kecil Fermat dengan fakta bahwa, jika  adalah bilangan prima ganjil, maka bilangan bulat modulo  membentuk medan berhingga, di mana  adalah 1 dengan -1.

Uji Miller–Rabin menggunakan properti ini dengan cara berikut:{math|1=p =  2s  d + 1}}, dengan  ganjil, bilangan bulat ganjil yang primalitasnya harus diuji, pilih secara acak  sehingga ; maka ; jika  bukan 1 atau −1, maka kuadratkan berulang kali modulo  sampai Anda mendapatkan 1, −1, atau telah mengkuadratkan  kali. Jika  dan −1 belum diperoleh, maka  bukan bilangan prima. Jika tidak,  mungkin bilangan prima atau tidak. Jika  bukan bilangan prima, probabilitas hal ini dibuktikan dengan pengujian lebih tinggi dari 1/4. Oleh karena itu, setelah  uji acak non-konklusif, probabilitas bahwa  bukan bilangan prima lebih rendah dari , dan karenanya dapat dibuat serendah yang diinginkan, dengan meningkatkan .

Singkatnya, pengujian tersebut membuktikan bahwa suatu bilangan bukan bilangan prima, atau menyatakan bahwa bilangan tersebut adalah bilangan prima dengan probabilitas kesalahan yang dapat dipilih rendah.

Tes ini sangat sederhana untuk diterapkan dan secara komputasi lebih efisien daripada semua tes deterministik yang diketahui. Oleh karena itu, biasanya digunakan sebelum memulai pembuktian keutamaan.