Jelaskan Kompleksitas dari Algoritma Berlekamp–Rabin

Misalkan suatu polinomial merupakan polinomial berderajat , maka kompleksitas algoritma dapat diturunkan sebagai berikut:

Karena menurut teorema binomial mengatakan bahwa , maka dapat dilakukan transisi dari  ke  dalam waktu .

Perkalian polinomial dan mengambil sisa dari satu polinomial yang modulo dengan yang lain dapat dilakukan di . Jadi, perhitungan  dilakukan di .

Eksponensial biner bekerja di .

Mengambil  dari dua polinomial melalui algoritma Euklides yang bekerja di .

Jadi, seluruh prosedur dapat dilakukan di . Dengan menggunakan transformasi Fourier cepat dan algoritma setengah-FPB, maka kompleksitas algoritmanya dapat ditingkatkan menjadi . Untuk kasus akar kuadrat modular, derajatnya adalah , sehingga seluruh kompleksitas algoritma dalam kasus tersebut dibatasi dengan  per iterasi.