#include"stdio.h"
main()
{
int i,n,num
for(n=0,num=0n<=300n++)
{
i=2
while(i<n&&n%i!=0)
i++
if(i==n)
{
printf("%6d",n)
num++
}
}
printf("n素数个数为%d",num)
}
别浪费了尘枝帆我的宝贵时间！
你需要的包含在这个程序中，生成一个大数然后做RM素数测试，通过的我们假设其为素数即可！RSA算法
1978年就出现了这种算法，它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和 *** 作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, AdiShamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。
RSA的安全性依赖于大数难于分解这一特点。公钥和私钥都是两个大素数（大于100个十进制位）的函数。据猜测，从一个密钥和密文推断出明文的难度等同颤凯运于分解两个大素数的积。
密钥对的产生。选择两个大素数，p 和q 。计算：n = p * q 然后随机选择加密密钥e，要求 e 和 ( p - 1 ) * ( q - 1 )互质。最后，利用Euclid 算法计算解密密钥d, 满足e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )其中n和d也要互质。数e和n是公钥，d是私钥。两个素数p和q不再需要，应该丢弃，不要让任何人知道。加密信息 m（二进制表示）时，首先把m分成等长数据块 m1 ,m2,..., mi ，块长s，其中 2^s <= n, s 尽可能的大。对应的密文是：ci = mi^e ( mod n ) ( a ) 解密时作如下茄梁计算：mi = ci^d ( mod n ) ( b )
RSA 可用于数字签名，方案是用 ( a ) 式签名， ( b )式验证。具体 *** 作时考虑到安全性和 m信息量较大等因素，一般是先作HASH 运算。RSA 的安全性。RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解140多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。
由于进行的都是大数计算，孙森使得RSA最快的情况也比DES慢上100倍，无论是软件还是硬件实现。速度一直是RSA的缺陷。一般来说只用于少量数据加密。
*/
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std//RSA算法所需参数
typedef struct RSA_PARAM_Tag
{
unsigned __int64p, q //两个素数，不参与加密解密运算
unsigned __int64f //f=(p-1)*(q-1)，不参与加密解密运算
unsigned __int64n, e //公匙，n=p*q，gcd(e,f)=1
unsigned __int64d //私匙，e*d=1 (mod f)，gcd(n,d)=1
unsigned __int64s //块长，满足2^s<=n的最大的s，即log2(n)
} RSA_PARAM//小素数表
const static long g_PrimeTable[]=
{
3,
5,
7,
11,
13,
17,
19,
23,
29,
31,
37,
41,
43,
47,
53,
59,
61,
67,
71,
73,
79,
83,
89,
97
}
const static long g_PrimeCount=sizeof(g_PrimeTable) / sizeof(long)const unsigned __int64 multiplier=12747293821
const unsigned __int64 adder=1343545677842234541//随机数类
class RandNumber
{
private:
unsigned __int64randSeed
public:
RandNumber(unsigned __int64 s=0)
unsigned __int64Random(unsigned __int64 n)
}
RandNumber::RandNumber(unsigned __int64 s)
{
if(!s)
{
randSeed= (unsigned __int64)time(NULL)
}
else
{
randSeed=s
}
}
unsigned __int64 RandNumber::Random(unsigned __int64 n)
{
randSeed=multiplier * randSeed + adder
return randSeed % n
}static RandNumber g_Rnd
inline unsigned __int64 MulMod(unsigned __int64 a, unsigned __int64 b, unsigned __int64 n)
{
return a * b % n
}
unsigned __int64 PowMod(unsigned __int64 &base, unsigned __int64 &pow, unsigned __int64 &n)
{
unsigned __int64a=base, b=pow, c=1
while(b)
{
while(!(b &1))
{
b>>=1 //a=a * a % n //函数看起来可以处理64位的整数，但由于这里a*a在a>=2^32时已经造成了溢出，因此实际处理范围没有64位
a=MulMod(a, a, n)
}b-- //c=a * c % n //这里也会溢出，若把64位整数拆为两个32位整数不知是否可以解决这个问题。
c=MulMod(a, c, n)
}return c
}
long RabinMillerKnl(unsigned __int64 &n)
{
unsigned __int64b, m, j, v, i
m=n - 1
j=0 //0、先计算出m、j，使得n-1=m*2^j，其中m是正奇数，j是非负整数
while(!(m &1))
{
++j
m>>=1
}//1、随机取一个b，2<=b<n-1
b=2 + g_Rnd.Random(n - 3) //2、计算v=b^m mod n
v=PowMod(b, m, n) //3、如果v==1，通过测试
if(v == 1)
{
return 1
}//4、令i=1
i=1 //5、如果v=n-1，通过测试
while(v != n - 1)
{
//6、如果i==l，非素数，结束
if(i == j)
{
return 0
}//7、v=v^2 mod n，i=i+1
unsigned __int64 tmp1 = 2
v=PowMod(v,tmp1, n)
++i //8、循环到5
}return 1
}
long RabinMiller(unsigned __int64 &n, long loop)
{
//先用小素数筛选一次，提高效率
for(long i=0i <g_PrimeCounti++)
{
if(n % g_PrimeTable[i] == 0)
{
return 0
}
}//循环调用Rabin-Miller测试loop次，使得非素数通过测试的概率降为(1/4)^loop
for(long i=0i <loopi++)
{
if(!RabinMillerKnl(n))
{
return 0
}
}return 1
}
unsigned __int64 RandomPrime(char bits)
{
unsigned __int64base
do
{
base= (unsigned long)1 <<(bits - 1) //保证最高位是1
base+=g_Rnd.Random(base) //再加上一个随机数
base|=1 //保证最低位是1，即保证是奇数
} while(!RabinMiller(base, 30)) //进行拉宾－米勒测试30次
return base //全部通过认为是素数
}
unsigned __int64 EuclidGcd(unsigned __int64 &p, unsigned __int64 &q)
{
unsigned __int64a=p >q ? p : q
unsigned __int64b=p <q ? p : q
unsigned __int64t
if(p == q)
{
return p //两数相等，最大公约数就是本身
}
else
{
while(b)//辗转相除法，gcd(a,b)=gcd(b,a-qb)
{
a=a % b
t=a
a=b
b=t
}return a
}
}
unsigned __int64 SteinGcd(unsigned __int64 &p, unsigned __int64 &q)
{
unsigned __int64a=p >q ? p : q
unsigned __int64b=p <q ? p : q
unsigned __int64t, r=1
if(p == q)
{
return p //两数相等，最大公约数就是本身
}
else
{
while((!(a &1)) &&(!(b &1)))
{
r<<=1 //a、b均为偶数时，gcd(a,b)=2*gcd(a/2,b/2)
a>>=1
b>>=1
}if(!(a &1))
{
t=a //如果a为偶数，交换a，b
a=b
b=t
}do
{
while(!(b &1))
{
b>>=1 //b为偶数，a为奇数时，gcd(b,a)=gcd(b/2,a)
}if(b <a)
{
t=a //如果b小于a，交换a，b
a=b
b=t
}b=(b - a) >>1//b、a都是奇数，gcd(b,a)=gcd((b-a)/2,a)
} while(b)
return r * a
}
}
unsigned __int64 Euclid(unsigned __int64 &a, unsigned __int64 &b)
{
unsigned __int64m, e, i, j, x, y
longxx, yy
m=b
e=a
x=0
y=1
xx=1
yy=1
while(e)
{
i=m / e
j=m % e
m=e
e=j
j=y
y*=i
if(xx == yy)
{
if(x >y)
{
y=x - y
}
else
{
y-=x
yy=0
}
}
else
{
y+=x
xx=1 - xx
yy=1 - yy
}x=j
}if(xx == 0)
{
x=b - x
}return x
}
RSA_PARAM RsaGetParam(void)
{
RSA_PARAM Rsa={ 0 }
unsigned __int64t
Rsa.p=RandomPrime(16) //随机生成两个素数
Rsa.q=RandomPrime(16)
Rsa.n=Rsa.p * Rsa.q
Rsa.f=(Rsa.p - 1) * (Rsa.q - 1)
do
{
Rsa.e=g_Rnd.Random(65536)//小于2^16，65536=2^16
Rsa.e|=1 //保证最低位是1，即保证是奇数，因f一定是偶数，要互素，只能是奇数
} while(SteinGcd(Rsa.e, Rsa.f) != 1) Rsa.d=Euclid(Rsa.e, Rsa.f)
Rsa.s=0
t=Rsa.n >>1
while(t)
{
Rsa.s++ //s=log2(n)
t>>=1
}return Rsa
}
void TestRM(void)
{
unsigned long k=0
cout <<" - Rabin-Miller prime check.n" <<endl
for(unsigned __int64 i=4197900001i <4198000000i+=2)
{
if(RabinMiller(i, 30))
{
k++
cout <<i <<endl
}
}cout <<"Total: " <<k <<endl
}
void TestRSA(void)
{
RSA_PARAM r
charpSrc[]="abcdefghijklmnopqrstuvwxyz"
const unsigned long n=sizeof(pSrc)
unsigned char *q, pDec[n]
unsigned __int64pEnc[n]
r=RsaGetParam()
cout <<"p=" <<r.p <<endl
cout <<"q=" <<r.q <<endl
cout <<"f=(p-1)*(q-1)=" <<r.f <<endl
cout <<"n=p*q=" <<r.n <<endl
cout <<"e=" <<r.e <<endl
cout <<"d=" <<r.d <<endl
cout <<"s=" <<r.s <<endl
cout <<"Source:" <<pSrc <<endl
q= (unsigned char *)pSrc
cout <<"Encode:"
for(unsigned long i=0i <ni++)
{
unsigned __int64 tmp2 = q[i]
pEnc[i]=PowMod(tmp2, r.e, r.n)
cout <<hex <<pEnc[i] <<" "
}cout <<endl
cout <<"Decode:"
for(unsigned long i=0i <ni++)
{
pDec[i]=PowMod(pEnc[i], r.d, r.n)
cout <<hex <<(unsigned long)pDec[i] <<" "
}cout <<endl
cout <<(char *)pDec <<endl
}
int main(void)
{
TestRSA()
return 0
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）