mh.c

MH背包公钥密码算法的实现 MH背包公钥密码算法的实现

#include "stdlib.h"
int increase(int num,int a[])/*num为超递增的个数，数组a为存放生成的结果，且数组中只有0,num-1是有用数*/
{int i,sum;
randomize();/*随机函数的初始化，为库函数*/
a[0]=1+random(num);
sum=a[0];
for(i=1;i<num;i++)
  { a[i]=sum+1+random(i);
    sum=sum+a[i];
  }
}
求一个数w在MOD N 下的逆元w-1函数；
int inv(int xin,long n0)  /*求xin*xin-1=1 mod n0*/
{
long n1,n2,q,r,b1,b2,t;
if(xin==0)
  b2=0;
else
  { n1=n0;n2=xin;b2=1;b1=0;
    do{
      r=(n1%n2);
      q=(n1-r)/n2;
      if(r==0)
	{if(b2<0) b2=n0+b2;}
      else
	{n1=n2;n2=r;
	t=b2;
	b2=b1-q*b2;b1=t;
	}
      }while(r!=0);
    }
   return(b2);
}
求两个数的最大公约数函数，该函数可用于检测两个数是否互素；
int gcd(int a,int b)
{int t;
 t=a;
 while(!((a%t==0)&&(b%t==0))) t--;
 return t;
}
整数N和w选择函数；
sele_n_w(int num,int s[],int b[])/*num为超递增的个数,数组s为调用时传超递增数组的地址，数组b为存放N和w,其中b[0]存放N,b[1]存放w*/
{int i;
b[0]=2*s[num-1]+random(num)+1;
while(1)
  {
   b[1]=s[num-1]+random(s[num-1])+1;
   if(gcd(b[1],b[0])==1) break;
   }
}