素数 | Sakeven's Blog

〇. 素数的性质

素数只能被 1 和它本身整除。

一. 素数的普通算法

最朴素的素数测试，试除法，依次检验 \( 1-\sqrt n \) 能否整除 n

bool is_prime(int n)
{
	if(n % 2== 0 && n != 2)
		return false;
	for(int i = 3; i * i < n; i += 2)
		if(n % i == 0)
			return false;
	return true;
}

二. 普通筛选法

当 n 为素数时，is_prime[n] = 0; 依次排除 2 的倍数，3 的倍数，5 的倍数…

bool is_prime[1000];
int check_prime()
{
    memset(is_prime,0,sizeof(is_prime));
    for(int i = 2; i < 1000; i ++)
    {
        if(is_prime[i] == 0)
        {
            for(int j = 2*i; j < 1000;j += i)
                is_prime[j] = 1;
        }
    }
}

三. 除余法

由普通的素数测试演化而来，当我们对 2 到 n 的数字进行测试时，发现 2 的倍数会被测试，同理，3 的倍数也会被测试。于是我们就想能否将 2 的倍数、3 的倍数排除掉这里我们令 \( n_1 = 6k+1 \)、\( n_2=6k+2 \)、\( n_3=6k+3 \)、\( n_4=6k+4 \)、\(n_5=6k+5\)、\(n_6=6k+6 \) …

此时我们发现只需测试 \( n_1 \)、\(n_5\)、\(n_7\)、\(n_{11}\) …这样我们只需测试 2/6=1/3 ；

根据此规律不难发现其规则为 4，2，4，2 的间隔

int creat_prime(int p[], int n, int total)  
{  
    int i, j, g = 2;  
    for (i = 7; i <= n; i += g) {  
        g = 6 - g;  
        for (j = 0; p[j] * p[j] <= i && i % p[j]; j++);  
        if (i % p[j]) {  
            p[total++] = i;  
        }  
    }  
    return total;  
}

四. Miller-Rabin 素性测试

素性测试是对一个正整数是否为素数的测试。

由于是随机测试，素数一定可以通过的测试，而合数不一定不能通过测试。所以我们往往取 3 次测试，提高测试的准确性。

费马小定里

若 n 是一个素数，且 a 与 n 互质, 那么 \(a^{n-1} \equiv 1 (mod\ n) \)

费马小定理只是个必要条件, 符合费马小定理而非素数的数叫做 Carmichael。前 3 个 Carmichael 数是 561, 1105, 1729。Carmichael 数是非常少的。在 1~100000000 范围内的整数中，只有 255 个 Carmichael 数。

为此又有二次探测定理,以确保该数为素数.

二次探测定理

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

根据以上两个定理，得到 Miller-Rabin 算法的一般步骤：

先计算出 m、j，使得 \(n-1=m*2^j\)，其中 m 是正奇数，j 是非负整数
随机取一个 b，\(b \ge 2 \)
计算 \( v=b^m mod\ n \)
如果 v==1，通过测试，返回
令 i=1
如果 v==n-1，通过测试，返回
如果 i==j，非素数，结束
\(v=v^2 mod\ n \)，\(i=i+1\)
循环到 5

bool Miller_Rabin(int n)
{
    int m = n - 1;
    int i, j, v, b;
    j = 0;
    while((m&1) == 0)
    {
        m >>= 1;
        j ++;
    }

    v = 1;
    b = rand()%(n-3) + 2;
    while(m!=0)
    {
        if(m&1)
            v = (v*b)%n;
        b = b*b%n;
        m >>= 1;
    }

    if(v == 1)
        return true;

    for(i = 1;;i++)
    {
        if(v == n-1)
            return true;
        if(i == j)
            return false;
        v = (v*v)%n;
    }

    return false;
}

bool repeat_M_R(int n)//素性测试
{
    for(int i = 1; i<=3;i++)
    {
        if(Miller_Rabin(n) == false)
            return false;
    }
    return true;
}

素数