素数

1. 素数的判定

方法1：1到蛮力测试

//素数的判定

//2 到sqrt(x) 整除x，只要有一个能除尽，说明x 不是素数

BOOL isPrime1(UINT32 x)

{

switch(x)

{

case 0:

return FALSE;

case 1:

return FALSE;

case 2:

return TRUE;

case 3:

return TRUE;

default:

break;

}

//以上是处理边界情况1 2 3

for(UINT32 i = 2; i <= static_cast<UINT32>(sqrt(static_cast<float>(x)));

++i)

{

if(0U == x % i)

{

return FALSE;

}

}

return TRUE;

}

方法2：用素数表测试

//素数的判定

//如果x 不是太大，素数表的最大素数是不小于sqrt(x)的最大素数，用素数表的每个素数

//去整除x，只要有一个能整除，说明x是合数，返回FALSE；

//只有小于sqrt(x)内的所有素数都不能整除x，说明x是素数，返回TRUE

UINT32 list[] = {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};//sqrt(10000)内的素数表

BOOL isPrime2(UINT32 x)

{

switch(x)

{

case 0:

return FALSE;

case 1:

return FALSE;

case 2:

return TRUE;

case 3:

return TRUE;

default:

break;

}

//以上是处理边界情况1 2 3

UINT32 i = 0;

while(list[i] * list[i] <= x)

{

if(0 == x % list[i])

{

return FALSE;

}

++i;

}

return TRUE;

}

方法3：米勒-拉宾测试

令大奇数n=m+1，其中l是非负整数，m是正奇数，若1()或-1()，，则称n通过b为基的米勒-拉宾测试。

定理 如果n是奇合数，0<b<n，则使n通过Miller-Rabin测试的b的个数不超过(n-1)(即n通过b的Miller-Rabin测试的概率最高是)。

例如随机选取n，通过依次随机取的Miller-Rabin测试，n是合数的概率不超过==0.00000095，至少以0.999999的概率判定n是素数。

定理简单明了，但证明却需要许多准备。

//米勒-拉宾测试

//n=2^m*l+1

BOOL passMillerRabinTest(UINT32 n)

{

UINT<chmetcnv unitname="l" sourcevalue="32" hasspace="True" negative="False" numbertype="1" tcsc="0">32 l</chmetcnv> = 0U;

UINT<chmetcnv unitname="m" sourcevalue="32" hasspace="True" negative="False" numbertype="1" tcsc="0">32 m</chmetcnv> = n - 1;

while(0U == m % 2U)

{

l += 1;

m /= 2U;

}

UINT32 b = rand() % (n - 1U) + 1;

if(1U == modExp(b, m, n))

{

return TRUE;

}

UINT32 j = m;

for(UINT32 i = 0U; i < l; ++i)

{

if(modExp(b, j, n) == n - 1)

{

return TRUE;

}

j *= 2;

}

return FALSE;

}

2. 产生一个素数

在实际应用中，经常需要大素数，产生大素数的过程如下：

（1）产生一个n位随机数p（n位二进制）；

（2）将最高位和最低为置为1（最高位置1保证了产生的素数足够大，而最低位为1保证为奇数）；

（3）检查p是否能被小素数整除：3，5，7，11等。许多实际应用中都用小于256的所有素数去除p；

（4）对于随机数a，进行Miller-Rabin测试，如果p通过了，则产生另一个随机数a再进行测试。选择值小一些的额a可以令计算更快。做5次测试，只要p没有通过其中的一次，转（1）重新开始；

另一种方法不是每次产生一个随机数，而是从一个起始数开始逐次递增，直到找到素数。

步骤（3）是可选的，但很有用。测试一个随机奇数p是否能被3，5，7整除，可以在第（4）步测试前去掉54%的基数，用100以内的素数测试可以去掉76%的奇数，而用256以内的素数测试可以去掉80%的奇数。一般地，奇数中不为任何小于n的素数的倍数的数的比例占1.12/lnn。

查看原文