#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <string.h>
#include <math.h>
#define maxlen 150
#define base 28
unsigned long long int primes[20][10] = {
{9, 19, 21, 55, 61, 69, 105, 111, 121, 129},
{3, 17, 27, 33, 57, 87, 105, 113, 117, 123},
{15, 21, 27, 37, 61, 69, 135, 147, 157, 159},
{3, 17, 33, 63, 75, 77, 89, 95, 117, 167},
{39, 49, 61, 85, 91, 115, 141, 159, 165, 183},
{5, 27, 45, 87, 101, 107, 111, 117, 125, 135},
{39, 79, 111, 115, 135, 187, 199, 219, 231, 235},
{57, 89, 95, 119, 125, 143, 165, 183, 213, 273},
{3, 33, 43, 63, 73, 75, 93, 99, 121, 133},
{35, 41, 83, 101, 105, 107, 135, 153, 161, 173},
{1, 19, 61, 69, 85, 99, 105, 151, 159, 171},
{5, 17, 65, 99, 107, 135, 153, 185, 209, 267},
{9, 25, 49, 79, 105, 285, 301, 303, 321, 355},
{41, 77, 113, 131, 143, 165, 185, 207, 227, 281},
{31, 49, 61, 69, 79, 121, 141, 247, 309, 325},
{5, 17, 23, 65, 117, 137, 159, 173, 189, 233},
{25, 31, 45, 69, 123, 141, 199, 201, 351, 375},
{45, 87, 107, 131, 153, 185, 191, 227, 231, 257},
{7, 19, 67, 91, 135, 165, 219, 231, 241, 301},
{87, 167, 195, 203, 213, 285, 293, 299, 389, 437}
};
typedef struct bignum bignum;
struct bignum {
int place[maxlen];
};
void copyBignum(bignum * a, bignum * b) {
int i;
for(i=0;i<maxlen;i++) a->place[i] = b->place[i];
}
void shiftleft(bignum * n, int d) {
int c;
for(c=maxlen-1-d;c>=0;c--) n->place[c+d] = n->place[c];
for(c=0;c<d;c++) n->place[c] = 0;
}
void shiftRight(bignum * n) {
int c;
for(c=0;c<=maxlen-2;c++) n->place[c] = n->place[c+1];
n->place[maxlen-1] = 0;
}
bignum * initBignum() {
bignum * newbignum = (struct bignum*)malloc(sizeof(bignum));
int c;
for(c=0;c<maxlen;c++) newbignum->place[c] = 0;
return newbignum;
}
void intToBignum(unsigned long long int i, bignum * a) {
unsigned long long int x = i;
int c;
for(c=0;c<maxlen;c++) a->place[c] = 0;
for(c=0;x>0 && c<maxlen;x/=base, c++) a->place[c] = x % base;
}
void printBignum(bignum * a) {
int c;
for(c=maxlen-1;c>0 && a->place[c]==0;c--);
for(;c>=0;c--) printf("%d", a->place[c]);
printf("\n");
}
bool isNotZero(bignum * n){
int c;
for(c=0;c<maxlen;c++) if(n->place[c]!=0) return true;
return false;
}
bool equals(bignum * a, bignum * b) {
int c;
for(c=0;c<maxlen;c++) if(a->place[c]!=b->place[c]) return false;
return true;
}
bool isGreaterThan(bignum * a, bignum * b) {
int c;
for(c=maxlen-1;c>0 && a->place[c] == b->place[c];c--);
if(a->place[c]>b->place[c]) return true;
return false;
}
bool isLessThan(bignum * a, bignum * b) {
int c;
for(c=maxlen-1;c>0 && a->place[c] == b->place[c];c--);
if(a->place[c]<b->place[c]) return true;
return false;
}
bool isLessThanOrEqualTo(bignum * a, bignum * b) {
if(isLessThan(a, b)) return true;
if(equals(a, b)) return true;
return false;
}
bool isGreaterThanOrEqualTo(bignum * a, bignum * b) {
if(isGreaterThan(a, b)) return true;
if(equals(a, b)) return true;
return false;
}
bignum * plus(bignum * a, bignum * b) {
bignum * sum = initBignum();
int carry = 0, p;
for(p=0;p<maxlen;p++) {
sum->place[p] = (a->place[p] + b->place[p] + carry) % base;
carry = (a->place[p] + b->place[p] + carry) / base;
}
return sum;
}
bignum * minus(bignum * a, bignum * b) {
bignum * diff = initBignum();
int borrow = 0, p, d;
for(p=0;p<maxlen;p++) {
diff->place[p] = a->place[p] - borrow - b->place[p];
borrow = 0;
if(diff->place[p]<0) {
diff->place[p] += base;
borrow = 1;
}
}
return diff;
}
bignum * times(bignum * a, bignum * b) {
bignum r;
bignum * product = initBignum();
bignum * temp;
int c, c2;
r = *a;
for(c=0;c<maxlen;c++) {
for(c2=1;c2<=b->place[c];c2++){
temp = plus(product, &r);
copyBignum(product, temp);
free(temp);
}
shiftleft(&r, 1);
}
return product;
}
bignum * divide(bignum * a, bignum * b) {
bignum * r = initBignum(), * temp = initBignum(), * quotient = initBignum();
int c, c2;
for(c=maxlen-1;c>=0;c--) {
shiftleft(r, 1);
r->place[0] = a->place[c];
quotient->place[c] = 0;
while(isGreaterThanOrEqualTo(r, b)) {
quotient->place[c]++;
temp = minus(r, b);
copyBignum(r,temp);
free(temp);
}
}
free(r);
return quotient;
}
bignum * modBignum(bignum * a, bignum * b){
bignum * temp = divide(a, b);
bignum * temp2 = times(b, temp);
free(temp);
temp = minus(a, temp2);
free(temp2);
return temp;
}
bignum * gcdBignum(bignum * a, bignum * b) {
bignum * temp = initBignum();
if(equals(b, temp)) {
free(temp);
return a;
} else {
free(temp);
return gcdBignum(b, modBignum(a,b));
}
}
bignum * raiseTo(bignum * a, bignum * b){
bignum counter = *b;
bignum * temp2;
bignum * product = initBignum();
intToBignum(1, product);
bignum * one = initBignum();
intToBignum(1, one);
while(isNotZero(&counter)) {
temp2 = times(product, a);
copyBignum(product,temp2);
free(temp2);
temp2 = minus(&counter, one);
copyBignum(&counter, temp2);
free(temp2);
}
free(one);
return product;
}
bignum * randomBignumPrime() {
bignum * prime;
bignum * two = initBignum();
bignum * n = initBignum();
bignum * k = initBignum();
bignum * temp;
int intn = rand() % 20;
intToBignum(2, two);
intToBignum(intn+21, n);
intToBignum(primes[intn][rand() % 10], k);
prime = raiseTo(two, n);
temp = minus(prime, k);
copyBignum(prime, temp);
free(temp);
free(k);
free(n);
free(two);
return prime;
}
bignum * modInverseBignum(bignum * e, bignum * phi) {
bignum * a = initBignum();
bignum * b = initBignum();
bignum * q = initBignum();
bignum * x = initBignum();
bignum * lastx = initBignum();
intToBignum(1, lastx);
bignum * temp;
bignum * tempp;
bignum * temp2 = initBignum();
copyBignum(a, e);
copyBignum(b, phi);
while(isNotZero(b)) {
temp = divide(a, b);
copyBignum(q, temp);
free(temp);
copyBignum(temp2, b);
temp = modBignum(a, b);
copyBignum(b, temp);
free(temp);
copyBignum(a, temp2);
copyBignum(temp2, x);
temp = times(q, x);
tempp = minus(lastx, temp);
free(temp);
copyBignum(x, tempp);
free(tempp);
copyBignum(lastx, temp2);
}
temp = plus(lastx, phi);
free(a);
free(b);
free(q);
free(x);
free(lastx);
free(temp2);
return temp;
}
bignum * modExpoBignum(bignum * b, bignum * exp, bignum * mod) {
bignum * temp;
bignum * tempp;
bignum * c = initBignum();
intToBignum(1, c);
bignum * e = initBignum();
intToBignum(1, e);
bignum * one = initBignum();
intToBignum(1, one);
while(isLessThanOrEqualTo(e,exp)) {
temp = times(c,b);
tempp = modBignum(temp,mod);
copyBignum(c, tempp);
free(tempp);
free(temp);
temp = plus(e, one);
copyBignum(e, temp);
free(temp);
}
return c;
}
bignum * modExpoBignumEx(bignum * b, bignum * exp, bignum * mod) {
bignum * temp;
bignum * temp2;
bignum * c = initBignum();
intToBignum(1, c);
bignum * e = initBignum();
copyBignum(e, exp);
bignum * bb = initBignum();
copyBignum(bb, b);
bignum * two = initBignum();
intToBignum(2, two);
while(isNotZero(e)) {
if(e->place[0]%2 == 1) {
temp = times(c, bb);
temp2 = modBignum(temp, mod);
free(temp);
评论0