📄 main.cpp
字号:
CopyBigNum(X,A);
for(i=iBitCount-2;i>=0;i--)
{
//x=x*x*R'%N
Montgomery_r(X,X,N,temp);
CopyBigNum(X,temp);
byte=(unsigned char)(power[i/32+1]>>(i%32))&0x1;
if(byte==1)
{
//X=X*A'*R' %N
Montgomery_r(A,X,N,temp);//A=A*R%N
CopyBigNum(X,temp);
}
}
Montgomery_r(X,ONEVALUE,N,temp);//A=A*R%N
CopyBigNum(remainder,temp);
return;
//CopyBigNum(remainder,product);
}
/******************************************************************************/
/* */
/* 函数: 实现2^32进制大数的幂模(调用二进制蒙哥马利算法) */
/* 语法: powermode_r(BIGNUM base,BIGNUM power,BIGNUM N,BIGNUM remainder) */
/* 输入: */
/* base：2^32进制大数 */
/* power: 2^32进制大数 */
/* N: 2^32进制大数 */
/* remainder: 2^32进制大数 */
/* 输出: */
/* remainder： */
/* 返回: void */
/* 算法： */
/* */
/* 设R=2**k %N，R'=2**(-k) %N，E=Sum[i=0 to n](E*2**i)： */
/* A'=A*R %N */
/* X=A' */
/* FOR i FROM n-1 TO 0 */
/* X=X*X*R' %N */
/* IF E=1 X=X*A'*R' %N */
/* X=X*1*R' %N */
/* RETURN X */
/******************************************************************************/
//二进制的模幂(调用二进制蒙哥马利算法)
void powermode_2(BIGNUM base,BIGNUM power,BIGNUM m,BIGNUM remainder)
{
int i;
int iBitCount=0;
unsigned char byte;
BIGNUM R,r,R2;//R=2^(m的比特位数)
BIGNUM A,X,temp,temp2,temp3;
iBitCount=GetBigNumBitCount(m);
if(base[0]==0)
{
remainder[0]=0;
return;
}
memset(R,0,sizeof(BIGNUM));
memset(R2,0,sizeof(BIGNUM));
R[0]=((iBitCount+1)+31)/32;
bignum_set_bit(R,iBitCount,1);//2^iBitCount
//R2[0]=(2*(iBitCount+1)-1)/32+1;
//bignum_set_bit(R2,2*(iBitCount+1)-1-1,1);//比特位从零位算起
bignum_substract(R,m,r);//r=2^iBitCount-m
bignum_mul(r,r,R2);//R2=r^2
bignum_mod(R2,m,X);
CopyBigNum(R2,X);//R2=R2%m
/*BIGNUM product,quotient;
bignum_mul(base,R,product);
bignum_mod(product,divisor,temp);*/
BIGNUM product;
//Montgomery(base,X,divisor,A);//A=A*R%M
iBitCount=GetBigNumBitCount(power);//指数
Montgomery_2(base,R2,m,A);//A=A*R%M
CopyBigNum(X,A);
for(i=iBitCount-2;i>=0;i--)
{
//x=x*x*R'%N
Montgomery_2(X,X,m,temp);
CopyBigNum(X,temp);
byte=(unsigned char)(power[i/32+1]>>(i%32))&0x1;
if(byte==1)
{
//X=X*A'*R' %N
Montgomery_2(X,A,m,temp);//A=A*R%N
CopyBigNum(X,temp);
}
}
//byte=(unsigned char)(power[i/32+1]>>(i%32))&0x1;
Montgomery_2(ONEVALUE,X,m,temp);//A=A*R%N
CopyBigNum(remainder,temp);
return;
//CopyBigNum(remainder,product);
}
//选择与模数n互素的基数R=2^k，n满足2^(k－1)≤n<2^k， n应为奇数。
//并且选择R'及n’，满足0< R'<n, 0< n’<n,使得 RR'-nn’＝1
/*
M(m)
{
k = ( m * n’ ) mod R;
x = (m + k*n ) / R;
if (x>=n)
x -= n;
return x;
}
exp(C,E,n)
{
D=R-n;
P=C*R mod n;
i=0;
while(true)
{
if(E的当前二进制位Ei==1)
D=M(D*P); //从低位到高位检测二进制位
i+=1;
if(i==E的二进制位数)
break;
P=M(P*P);
}
return D*R^(-1) (mod n);
}
*/
//R=
void powermode4(BIGNUM base,BIGNUM power,BIGNUM n,BIGNUM remainder)
{
int i;
int iBitCount=0;
unsigned char byte;
BIGNUM R,R_,n_;
BIGNUM temp;
iBitCount=GetBigNumBitCount(base);
if(base[0]==0)
{
remainder[0]=0;
return;
}
memset(R,0,sizeof(BIGNUM));
R[0]=base[0]+1;
R[base[0]+1]=1;
//R[0]=1;
//R[1]=16;
GetEuclidEquation(R,n,R_,n_);//R*R'-n*n'=1
BIGNUM D,P,product;
bignum_substract(R,n,D);//D=R-n
bignum_mul(base,R,product);
bignum_mod(product,n,P);//p=base*R%n
i=0;
iBitCount=GetBigNumBitCount(power);//指数
for(;;)
{
//byte=(unsigned char)(power[i/32+1]>>(i%32))&0x1;
byte=bignum_get_bit(power,i);//从低位到高位检测二进制位
if(byte)
{
bignum_mul(D,P,product);
Montgomery4(product,R,n_,n,D);//D=M(D*P);
}
i++;
if(i==iBitCount)
break;
bignum_mul(P,P,product);
Montgomery4(product,R,n_,n,P);//P=M(P*P);
}
Montgomery4(D,R,n_,n,remainder);//D=M(D);
//CopyBigNum(remainder,D);
}
///////////////////////////////////////////////////////////////////////////////
//利用线性同余生成随机数
//x[i+1]=(x[i]*a+b)%m
//a=0x5851f42d,0x4c957f2d,
//b=1
//m=2^64
///////////////////////////////////////////////////////////////////////////////
//初始化伪随机函数的种子(unsigned __int32)time(NULL)
void InitSeed(unsigned __int32 seed)
{
SEED64[0]=1;
SEED64[1]=seed;
}
/******************************************************************************/
/* */
/* 函数: 生成一个数据类型为BIGNUM 的64比特位的伪随机数 */
/* 语法: GetSeed_64 (void); */
/* 输入: 全局变量：SEED64，A64 */
/* SEED64：随机数种子（全局变量） */
/* A64:线性同余公式的常参数 （全局变量） */
/* 输出: */
/* SEED64：随机数种子(全局变量) */
/* 返回: void */
/*x[i+1]=(x[i]*a+b)%m */
/******************************************************************************/
void GetRandomSeed_64 ()
{
BIGNUM product,result;
unsigned __int32 b=1;
bignum_mul(SEED64,A64,product);//product=SEED64*A64
bignum_Increment(product);//product=product+1
result[0]=2;
result[1]=product[1];
result[2]=product[2];
while(result[0]>0 &&result[result[0]]==0)
result[0]--;
/*if(product[2]==0)
{
if(sum[1]==0)
result[0]=0;
else
result[0]=1;
}*/
CopyBigNum(SEED64,result);
}
unsigned __int32 GetRandom_32 ()
{
unsigned __int32 lValue=0;
unsigned int len;
GetRandomSeed_64();
len=SEED64[0];
switch(len)
{
case 2:
case 1:
lValue=SEED64[len];
break;
//default:
// lValue=0;
}
return lValue;
}
/******************************************************************************/
/* */
/* 函数: 生成一个数据类型为BIGNUM 的比特长度为iBitCount的伪随机数 */
/* (首先需要调用 InitSeed()函数初始化伪随机数种子) */
/* 语法: void GetRandom(BIGNUM dest,int iBitCount); */
/* 输入: */
/* iBitCount：伪随机数的比特长度 */
/* 输出: */
/* dest：比特长度为iBitCount的伪随机数 */
/* 返回: void */
/* */
/******************************************************************************/
void GetRandom(BIGNUM dest,int iBitCount)
{
unsigned __int32 lValue=0;
unsigned int i,len;
unsigned int quotient;//随机数有几个64位的
unsigned int remainder;//随机数减去64位比特倍数的余数(小于64位比特)
memset(dest,0,sizeof(BIGNUM));
if(iBitCount<=0)
{
return;
}
quotient=iBitCount/64;
remainder=iBitCount%64;
for(i=1;i<=quotient;++i)
{
GetRandomSeed_64();
dest[i*2-1]=SEED64[1];
dest[i*2]=SEED64[2];
}
len=quotient*2;
if(remainder>0)
{
GetRandomSeed_64();
/*************************
unsigned __int64 randNum64;
randNum64=(((__int64)SEED64[2])<<32)+SEED64[1];
randNum64<<=(64-remainder);
randNum64|=0x8000000000000000;//二进制最高位保证为1
randNum64>>=(64-remainder);
dest[len+1]=(unsigned __int32)randNum64;
dest[len+2]=(unsigned __int32)(randNum64>>32);
if(dest[len+2]==0)
{
dest[0]=len+1;
}
else
dest[0]=len+2;
**************************************************/
if(remainder>32)//32<remainder<64
{
dest[len+1]=SEED64[1];
lValue=SEED64[2];
lValue=lValue<<(64-remainder);
lValue=lValue|0x80000000;//二进制最高位保证为1
lValue>>=(64-remainder);
dest[len+2]=lValue;
dest[0]=len+2;
}
else if(remainder<32)
{
lValue=SEED64[2];
lValue=lValue<<(64-remainder);
lValue=lValue|0x80000000;//二进制最高位保证为1
lValue>>=(64-remainder);
dest[len+1]=lValue;
dest[0]=len+1;
}
else
{
lValue=SEED64[2];
lValue|=0x80000000;//二进制最高位保证为1
dest[len+1]=lValue;
dest[0]=len+1;
}
}
else
{
dest[len]|=0x80000000;
dest[0]=len;
}
}
void GetRandom2(BIGNUM dest,int iBitCount)
{
unsigned __int32 lValue=0;
unsigned int i,len;
unsigned int quotient;//随机数有几个64位的
unsigned int remainder;//随机数减去64位比特倍数的余数(小于64位比特)
memset(dest,0,sizeof(BIGNUM));
if(iBitCount<=0)
{
return;
}
quotient=iBitCount/64;
remainder=iBitCount%64;
for(i=1;i<=quotient;++i)
{
GetRandomSeed_64();
dest[i*2-1]=SEED64[1];
dest[i*2]=SEED64[2];
}
len=quotient*2;
if(remainder>0)
{
GetRandomSeed_64();
/*************************
unsigned __int64 randNum64;
randNum64=(((__int64)SEED64[2])<<32)+SEED64[1];
randNum64<<=(64-remainder);
randNum64|=0x8000000000000000;//二进制最高位保证为1
randNum64>>=(64-remainder);
dest[len+1]=(unsigned __int32)randNum64;
dest[len+2]=(unsigned __int32)(randNum64>>32);
if(dest[len+2]==0)
{
dest[0]=len+1;
}
else
dest[0]=len+2;
**************************************************/
if(remainder>32)//32<remainder<64
{
dest[len+1]=SEED64[1];
lValue=SEED64[2];
lValue=lValue<<(64-remainder);
//lValue=lValue|0x80000000;//二进制最高位保证为1
lValue>>=(64-remainder);
dest[len+2]=lValue;
dest[0]=len+2;
}
else if(remainder<32)
{
lValue=SEED64[2];
lValue=lValue<<(64-remainder);
//lValue=lValue|0x80000000;//二进制最高位保证为1
lValue>>=(64-remainder);
dest[len+1]=lValue;
dest[0]=len+1;
}
else
{
lValue=SEED64[2];
//lValue|=0x80000000;//二进制最高位保证为1
dest[len+1]=lValue;
dest[0]=len+1;
}
}
else
{
//dest[len]|=|0x80000000;
dest[0]=len;
}
}
/******************************************************************************
//*****************************************************************************
Rabin-Miller素数测试，通过测试返回1，否则返回0。
n是待测素数。
注意：通过测试并不一定就是素数，非素数通过测试的概率是1/4
数论学家利用费马小定理( a^(p-1)%p=1,其中p是质数,a是整数 )研究出了多种素数测试方法，目
前最快的算法是拉宾米勒测试算法，测试N是素数的过程如下：
（1）计算奇数M，使得N=(2^j)*M+1
（2）选择随机数A<N
（3）对于任意i<j，若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 进行测试，以提高拉宾米勒测试通过的概率，从
而提高测试速度。而在生成随机素数时，选取的随机数最好让 j=0，则可省去步骤（3） 的测试，进
一步提高测试速度。
//*****************************************************************************
******************************************************************************/
/******************************************************************************/
/* */
/* 函数: 拉宾米勒测试算法 */
/* */
/* 语法: long RabinMillerKernel(BIGNUM n,int iLoop) */
/* 输入: */
/* n：2^32进制的大数 */
/* iLoop：测试的次数 */
/* 输出: */
/* --- */
/* 返回: */
/* 1：测试通过 */
/* 0：测试不通过 */
/* */
/******************************************************************************/
long RabinMillerKernel(BIGNUM n,int iLoop)
{
BIGNUM m,v,v2,n_1;
BIGNUM result;
int i,j,iBitCount;
BIGNUM quotient,remainder;
memset(result,0,sizeof(BIGNUM));//结果清零初始化
j=0;
//0、先计算出m、j，使得n-1=m*2^j，其中m是正数，j是非负整数
//一个正奇数一定可以分解为n-1=m*2^j
/*
bignum_substract2(n,1,n_1);//m=n-1
CopyBigNum(m,n_1);//余数
while(m[1]%2==0&& m[0]!=0)//偶数而且非零值就继续循环
{
++j;
//division(m,TWOVALUE,quotient,remainder);//m/2
bignum_rightshift2(m,1,quotient);//移位速度较快
CopyBigNum(m,quotient);
}*/
CopyBigNum(m,n);
//在n-1中找到第一个比特位为1的位数
for (j = 0; bignum_get_bit(m, j) == !j; j++)
continue;
bignum_rightshift2(m,j,quotient);
CopyBigNum(m,quotient);
CopyBigNum(n_1,n);
bignum_Decrement(n_1);//n_1=n-1
//CopyBigNum(m,n_1);//令j=0
//1、随⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -