sx.txt

应用加密算法和认证技术 实验：Solovag-Strassen算法、Lehmann算法和Rabin-Miller算法的素性检测的原理与测试过程。

#include"math.h"
#include"stdlib.h"
#include"stdio.h"
#include "time.h"
#include "iostream.h"

//__int64 b=0,m=0;


__int64 gcd(__int64 a,__int64 n)
{   __int64 tmp;
    if(a<0) a=-a;
    tmp=n;
    while(a>0)
    {
        tmp=a;
        a=n%a;
        n=tmp;
    }
    return tmp;
}

__int64 jacobi(__int64 a,__int64 n)
{
    __int64 g;
    if(a>=n) a%=n;
    if(a==0) return 0;
    if(a==1) return 1;
    if(a<0)
        if((n-1)/2%2==0)
            return jacobi(-a,n);
        else 
            return -jacobi(-a,n);
    if(a%2==0)
        if(((n*n-1)/8)%2==0)
            return +jacobi(a/2,n);
        else 
            return -jacobi(a/2,n);
    g=gcd(a,n);
    if(g==a)
        return 0;
    else if(g!=1)
        return jacobi(g,n);
    else if(((a-1)*(n-1)/4)%2==0)
        return +jacobi(n,a);
    else 
        return -jacobi(n,a);
}

__int64 times(__int64 a,__int64 m,__int64 n)
{   __int64 tmp,q;
    tmp=a%n;
    for(q=1;q<m;q++) tmp=(tmp*a)%n;
    return tmp;
}

//void mb(__int64 n)
//{   __int64 m,b;
 //   m=n-1;
 //   b=0;
 //   while(m/2!=0)
 //   {
 //       m/=2;
 //       b++;
 //   }
//printf("%I64d\n",m);
//printf("%I64d\n",b);
//}


solovag()
{
__int64 n,t,i,q,a,g,s,ja,jac;
__int64 randno[20];
printf("\n??ê?è??ì2aêy×?￡o");
scanf("%I64d",&n);
if(n==2) {printf("\n??êy￡?");return 1;}
if((n!=2)&&(n%2==0)) {printf("\no?êy￡?");return 1;}
printf("??ê?è?aμ???êy￡o");
    scanf("%I64d",&t);
   // randomize();
	srand( (unsigned)time( NULL ) );
    for(i=0;i<t;i++)
    {
        while(1)
        {
            q=rand();
            if(q<n) {randno[i]=q;break;}
        }
    }
    for(i=0;i<t;i++)
    {
        a=randno[i];
        //printf("%I64d\n",a);
        g=gcd(a,n);
        if(g!=1) {printf("\no?êy￡?");break;}
        s=(n-1)/2;
        ja=times(a,s,n);
        jac=jacobi(a,n);
	    if(jac<0)jac+=n;
        if(ja!=jac) {printf("\no?êy￡?");break;}
    } 
    if(ja==jac)
        {printf("?é?üê???êy￡?\n");
         printf("??D??¤êé?a:");
        for(i=0;i<t;i++)
            printf("%I64d  ",randno[i]);

        }



}

lehmann()
{   __int64 n,t,i,q,a,s,ja;
    __int64 randno[20];
    printf("\n??ê?è??ì2aêy×?￡o");
    scanf("%I64d",&n);
    if(n==2) {printf("\n??êy￡?");return 1;}
    if((n!=2)&&(n%2==0)) {printf("\no?êy￡?");return 1;}
    printf("??ê?è???è?aμ???êy￡o");
    scanf("%I64d",&t);
   // randomize();
	srand( (unsigned)time( NULL ) );
    for(i=0;i<t;i++)
    {
        while(1)
        {
            q=rand();
            if(q<n) {randno[i]=q;break;}
        }
    }
    for(i=0;i<t;i++)
    {
        a=randno[i];
        s=(n-1)/2;
        ja=times(a,s,n);
        if((ja==1)||(ja==n-1)) continue;
        else {printf("\no?êy￡?");break;}
    }  
    if(i>=t) 
    {
        printf("?é?üê???êy￡?\n");
        printf("??D??¤êé?a:");
        for(i=0;i<t;i++)

            printf("%I64d  ",randno[i]);

    }

}

rabin_miller()
{
    __int64 n,t,i,q,a,z,m,b,banner=0;  
    __int64 randno[20];
    printf("\n??ê?è??ì2aêy×?n￡o");
    scanf("%I64d",&n);
  //  printf("%I64d",n);
    if(n==2)
        {printf("\n??êy￡?");return ;}
    else
    if((n!=2)&&(n%2==0))
        {printf("\no?êy￡?");return ;}
    printf("??ê?è???è?aμ???êy￡o");
    scanf("%I64d",&t);
    //randomize();
	srand( (unsigned)time( NULL ) );
    for(i=0;i<t;i++)
    {
        while(1)
        {
            q=rand();
            if(q<n) {randno[i]=q;break;}
        }
    }
    //mb(n);
	m=n-1;
    b=0;
    while(m%2==0)
    {
        m/=2;
        b++;
    }
//	printf("%I64d\n",m);
//    printf("%I64d\n",b);
    for(i=0;i<t;i++)
    {
        a=randno[i];
        printf("%I64d\n",a);
        z=times(a,m,n);
        if(z==1||z==n-1) continue;
        for(q=0;q<b;q++)                         
        {
            z=(z*z)%n;
            if(z==n-1) break;
            if(z==1) {banner=0;break;}
        }
        if(q>0&&banner==0)
            {printf("o?êy￡?");break;}
        else continue;
    }
    if(i>=t) 
    {
        printf("?é?üê???êy￡?\n");
        printf("??D??¤êé?a:");
        for(i=0;i<t;i++)
              printf("%I64d  ",randno[i]);
     }


}


void main()
{
int cn;
while(1)
    {
        printf("\n                        Primality testing  \n");
        printf("                          1?￠Solovag-Strassen        \n");
        printf("                          2?￠Lehmann                 \n"); 
        printf("                          3?￠Rabin_Miller            \n");
        printf("                          0?￠exit                    \n");
        printf("                    \n");
        printf("please input the number￡o");
        scanf("%d",&cn);
        switch(cn)
        {
        case 1 : solovag();break;
        case 2 : lehmann();break;
        case 3 : rabin_miller();break;
        case 0 : exit(0);break;
        }
     }
}