若为奇数（这里可以考虑去掉3甚至5的倍数），则先求出d。

对于每一个底a，让d不断乘以2直到为(p-1)/2，

在此过程中（包括原本的d与d=(p-1)/2时的情况），

设t为a的d次方模p的余数，

（1）当t=-1时跳出，声明p有可能为素数

（2）当t=1时，若d为奇数，跳出声明p有可能为素数，否则跳出声明p必为合数

（3）当d=(p-1)/2时跳出，声明p必为合数。