robin miller素性检测

115792089237316195423570985008687907853269984665640564039457584007908834671663
是个质数吗？

测试

测试100是否为质数
只需要测试 [2, sqrt(100) ] 区间的数能被100整除否

100/10 = 10
100/5 = 20
100/20 = 5
这算是某种 “对称性”吧

更快速的方法是：求得[2, sqrt(100)]区间的所有质数，能否被100整除否，既然取质数，偶数除了2以外，都不是质数

rane(start, end, step)， 所有step可以为2

记得有一种筛选法寻找质数，
剔除2的倍数，3的倍数，5的倍数，7的倍数 ...... 依次类推

ruby 有特殊的技巧

require 'prime'

Pcurve = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 -1

Prime.each(10).to_a  #10以内的质数表
# [2, 3, 5, 7]

Prime.each(10).to_a.size #10以内的质数数量
# 4

Prime.each(100000000).to_a.size() #100000000以内的质数数量
# 5761455

Prime.prime?(7) # 7是质数么
# true

Prime.prime?(Math.sqrt(Pcurve).to_i) 
# 340282366920938463463374607431768211456 是质数么
# false, 速度很快

Prime.prime?(Pcurve)
# 10分钟后还在计算

Pcurve 难以想象的大

python script

按照以上想法做个实现

#coding:utf-8

import math

Pcurve = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 -1
 
def _sqrt(x):
    r = int(math.sqrt(x))
    return r

def is_prime():
    for i in range(2, _sqrt(Pcurve), 2):
        if (Pcurve % i) == 0:
            print(Pcurve," is not a prime number")
            print(i," times",Pcurve//i,"is",Pcurve)
            break
        else:
            print(Pcurve,"is a prime number")


if __name__ == '__main__':
    is_prime()

代码不能运行，提示 OverflowError: range() result has too many items，直接溢出了。

这就是感觉上很简单，验证却比较困难的问题。

Pcurve大的超出了想象

下一步的方案

我们可以找到 内的质数，
欲找到 内的质数，先找到内的质数，
欲找到内的质数，先找到内的质数，

如果想更快，就需要了解数论方面的研究了

😶😶😶😶😶😶

使用openssl检测素数

openssl prime 115792089237316195423570985008687907853269984665640564039457584007908834671663

0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F is prime

---

参考：

https://github.com/ruby/prime
http://www.matrix67.com/blog/archives/234