1.头文件
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
2.判断大数是否为0
int big_num_is_zero(unsigned long *a, int len)
{
int i = 0;
for(i=0; i<len; i++)
{
if(a[i] > 0) return 0;
}
return 1;
}
3.大数加法
int big_num_add(unsigned long *a, unsigned long *b, unsigned long *c, int len)
{
int u = 0;
int v = 0;
int i = 0;
for(i=len-1; i>=0; i--)
{
c[i] = a[i] + b[i];
if(c[i] < a[i] || c[i] < b[i])
{
u = 1;
}
else
{
u = 0;
}
if(c[i] + v < c[i])
{
c[i] += v;
u = 1;
}
else
{
c[i] += v;
}
v = u;
}
return v;
}
4.大数减法
int big_num_sub(unsigned long *a, unsigned long *b, unsigned long *c, int len)
{
int u = 0;
int v = 0;
int i = 0;
for(i=len-1; i>=0; i--)
{
c[i] = a[i] - b[i];
//printf("a=[%08x], b=[%08x], c=[%08x]\n", a[i], b[i], c[i]);
if(c[i] > a[i])
{
u = 1;
}
else
{
u = 0;
}
//printf("u=[%d], v=[%d]\n", u, v);
if(c[i] - v > c[i])
{
c[i] -= v;
u = 1;
}
else
{
c[i] -= v;
}
v = u;
//printf("v=[%d]\n", v);
}
return v;
}
5.大数右移
int big_num_sfr(unsigned long *a, unsigned long *b, int len, int w)
{
unsigned long c[len];
int u = w / 32;
int v = w % 32;
int i = 0;
for(i=0; i<u; i++)
{
c[i] = 0;
b[i] = 0;
}
for(i=len-1; i>=u; i--)
{
c[i] = a[i-u];
}
if(v)
{
//printf("v=[%d]\n", v);
for(i=len-1; i>=u; i--)
{
b[i] = (c[i] >> v);
if(i>u) b[i] |= (c[i-1] << (32-v));
}
}
else
{
for(i=len-1; i>=u; i--)
{
b[i] = c[i];
}
}
return 0;
}
6.大数求模
int big_num_sfl_a(unsigned long *s, unsigned long *a, unsigned long *d, int len, int w)
{
unsigned long b[len];
unsigned long c[len];
int u = w / 32;
int v = w % 32;
int i = 0;
for(i=0; i<u; i++)
{
c[len-1-i] = 0;
b[len-1-i] = 0;
}
for(i=len-1-u; i>=0; i--)
{
c[i] = a[i+u];
}
if(v)
{
for(i=len-1-u; i>=0; i--)
{
b[i] = c[i] << v;
if(i<len-1-u) b[i] |= (c[i+1] >> (32-v));
}
}
else
{
for(i=len-1-u; i>=0; i--)
{
b[i] = c[i];
}
}
//printf("s: ");
//print_num(s, len);
//printf("c: ");
//print_num(c, len);
//printf("b: ");
//print_num(b, len);
return big_num_sub(s, b, d, len);
}
int big_num_sfl_b(unsigned long *s, unsigned long *a, unsigned long *d, int len)
{
int u = 0;
int i = 0;
for(i=0; i<len*32; i++)
{
u = big_num_sfl_a(s, a, d, len, i);
//printf("i=[%d], u=[%d]\n", i, u);
if(u) break;
}
//if(i == len*32) exit(0);
//printf("sfl_b: i=[%d]\n", i);
if(i) big_num_sfl_a(s, a, d, len, i-1);
else memcpy(d, s, 4*len);
return i;
}
int big_num_mod(unsigned long *a, unsigned long *b, unsigned long *c, int len)
{
unsigned long d[len];
unsigned long e[len];
unsigned long f[len];
unsigned long g[len];
unsigned long h[len];
int w = 1;
memset(d, 0x00, sizeof(d));
memset(e, 0x00, sizeof(e));
memset(f, 0x00, sizeof(f));
memset(g, 0x00, sizeof(g));
memset(h, 0x00, sizeof(h));
memcpy(e, a, len*4);
d[len-1] = 1;
//printf("e[0]=[%08x], e[1]=[%08x]\n", e[0], e[1]);
//printf("b[0]=[%08x], b[1]=[%08x]\n", b[0], b[1]);
w = big_num_sfl_b(e, b, f, len);
//printf("w=[%d]\n", w);
while(w > 0)
{
memcpy(e, f, len*4);
big_num_sfl(d, g, len, w-1);
big_num_add(h, g, f, len);
memcpy(h, f, len*4);
w = big_num_sfl_b(e, b, f, len);
//printf("w=[%d], len=[%d]\n", w, len);
}
//printf("u, ");
//print_num(h, len);
memcpy(c, e, len*4);
return 0;
}
7.幂模运算
int big_num_pow_mod(unsigned long *a, unsigned long *b, unsigned long *c, unsigned long *s, int len)
{
unsigned long d[len*2];
unsigned long e[len*2];
unsigned long f[len*2];
unsigned long g[len*2];
unsigned long h[len*2];
unsigned long p[len*2];
memset(d, 0x00, sizeof(d));
memset(e, 0x00, sizeof(e));
memset(f, 0x00, sizeof(f));
memset(p, 0x00, sizeof(p));
e[2*len-1] = 1;
memcpy((char *)(d+len), (char *)b, 4*len);
memcpy((char *)(f+len), (char *)a, 4*len);
memcpy((char *)(p+len), (char *)c, 4*len);
while(!big_num_is_zero(d+len, len))
{
printf("b: ");
print_num(d, len*2);
if(d[2*len-1] % 2 == 1)
{
memset(g, 0x00, sizeof(g));
memset(h, 0x00, sizeof(h));
big_num_mul(f+len, e+len, g, len);
//printf("e, ");
//print_num(e, len*2);
//printf("g, ");
memset(g, 0x00, sizeof(g));
memset(h, 0x00, sizeof(h));
big_num_sfr(d, g, 2*len, 1);
memcpy(d, g, 8*len);
//printf("b: ");
//print_num(d, len*2);
memcpy(g, f, 8*len);
big_num_mul(f+len, g+len, h, len);
//printf("h: ");
//print_num(h, 2*len);
big_num_mod(h, p, f, 2*len);
//printf("f: ");
//print_num(f, 2*len);
}
memcpy((char *)s, e+len, 4*len);
return 0;
}
7.大数乘法
参见<<C语言实现大数乘法>>部分
8.主函数部分
int main()
{
unsigned long a[32] = {0xeedaddd8, 0x8bfcfeb2, 0xda188373, 0x9cad9f06, 0x09448544, 0x9b0904d7, 0xb120f751, 0x27fa7af5, 0x12c08607, 0xa25f1359, 0xdcee9b8f, 0xc88f9fcf, 0x8dc4669f, 0xe5223c46, 0x542829e4, 0xf47b813b, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
unsigned long b[32] = {0x89f8abf2, 0xcd9f2400, 0x941e7c8b, 0x3c17944f, 0x9eec9c04, 0x238e8aec, 0x67b8f6b4, 0xfca12f84, 0x0e90d35e, 0xa63b6a35, 0x0b1444d2, 0x703abf3b, 0x888cba8b, 0xcfc9be98, 0xc450dd3a, 0x1d5d3963, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
unsigned long c[32] = {0x29AADDDE, 0x36EE4206, 0x61BBFF16, 0xD37FCD9A, 0xCE0A462D, 0xA66AB047, 0xF37C6C13, 0x4D5BBF19, 0x1A18864E, 0x06CF1F90, 0xC9A32936, 0xCD8D4C62, 0x3389F934, 0x0B494395, 0x0750E837, 0xD00EA9F5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
//unsigned long a[2] = {0xcebd4c1e, 0x8f57f885};
//unsigned long c[2] = {0};
unsigned long d[32] = {0};
unsigned long f[32] = {0};
unsigned long g[32] = {0};
unsigned long h[32] = {0};
unsigned long p[32] = {0};
d[15] = 2;
d[31] = 1;
big_num_sub(a, d+16, g, 16);
big_num_pow_mod(d, g, a, p, 16);
print_num(a, 16);
print_num(g, 16);
print_num(d, 16);
print_num(p, 16);
return 0;
}
