Miller-Rabin素数测试法 学习笔记

一般情况下判断一个数是不是质数时间复杂度是 $O(\sqrt{n})$，用 $Miller-Rabin$ 素数测试法可以降低时间复杂度。

前置知识

$1.$ 费马小定理 $:$ 当 $p$ 为素数，且 $gcd(a,p)=1$，有 $a^{p-1}\equiv 1(\mathrm{mod}p)$，这是 $p$ 为素数的必要不充分条件。

$2.$ 二次探测定理 $:$ 当 $p$ 为素数，且 $0<x<p$，则方程 $x\equiv 1($