不是非常完美的程序，用 gmp 调试 //**Solution to the Millionmaires' Problem #include #include #include #include unsigned int size_of(mpz_t op){ char *str; unsigned l,size; mpz_t tmp; mpz_init(tmp); l = 1000; while(1){ str = (char *)malloc(sizeof(char)*l); mpz_get_str(str,2,op); mpz_set_str(tmp,str,2); if(mpz_cmp(tmp,op) == 0) break; l = l * 100; } size = strlen(str); return size; } void RSA_gmp(mpz_t *d,mpz_t *e,mpz_t *n,unsigned int l) {//generate secret key d,e,n char *str; int size; unsigned long l1,l2,seed; mpz_t p,q,fn,fn_r,tmp;//,max; l1 = l / 2; mpz_init(p); mpz_init(q); mpz_init(fn); mpz_init(fn_r); mpz_init_set_ui(tmp,2); //mpz_init_set_ui(max,2); //mpz_pow_ui(max,2,l-1); mpz_pow_ui(tmp,tmp,l1-1); seed=rand()%(1<<31)+100; gmp_randstate_t state; gmp_randinit_default(state); //seed 在定义时，生成随机数。用 rand 后 seed 是定值 

gmp_randseed_ui(state,seed++); mpz_urandomb(p,state,l1-1); mpz_add(p,p,tmp); mpz_nextprime(p,p); l1 = size_of(p); mpz_set_ui(tmp,2); mpz_pow_ui(tmp,tmp,l-l1-1); while(1){ gmp_randseed_ui(state,seed++); mpz_urandomb(q,state,l-l1-1); mpz_add(q,q,tmp); mpz_nextprime(q,q); l2 = size_of(q); if(l = (l1 + l2)) break; } //Calculate for n=p*q //Calculate for fn=(p-1)*(q-1) mpz_mul(*n,p,q); mpz_sub_ui(p,p,1); mpz_sub_ui(q,q,1); mpz_mul(fn,p,q); mpz_sqrt(fn_r,fn); mpz_get_str(str,2,fn); l1=strlen(str); while(1){ //Geberate e ( sqrt(fn)fn_r) break; } mpz_invert(*d,*e,fn); } void E(mpz_t x,mpz_t d,mpz_t n,mpz_t *c) { mpz_powm(*c,x,d,n); } void D(mpz_t *x,mpz_t e,mpz_t n,mpz_t c) { mpz_powm(*x,c,e,n); } void Bob_random(mpz_t *x,unsigned N){ 

unsigned long seed; mpz_t tmp; mpz_init(tmp); mpz_set_ui(*x,2); mpz_pow_ui(*x,*x,N-1); seed=rand()%(1<<31)+100; gmp_randstate_t state; gmp_randinit_default(state); gmp_randseed_ui(state,seed++); mpz_urandomb(tmp,state,N-1); mpz_add(*x,*x,tmp); } void getPrime(mpz_t *p,unsigned l){ int counter = 1; unsigned long seed; mpz_t tmp,tmp1; mpz_init(tmp); mpz_init(tmp1); mpz_set_ui(*p,2); mpz_pow_ui(*p,*p,l-1); seed=rand()%(1<<31)+100; gmp_randstate_t state; gmp_randinit_default(state); gmp_randseed_ui(state,seed++); mpz_urandomb(tmp,state,l-2); mpz_add(*p,*p,tmp); mpz_nextprime(*p,*p); } int MSTMP(unsigned int Na,unsigned int Nb,unsigned int N,mpz_t d,mpz_t e,mpz_t n){ int i,j,flag,t,V,*Index,counter = 1,l; unsigned int k; mpz_t c,x,p,y[10],z[10],sendNum,tmp; mpz_init(c); mpz_init(x); mpz_init(p); mpz_init(tmp); Bob_random(&x,N); E(x,d,n,&c); k = Nb - 1; mpz_sub_ui(sendNum,c,k); V = 10; 

for(i=0;i= Na){ mpz_add_ui(z[i],z[i],1); mpz_mod(z[i],z[i],p); } mpz_mod(tmp,x,p); if(mpz_cmp(z[Nb-1],tmp) != 0) flag = -1; else flag = 1; //free(y);free(z); return flag; } void main(){ int i,j,i1,j1,flag,t,Num,*Index,counter = 1,l; unsigned int N,k,Na,Nb,*A,t1; mpz_t c,d,e,n,x,p,sendNum,tmp; mpz_init(c); mpz_init(d); mpz_init(e); mpz_init(n); 

mpz_init(x); mpz_init(p); mpz_init(tmp); mpz_init(sendNum); N = 200; printf("Input the number of millionaires:"); scanf("%d",&Num); Index = (int *)malloc(sizeof(int)*Num); A = (unsigned int *)malloc(sizeof(int)*Num); printf("Input the wealth of each millionaire:\n"); for(i=0;i x if(MSTMP(A[i],A[j],N,d,e,n) != 1){ t1 = A[i]; A[i] = A[j]; A[j] = t1; t = Index[i]; Index[i] = Index[j]; Index[j] = t; Na = A[i]; } } } printf("\nThe result of ordered is:"); for(i=0;i