Miller-rabin检验法也是一个多项式时间算法, 它比 Solovay- Strassen检验法快,执行一次的 错误概率最多为1/4 ■对于奇整数n的 Miller-Rabin素性测试算法如 下 (1)令n-1=2km,m是奇数; ■(2)对i=1 to t do ①选择随机整数a(2≤a≤n-2); ②计算b= ammon; ③Ifb=modn, then n是素数and返回,else ④ If j=k then n是合数,算法终止 oIfb=1modn, then n是素数and返回, else计算b=b2modm,j=j计1,goto④ 23:31:4823:31:48  Miller-Rabin检验法也是一个多项式时间算法， 它比Solovay-Strassen检验法快，执行一次的 错误概率最多为1/4 。  对于奇整数 n 的Miller-Rabin素性测试算法如 下：  (1) 令n-1=2 k m，m是奇数；  (2) 对i=1 to t do  ①选择随机整数a(2  a n-2)；  ②计算 b  a mmodn;  ③If b 1modn，then n是素数 and 返回,else 令j=1  ④If j=k then n是合数，算法终止  ⑤If b -1modn, then n是素数 and 返回，  else 计算 b  b 2modn, j=j+1,goto ④