ran.c

加密解密现代密码学的内容c语言编写uoto

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>

int gcd(unsigned long a,unsigned long b);
int Is_Prime(unsigned int p);
unsigned power(unsigned a,unsigned b,unsigned long c);



main()
{
    unsigned int p=10,q=10;
    unsigned long n;

    srand(time(NULL));


    while(!Is_Prime(p))
    p=50000+rand()%10000;
    while(!Is_Prime(q))
    q=10000+rand()%55535;
    n=(unsigned long)p*(unsigned long)q;

    printf("p= %u\n",p);
    printf("q= %u\n",q);
    printf("n= %lu\n-------------------\n",n);

    getchar();
    printf("%d\n",Is_Prime(47));
     getchar();
}

int gcd(unsigned long a,unsigned long b)
{
 unsigned long x,y,r ;  x=a; y=b;
 while(1){
 if(y==0)
    return 0;
 if(y==1)
    return 1;
 r=x%y;
 x=y;
 y=r;}
}

int Is_Prime(unsigned int p)
{
    int i;

    for(i=2;i<sqrt(p);i++)
        if((p%i)==0)
            return 0;

    return 1;
}


unsigned power(unsigned a,unsigned b,unsigned long c)
{
 /*此函数计算"a的b次方对c求余"*/

 unsigned long z=1,t;
 for(t=a;b>0;b>>=1)
 {
  /*每轮循环b右移1位是为了控制循环次数,可如下等价理解:*/
  /*将b写成二进制形式:mk,mk-1,mk-2------m0.其中k就是循环次数*/

  /* 在以下的注释中: "a(mk)"代表"a的mk次方","(a)(b)"代表"a的b次方",*/
  /* "[a]*[b]"代表"a*b"*/

  /* 此函数的原理是:*/
  /* b写成二进制形式后,"a的b次方"=a(b)=[(a(mk))(2(k))]*[(a(mk-1))(2(k-1))]*   */
  /* [(a(mk-2))(2(k-2))]----*[(a(m0))(2(0))].由此可见mi=0的项的值=1,因此这一项*/
  /* 不用累乘到"a的b次方"中,只有当mi=1时,才将[(a(mi))(2(i))]累乘到"a的b次方"中*/

   if(b%2==1)z=(z*t)%c;  /*z用来存放当前的"a的b次方"*/

   /* "b%2==1"说明b是奇数.当b是奇数时,b的二进制表示的最低位是1.又因为每次循环b*/
   /* 都右移1位,因此此时b的最低位其实是传入此函数的b的二进制表示的第j位*/
   /* j表示当前的循环次数,从0开始,二进制表示的位数从0开始. */

   /*对于传入此函数的b, 若其二进制表示第j位为1,即mj=1,则根据上面提到的此函数的*/
   /*原理,应将mj,mj-1,mj-2-------m0表示的十进制数(即[(a(mj))(2(j))])累乘到z中*/
   /*而[(a(mj))(2(j))]就是t*/

   t=(t*t)%c;

   /* 此函数实际操作时:*/
   /* t存放当前"a的i次方"的值(i=1,2,3----k)*/
   /* [(a(m))(2(i))]的值*/

  }
  return z;
 }