Jelaskan Bukti kebenaran dari Algoritma Berlekamp–Rabin

Algoritma menemukan faktorisasi  dalam semua kasus, kecuali ketika semua bilangan  adalah residu kuadrat atau non-residu secara bersamaan. Menurut teori siklotomi, peluang kejadiannya untuk kasus ketika  juga merupakan semua residu atau non-residu secara bersamaan (yaitu, ketika  tidak berhasil) diestimasi sebagai , untuk  adalah jumlah nilai yang berbeda dalam . Dengan cara ini, bahkan untuk kasus galat  dan , maka estimasi peluang galatnya adalah , dan untuk kasus akar kuadrat modular, probabilitas galat setidaknya bernilai .