Miller-Rabin 素性测试算法需要如下两个引理：
1. 费马小定理
设 \(p\) 是素数，\(a\) 为整数，且 \((a,p)=1\)，则 \(a^{p-1}\equiv1\pmod{p}\)
证明:考虑 \(1,2,3,\dots,(p-1)\) 这 \(p-1\) 个数字，同时乘 \(a\) 得 \(a,2a,3a,\dots,(p-1)a\)。
Miller-Rabin 素性测试算法需要如下两个引理：
设 \(p\) 是素数，\(a\) 为整数，且 \((a,p)=1\)，则 \(a^{p-1}\equiv1\pmod{p}\)
证明:考虑 \(1,2,3,\dots,(p-1)\) 这 \(p-1\) 个数字，同时乘 \(a\) 得 \(a,2a,3a,\dots,(p-1)a\)。