- 论坛徽章:
- 3
|
循环要比预期小 我一个程序生成N 另一个程序生成P和Q 算法一样 我已经有N多重复的值了
这是生成素数的程序
/****************************************************************************************
产生随机素数
调用方法：N.GetPrime(bits)
返回值：N被赋值为一个bits位（0x100000000进制长度）的素数
****************************************************************************************/
void CBigInt::GetPrime(int bits)
{
unsigned i;
m_nLength=bits;
begin:
for(i=0;i<m_nLength;i++)m_ulValue[i]=rand()*0x10000+rand();
m_ulValue[0]=m_ulValue[0]|1;
for(i=m_nLength-1;i>0;i--)
{
m_ulValue[i]=m_ulValue[i]<<1;
if(m_ulValue[i-1]&0x80000000)m_ulValue[i]++;
}
m_ulValue[0]=m_ulValue[0]<<1;
m_ulValue[0]++;
for(i=0;i<550;i++){if(Mod(PrimeTable[i])==0)goto begin;}
CBigInt S,A,I,K;
K.Mov(*this);
K.m_ulValue[0]--;
for(i=0;i<5;i++)
{
A.Mov(rand()*rand());
S.Mov(K.Div(2));
I.Mov(A.RsaTrans(S,*this));
if(((I.m_nLength!=1)||(I.m_ulValue[0]!=1))&&(I.Cmp(K)!=0))goto begin;
}
}
产生的原理是这个
数论学家利用费马小定理研究出了多种素数测试方法，目前最快的算法是拉宾米
勒测试算法，其过程如下：
（1）计算奇数M，使得N=(2**r)*M+1
（2）选择随机数A<N
（3）对于任意i<r，若A**((2**i)*M) MOD N = N-1，则N通过随机数A的测试
（4）或者，若A**M MOD N = 1，则N通过随机数A的测试
（5）让A取不同的值对N进行5次测试，若全部通过则判定N为素数
若N 通过一次测试，则N 不是素数的概率为 25%，若N 通过t 次测试，则N 不是
素数的概率为1/4**t。事实上取t 为5 时，N 不是素数的概率为 1/128，N 为素数的
概率已经大于99.99%。
在实际应用中，可首先用300—500个小素数对N 进行测试，以提高拉宾米勒测试
通过的概率，从而提高测试速度。而在生成随机素数时，选取的随机数最好让 r=0，
则可省去步骤（3） 的测试，进一步提高测试速度。 |
|
免费注册
楼主: zuoyuanturing
发表于 2016-03-11 22:18
发表于 2016-03-12 00:33
发表于 2016-03-12 21:44