robin miller素性检测

2018-10-08  本文已影响18人  已不再更新_转移到qiita

2^{256} - 2^{32} - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 -1=

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大的超出了想象

下一步的方案

我们可以找到 \sqrt{Pcurve} 内的质数,
欲找到 \sqrt{Pcurve}内的质数,先找到\sqrt{ \sqrt{Pcurve} }内的质数,
欲找到\sqrt{ \sqrt{Pcurve} }内的质数,先找到\sqrt{\sqrt{ \sqrt{Pcurve}}}内的质数,

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

😶😶😶😶😶😶

使用openssl检测素数

openssl prime 115792089237316195423570985008687907853269984665640564039457584007908834671663

0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F is prime


参考:

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

上一篇 下一篇

猜你喜欢

热点阅读