Fermat素性检验算法 算法描述 给定奇整数m>=3和安全参数k 随机选取整数a，2<=a<=m-2 计算g=(a,m)，如果g=1，转 3. ；否则，跳出，m为合数 计算r=a^(m-1)(mod m)，如果r=1，m可能是素数，转 1. ；否则，跳出，m为合数 重复上述过程k次，如果每次得到m可能为素数，则m为素数的概率为 1-1/2^k