📄 dsa2.c
字号:
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <math.h>
#include <dos.h>
#include <bios.h>
#define FULL 0xffffffff
#define BLOCK 64
#define CLEAR 0x00000000
#define RIGHT 0x000000ff
#define MID 0x0000ffff
#define LEFT 0x00ffffff
#define FULS 0xfffffff8
#define LMASK 0x80000000
#define RMASK 0x00000001
#define NNINE 0x3b9ac9ff
#define LENGTH 17
typedef unsigned long LINT[18];
unsigned long aa,bb,cc,dd;
int count,cpass;
char uname[20],sname[20],fmat[20];
FILE *fp,*fp1,*fp2,*fopen();
LINT up,uq,un,ue,udp,udq,ua,uv,uu,ub,ux,uy,us;
clock_t time1,time2;
int compare(unsigned long *p1,unsigned long*p2)
{
long j;
int flag=0;
if (*p1>*p2) flag=1;
else if(*p1<*p2) flag=-1;
else
{
j=*p1;
p1=p1+(*p1);
p2=p2+(*p2);
while((flag==0)&&(j>0))
{
if(*p1>*p2) flag=1;
else if(*p1<*p2) flag=-1;
j--;
p1--;
p2--;
}
}
return flag;
}
void shiftleft(unsigned long *sl)
{
unsigned long b1,b2,*psl;
long cnt;
b1=0x0;
psl=sl+1;
for (cnt=*sl;cnt>0;cnt--)
{
b2=(*psl)&LMASK;
*psl=((*psl)<<1)|b1;
if(b2==0x0)
b1=0x0;
else b1=RMASK;
psl++;
}
if(b1!=0x0)
{
(*psl)=1;
(*sl)++;
}
}
void shiftright(unsigned long *rl)
{
unsigned long b1,b2,*prl;
long cnt;
b1=0x0;
prl=rl+(*rl);
for(cnt=*rl;cnt>0;cnt--)
{
b2=*prl&RMASK;
*prl=(*prl>>1)|b1;
if(b2==0x0) b1=0x0;
else b1=LMASK;
prl--;
}
prl=rl+(*rl);
if((*prl)==0)
(*rl)--;
}
void add(unsigned long *p1,unsigned long *p2)
{
unsigned long len,carry,*pp1,*pp2;
if(*p1>*p2) len=*p1;
else len=*p2;
carry=0;
*p1=len;
pp1=p1+1;
pp2=p2+1;
for(;len>0;len--)
{
*pp1=(*pp1)+(*pp2)+carry;
if((*pp1)<(*pp2)) carry=1;
else carry=0;
pp1++;
pp2++;
}
if(carry==1)
{
(*p1)++;
(*pp1)++;
}
}
void sub(unsigned long *p1,unsigned long *p2)
{
unsigned long *pp1,*pp2,len,carry;
carry=0;
pp1=p1+1;
pp2=p2+1;
for(len=*p1;len>0;len--)
{
if((*pp1)>=(*pp2))
{
(*pp1)-=(*pp2);
if((*pp1==0x0)&&(carry==0x1))
*pp1=NULL;
else
{
(*pp1)-=carry;
carry=0x0;
}
}
else
{
(*pp1)=FULL-(*pp2)+(*pp1)+RMASK-carry;
carry=RMASK;
}
pp1++;
pp2++;
}
pp1=p1+(*p1);
while(((*pp1)==0)&&(pp1>p1))
{
(*p1)--;
pp1--;
}
}
void mod(unsigned long *ma,unsigned long *mb)
{
LINT pmb;
unsigned long t1,t2,*ptr;
if(compare(ma,mb)>0)
{
for(t1=1;t1<=LENGTH;t1++) pmb[t1]=0;
ptr=mb;
for(t1=0;t1<=LENGTH;t1++,ptr++) pmb[t1]=*ptr;
while(compare(ma,pmb)>0) shiftleft(pmb);
while(compare(ma,mb)>0)
{
while(compare(ma,pmb)<0) shiftright(pmb);
sub(ma,pmb);
}
}
if(compare(ma,mb)==0)
for(t1=0;t1<=LENGTH;t1++,ma++)
*ma=0;
}
void modmul(unsigned long *mx,unsigned long *my,unsigned long *mp,unsigned long *mz)
{
LINT pmx,pmy,pmz;
unsigned long m1,m2,a1,a2,*ptr1,*ptr2;
ptr1=mx;
ptr2=my;
for(m1=0;m1<=LENGTH;m1++)
{
pmx[m1]=*ptr1;
pmy[m1]=*ptr2;
pmz[m1]=0x0;
ptr1++;
ptr2++;
}
if(compare(pmx,mp)>0)
mod(pmx,mp);
for(m1=pmy[0];m1>0;m1--)
{
a1=LMASK;
for(m2=32;m2>0;m2--)
{
shiftleft(pmz);
a2=pmy[m1]&a1;
if(a2!=0)
add(pmz,pmx);
while(compare(pmz,mp)>0)
sub(pmz,mp);
a1>>=1;
}
}
for(m1=0;m1<=LENGTH;m1++,mz++)
*mz=pmz[m1];
}
void modexp(unsigned long *ex,unsigned long *ev,unsigned long *ep,unsigned long *ew)
{
LINT pex,pev,pew;
unsigned long e1,*ptm1,*ptm2;
count=0;
ptm1=ev;
ptm2=ex;
for(e1=0;e1<=LENGTH;e1++)
{
pev[e1]=*ptm1;
pex[e1]=*ptm2;
pew[e1]=0x0;
ptm1++;
ptm2++;
}
pew[0]=1;
pew[1]=0x1;
do
{
if((pev[1]&RMASK)==RMASK)
{
modmul(pex,pew,ep,pew);
count++;
}
shiftright(pev);
if(pev[0]!=0)
{
modmul(pex,pex,ep,pex);
count++;
}
}
while(pev[0]!=0);
for(e1=0;e1<=LENGTH;e1++,ew++)
*ew=pew[e1];
}
void bigrand(unsigned int rdl,unsigned long *bin)
{
unsigned long lp,rp,bcnt,*bip;
int bmask;
bip=bin+1;
bmask=0x7fff;
for(bcnt=1;bcnt<=LENGTH;bcnt++,bip++) *bip=0;
*bin=rdl;
bip=bin+1;
randomize();
for(bcnt=1;bcnt<=(*bin);bcnt++,bip++)
{
lp=random(bmask);
rp=random(bmask);
*bip=(lp<<16)|rp;
bin[bcnt]=*bip;
}
bip=bin+(*bin);
while(*bip==0)
{
(*bin)--;
bip--;
}
}
int primetest( unsigned long *pa)
{
LINT px,py;
int flag,ptmp,ptest;
unsigned long pcnt,pi,pk,*ppa;
ptmp=*pa;
ptest=0;
flag=1;
while((flag!=0)&&(ptest<25))
{
bigrand(ptmp,px);
ppa=pa+(*pa);
do
{
if(compare(px,pa)>0)
{
pcnt=FULL;
while(pcnt>=(*ppa))
pcnt>>=1;
px[ptmp]&=pcnt;
}
px[1]|=RMASK;
if(px[0]==0) px[0]=1;
}
while(compare(px,pa)==0);
pi=0;
ppa=pa;
for(pcnt=0;pcnt<=LENGTH;pcnt++,ppa++)
py[pcnt]=(*ppa);
flag=1;
pk=0;
if((py[1]&RMASK)==0)
flag=0;
else
{
py[1]--;
while((py[1]&RMASK)==0)
{
shiftright(py);
pk++;
}
}
if(flag==1)
{
modexp(px,py,pa,py);
ppa=pa;
for(pcnt=0;pcnt<=LENGTH;pcnt++,ppa++)
px[pcnt]=*ppa;
px[1]--;
if((compare(px,py)==0)||((py[0]==1)&&(py[1]==1)))
flag=2;
}
while((flag==1)&&(pi<pk))
{
pi++;
modmul(py,py,pa,py);
if((py[0]==1)&&(py[1]==1))
flag=0;
if(compare(px,py)==0)
flag=2;
}
if((flag==1)&&((py[0]!=1)||(py[1]!=1)))
flag=0;
ptest++;
}
cpass=ptest;
return flag;
}
void multiply( unsigned long *mua, unsigned long *mub, unsigned long *muc)
{
LINT mucc,muaa,mubb;
unsigned long mu1,mu2,ma1,ma2,*mptr1,*mptr2;
mptr1=mua;
mptr2=mub;
for(mu1=0;mu1<=LENGTH;mu1++)
{
muaa[mu1]=*mptr1;
mubb[mu1]=*mptr2;
mucc[mu1]=0x0;
mptr1++;
mptr2++;
}
for(mu1=mubb[0];mu1>0;mu1--)
{
ma1=LMASK;
for(mu2=32;mu2>0;mu2--)
{
shiftleft(mucc);
ma2=mubb[mu1]&ma1;
if(ma2!=0)
add(mucc,muaa);
ma1>>=1;
}
}
for(mu1=0;mu1<=LENGTH;mu1++,muc++)
*muc=mucc[mu1];
}
void division( unsigned long *da, unsigned long *db, unsigned long *dq, unsigned long *dr)
{
LINT pdb;
unsigned long d1,d2,*dp1,*dp2,*dp3;
if (compare(da,db)>=0)
{
dp1=da;
dp2=dq;
dp3=dr;
for(d1=0;d1<=LENGTH;d1++)
{
pdb[d1]=0;
*dp2=0;
*dp3=(*dp1);
dp1++;
dp2++;
dp3++;
}
d2=(*da);
pdb[0]=(*da);
dp1=db+(*db);
for(d1=*db;d1>0;d1--,d2--,dp1--)
pdb[d2]=(*dp1);
while(compare(dr,pdb)>0)
shiftleft(pdb);
while(compare(dr,pdb)<0)
shiftright(pdb);
dp2=dq+1;
while((compare(db,dr)<=0)||(compare(db,pdb)<=0))
{
if(compare(dr,pdb)>=0)
{
sub(dr,pdb);
shiftright(pdb);
shiftleft(dq);
(*dp2)++;
if((*dq)==0)
(*dq)=1;
}
else
{
shiftright(pdb);
shiftleft(dq);
}
}
}
else
{
dp1=da;
dp2=dq;
dp3=dr;
for(d1=0;d1<=LENGTH;d1++)
{
(*dp2)=0;
(*dp3)=(*dp1);
dp1++;
dp2++;
dp3++;
}
}
}
void inverse( unsigned long *iva, unsigned long *ivn, unsigned long *ivb)
{
LINT y,g0,g1,g2,v0,v1,v2;
unsigned long *piv0,*piv1;
int ivcnt,ivrec;
piv0=ivn;
piv1=iva;
for(ivcnt=0;ivcnt<=LENGTH;ivcnt++,piv0++,piv1++)
{
g0[ivcnt]=(*piv0);
g1[ivcnt]=(*piv1);
v0[ivcnt]=0x0;
v1[ivcnt]=0x0;
}
v1[0]=1;
v1[1]=1;
while(g1[0]!=0)
{
division(g0,g1,y,g2);
ivrec=g1[0];
for(ivcnt=0;ivcnt<=ivrec;ivcnt++)
{
g0[ivcnt]=g1[ivcnt];
g1[ivcnt]=g2[ivcnt];
}
multiply(y,v1,v2);
while(compare(v0,v2)<0)
add(v0,ivn);
sub(v0,v2);
for(ivcnt=0;ivcnt<=LENGTH;ivcnt++)
{
v2[ivcnt]=v0[ivcnt];
v0[ivcnt]=v1[ivcnt];
v1[ivcnt]=v2[ivcnt];
}
}
for(ivcnt=0;ivcnt<=LENGTH;ivcnt++,ivb++)
*ivb=v0[ivcnt];
}
void hexout( unsigned long *num)
{
unsigned long c1,c2,*nptr;
if(*num==0) printf (" 0 \n");
else if (*num>=LENGTH) printf(" overflow \n");
else
{
nptr=num+(*num);
c1=*num;
c2=0;
while(*nptr==0)
{
nptr--;
c1--;
}
for(;c1>0;c1--)
{
printf("%08lx",*nptr);
if((c2%8)==7) printf("\n ");
nptr--;
c2++;
}
if((c2%8)!=0) printf("\n\n");
else printf("\n");
}
}
void getprime(unsigned int plen, unsigned long *pn)
{
LINT n210,nl;
unsigned long *ppn,gptmp;
int isget,gpcnt,plen1,plen2;
int p210[48]={1,11,13,17,19,23,29,31,37,41,43,47,53,59,61,
67,71,73,79,83,89,97,101,103,107,109,113,121,
127,131,137,139,143,149,151,157,163,167,169,173,
179,181,187,191,193,197,199,209};
plen1=plen/32;
plen2=plen%32;
if(plen2==0)
{
plen1--;
plen2=32;
}
plen1++;
bigrand(plen1,pn);
ppn=pn+plen1;
plen2=32-plen2;
gptmp=FULL>>plen2;
(*ppn)&=gptmp;
gptmp=LMASK>>plen2;
(*ppn)|=gptmp;
ppn=pn+1;
(*ppn)|=0x1;
ppn=pn;
for(gpcnt=0;gpcnt<=LENGTH;gpcnt++,ppn++)
{
n210[gpcnt]=0;
nl[gpcnt]=(*ppn);
}
n210[0]=1;
n210[1]=210;
mod(nl,n210);
plen1=nl[1];
gpcnt=0;
while(plen1>p210[gpcnt]) gpcnt++;
if(plen1<p210[gpcnt])
{
n210[1]=p210[gpcnt]-nl[1];
add(pn,n210);
}
nl[1]=p210[gpcnt];
isget=0;
plen2=0;
while(isget==0)
{
isget=primetest(pn);
plen2++;
if(isget==0)
{
gptmp=p210[gpcnt];
gpcnt++;
if(gpcnt==48)
{
nl[1]=2;
gpcnt=0;
}
else
{
nl[1]=p210[gpcnt]-gptmp;
}
add(pn,nl);
}
}
count=plen2;
}
void level_prime(unsigned int splen,unsigned long *spn)
{
LINT pt,ps,pr,prs,n_tmp;
unsigned long *psp;
int spcnt,spget,tplen,tmp1,tmp2;
for(spcnt=2;spcnt<=LENGTH;spcnt++)
n_tmp[spcnt]=0x0;
n_tmp[0]=1;
n_tmp[1]=1;
tplen=(int)(log((double)splen)+3);
spcnt=(splen-tplen)/2;
getprime(spcnt,ps);
spcnt=splen-tplen-spcnt;
getprime(spcnt,pr);
inverse(ps,pr,pt);
shiftleft(pt);
multiply(ps,pt,pt);
sub(pt,n_tmp);
multiply(pr,ps,prs);
shiftleft(prs);
for(spcnt=1;spcnt<=LENGTH;spcnt++)
pr[spcnt]=0;
tmp1=splen%32;
if(tmp1==0)
{
pr[0]=splen/32;
tmp2=pr[0];
pr[tmp2]=LMASK;
}
else
{
pr[0]=splen/32+1;
tmp2=pr[0];
pr[tmp2]=RMASK;
pr[tmp2]<<=(tmp1-1);
}
division(pr,prs,ps,n_tmp);
multiply(ps,prs,pr);
if(compare(pt,n_tmp)<0)
{
add(pt,pr);
add(pt,prs);
}
else add(pt,pr);
spcnt=0;
spget=0;
while(spget==0)
{
spget=primetest(pt);
spcnt++;
if(spget==0) add(pt,prs);
}
count=spcnt;
psp=spn;
for(spcnt=0;spcnt<=LENGTH;spcnt++,psp++)
*psp=pt[spcnt];
}
void rngout(unsigned long *pro)
{
LINT out;
unsigned long msk,i,j;
for(i=0;i<=10;i++,pro++)
{
out[i]=*pro;
if(i!=0)
{
msk=RMASK;
for(j=1;j<=32;j++)
{
if(out[i]&msk) printf("1");
else printf("0");
msk<<=1;
}
}
if(!(i%2)) printf("\n");
}
}
void rng( unsigned long *rn_add)
{
LINT rngn,rngx,rnge,rngz,rng_one;
unsigned long *rnp_add;
unsigned int b1,j;
int run=0;
char ch;
rnp_add=rn_add;
*rnp_add=10;
rnp_add++;
if(run==0)
{
b1=7;
bigrand(b1,rngx);
rngx[7]=(rngx[7]&RMASK);
*rngx=7;
rnge[0]=1;
rnge[1]=0x3;
for(j=2;j<=LENGTH;j++)
rnge[j]=0x0;
rngn[0]=17;
rngn[1]=0x52b10107;
rngn[2]=0x0fe4e0b0;
rngn[3]=0x16548d7d;
rngn[4]=0xd6df48a7;
rngn[5]=0x6d3f7d93;
rngn[6]=0x7b2aed38;
rngn[7]=0x3681f528;
rngn[8]=0x8c55df40;
rngn[9]=0x8d2f14c1;
rngn[10]=0x08833002;
rngn[11]=0xdb993815;
rngn[12]=0x5b068e40;
rngn[13]=0x542b99a0;
rngn[14]=0x1b7fd992;
rngn[15]=0xda5baffd;
rngn[16]=0x42205935;
rngn[17]=0x1;
rng_one[0]=1;
rng_one[1]=0x1;
for(j=2;j<=LENGTH;j++)
rng_one[j]=0x0;
}
modexp(rngx,rnge,rngn,rngz);
*rngz=17;
for(j=1;j<=7;j++)
rngx[j]=rngz[j+10];
add(rngx,rng_one);
for(j=1;j<=10;j++,rnp_add++)
*rnp_add=rngz[j];
run=1;
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -