一、素性检测、大数生成概览

1、Miller-Rabin素数检测算法

用来快速判断一个数是不是素数.
1、费马小定理：如果n是素数，则$$a ^ {n - 1}$$ % n 等于 1。
2、快速模取幂
米勒-拉宾算法就是结合上面两种，通过不断判断fmod(a, n - 1, n)的值是否为1来判断。这是一个概率算法，如果为1，不一定为素数，不为1，则必定是合数。循环判断多次就会让概率变得极为的小。

2、大素数生成：

大素数随机生成原理是，随机生成一个大素数，检测其是否为素数，如果是则输出，否则继续生成。

二、数学理论基础

0、Wilson定理:

给出了一个数n是素数的充要条件 (n-1)! ≡ -1 (mod n)
计算量太大，不现实

1. 费马小定理：

假如p是质数，a是整数，且a、p互质，那么a的(p-1)次方除以p的余数恒等于1，即：$$a^{p-1}$$≡1(mod p).
但是反过来却不一定成立，就是说，如果a、p互质，且$$a^{p-1}$$≡1(mod p)，不能推出p是质数，比如Carmichael数。

2. 二次探测定理：

如果p是一个素数，0<x<p,则方程$$x^2$$≡1(mod p)的解为x=1或x=p-1。

大素数1.jpg
若x>p, 则结果为x mod p = 1 或 -1 (即p-1)
(因为x*x mod p = 1, 根据模运算可乘性性质， x mod p = 1 或 -1)

3. 模运算的规则：

$$(a \times b)\%n=(a\%n \times b\%n)\%n$$

4. 快速积取模、快速幂取模：

快速幂算法（蒙哥马利算法）
http://139.196.53.116/ml/index.php/archives/173/

5、Miller-Rabin算法原理

$$a^{n-1}=a^{2^q \times m}=a^{2^{q-1}\times 2 \times m}={(a^{2^{q-1} \times m})}^2$$
大素数2.jpg

三、Miller-Rabin素数检测算法

对于要判断的数n:
1.先判断是不是2，是的话就返回true。
2.判断是不是小于2的，或合数，是的话就返回false。
3.令$$n-1=u*2^t$$求出u,t 其中u是奇数。
4.随机取一个a,且1<a<n
/*根据费马小定理，如果$$a^{n-1}$$≡1(mod p)
那么n就极有可能是素数，如果等式不成立，那肯定不是素数了
因为$$n-1=u\times 2^t$$所以$$a^{n-1}=a^{u\times 2^t}=(a^u)^{2^t}$$。*/
5.所以我们令$$x=a^u\ mod\ n $$
6.然后是t次循环，每次循环都让$$y=(x^2)\ mod\ n,x=y$$这样t次循环之后$$x=a^{u\times 2^t}=a^{n-1}$$了
7.因为循环的时候$$y=(x\times x)\ mod\ n$$ 且x肯定是小于n的，正好可以用二次探测定理:
如果$$(x^2)$$%n==1 也就是y等于1的时候，假如n是素数，那么x==1||x==n-1
如果x!=1&&x!=n-1 那么n肯定不是素数了，返回false。
(这里只要第一次$$a^u$$判断是否为1就行，后面平方后只需判断是否为n-1，因为第一次不为1，后面只要不是p-1就不能模1)
8.运行到这里的时候$$x=a^{n-1}$$根据费马小定理，x!=1的话，肯定不是素数了，返回false
9.因为Miller-Rabin得到的结果的正确率为 75%，所以要多次循环步骤4~8来提高正确率
10.循环多次之后还没返回，那么n肯定是素数了，返回true

四、大质数生成源码

满足p|q的两个大素数，通过p不好找q。不如反过来先随机产生q。q乘以一个偶数再加一，因为数越大，素数越多。用这种方法找到满足p|q的速度还是很快的。我用的512位的随机数，这样的到的p极大概率是1024位的。如果不是1024位，舍弃再产生一个新的就好了。
先生成随机数x
将x变为偶数 if x % 2 == 1: x = x+1
在用q乘以x+1 判段是否为素数，是否符合位数要求

