M-R算法的实现（跪求高人指点）
题目要求是这个：
(1) 实现MR算法
(2) 建立一个新的数据结构LargNum 可以表示大数 如2的1024次方
(3) 利用数据结构LargNum实现大数的MR算法，找到两个大约有2的1024次方大的素数
大家帮个忙，给个思路也行啊。。。
[解决办法]
这个算法不准确的，只能得到一个( 1- 2^(-s)的概率素数，需要使用s个不同的目击者才行，s要足够大
现在应该用aks确定性素数判断方法，
[解决办法]
使用s个不同的a计算witness( a, n );
n用k位二进制表示b[k];
d = 1;
for( i = k; i >= 0; --i )
{
x = d;
d = ( d * d ) % n;
if( d == 1 && x != 1 && x != n-1 )
return( false );
if( b[i] == 1 )
d = ( d * a ) % n;
}
if( d != 1 )
return( false );
return( true );
把这个算法重复使用s个不同的a，如果都返回true就有1-2^(-s)概率是素数，a是小于n的整数
s = 100;
for( i = 0; i < s; ++i )
{
a = rand();
while( a < 2 || a >= n )
a = rand();
if( !Witness( a, n ) )
return false;
}
return true;
这里主要是用vector实现大数运算问题
[解决办法]
n-1用k位二进制表示b[k];
for( i = k-1; i >= 0; --i )
[解决办法]
没有人为了那个确定性而去用AKS的。实际应用上都还是MR。
比如要判定个1024位的质数。MR的平方级别立马秒杀。AKS的6次方玩个毛啊。
[解决办法]
