素数

2013/10/24

Categories: Algorithm Tags: acm number theory

〇. 素数的性质

素数只能被 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 = 6*k+1 \)、\( n_2=6*k+2 \)、\( n_3=6*k+3 \)、\( n_4=6*k+4 \)、\(n_5=6*k+5\)、\(n_6=6*k+6 \) …

此时我们发现只需测试 \( n_1 \)、\(n_5\)、\(n_7\)、\(n_{11}\) …这样我们只需测试 26=13

根据此规律不难发现其规则为 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 算法的一般步骤:

  1. 先计算出 m、j,使得 \(n-1=m*2^j\),其中 m 是正奇数,j 是非负整数
  2. 随机取一个 b,\(b \ge 2 \)
  3. 计算 \( v=b^m mod\ n \)
  4. 如果 v==1,通过测试,返回
  5. 令 i=1
  6. 如果 v==n-1,通过测试,返回
  7. 如果 i==j,非素数,结束
  8. \(v=v^2 mod\ n \),\(i=i+1\)
  9. 循环到 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;
}