import random
def generateLargePrime(keysize=512):
    '''生成一个大素数，默认生成512位大素数。'''
    while True:
        num = random.randrange(2 ** (keysize - 1), 2 ** keysize)
        if isPrime(num):
            return num
def generateLargePrime1(q,keysize=512):
    while True:
        x=random.randrange(2 ** (keysize - 1), 2 ** keysize)
        if x % 2 == 1:
            x = x+1
        num1 = (q-1) * x+1

        if isPrime(num1)  :
            return num1
p = generateLargePrime()
q = generateLargePrime1(p)
print(p)
print(q)

五、Miller-Rabin素数检测源码

def millerRabin(num):
    s = num - 1
    t = 0
    while s % 2 == 0:
        s = s // 2
        t += 1

    for trials in range(5):
        a = random.randrange(2, num - 1)
        v = pow(a, s, num)
        if v != 1:
            i = 0
            while v != (num - 1):
                if i == t - 1:
                    return False
                else:
                    i = i + 1
                    v = (v ** 2) % num
    return True

需要先对1000以内素数查表排除，加速算法

def isPrime(num):
    '''对 Miller-Rabin 素性检测算法的封装，判断一个数是否为素数。'''
    if (num < 2):
        return False

    lowPrimes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,
                 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
                 101, 103, 107, 109, 113, 127, 131, 137, 139, 149,
                 151, 157, 163, 167, 173, 179, 181, 191, 193, 197,
                 199, 211, 223, 227, 229, 233, 239, 241, 251, 257,
                 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
                 317, 331, 337, 347, 349, 353, 359, 367, 373, 379,
                 383, 389, 397, 401, 409, 419, 421, 431, 433, 439,
                 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
                 503, 509, 521, 523, 541, 547, 557, 563, 569, 571,
                 577, 587, 593, 599, 601, 607, 613, 617, 619, 631,
                 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
                 701, 709, 719, 727, 733, 739, 743, 751, 757, 761,
                 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
                 839, 853, 857, 859, 863, 877, 881, 883, 887, 907,
                 911, 919, 929, 937, 941, 947, 953, 967, 971, 977,
                 983, 991, 997]

    if num in lowPrimes:
        return True

    for prime in lowPrimes:
        if num % prime == 0:
            return False

    return millerRabin(num)

六、基于费马定理的质数检测

基于费马小定理 ap-1 mod p≡1这个公式，随机选取若干个小于p的正整数a，若所有的a都满足p-1 mod p≡1，则基本认为p是质数。

Fermat素性测试只能大概率排除伪质数，而不能排除所有的伪质数，就是因为有卡迈克尔数的存在。从定义中也能看出这点。
Fermat素性测试实际上就是对费马小定理的应用。

统计表明，在前10亿个自然数中共有50847534个满足费马小定理的数，其中满足2(n-1) mod n = 1的合数n有5597个，这些合数都是以2为底的伪质数。有些伪质数可能通过了以2为底的测试，却不能通过以3为底的测试(3(n-1) mod n = 1)。能同时通过2和3测试的合数叫做以2和3为底的伪质数，前10亿中只有1272个。

所以，Fermat素性测试需要做相互独立的若干轮随机测试来降低出错的可能性。这个逻辑类似布隆过滤器。
而取遍1到n-1的所有整数进行素性测试，仍然没有被查出来的伪质数就被称为卡迈克尔数，前10亿中有600多个。
Fermat素性测试之所以不那么靠谱就是因为有卡迈克尔数的存在，这可以说是费马小定理的盲点吧。

基于fermat定理的强素性检测另一种实现。

    算法如下：
    输入：数N
    输出：是或否
        (1).N-1=2^k * m, m是奇数, k>=1;

        (2).在N的既约剩余系中随机选取一个数a, 1<a<N-1, 计算(a^m) mod N = b0;
                if b0 = 1, output "是"
        (3).i 1:k, 计算b(i+1) = (bi)^2 mod N
                if bk != 1, output "否"
        (4).j = min{i | b(i+1) = 1}
                bj != 1, b(j+1) = 1
        (5). g = gcd(bj != 1, N)
                if g = N or g = 1, output "是"
                else output "否"

发表新评论

RSA算法与数论-大质数生成