大数运算需要解决的问题
转载此文仅作参考，并不表示追风同意该文全部观点http://blog.icxo.com/read.jsp?aid=32454&uid=9169
本文适合那些正在或者将要进行大数运算的读者，对于其他读者，意义不大，大可就此打住。
如果你想要编程序自己实现一套大数运算，通过本文你将了解这一过程中你都需要做些什么；如果你正在使用某一第三方提供的大数运算，也可以通过本文更深入的了解其体系结构。
这里的大数，指的是超过计算机CPU寄存器表达的数，即超过计算机字长的数。大数运算主要指的是对大数进行数论运算，如加、减、乘、除。出于效率原因，一般的大数运算主要指对无符号类型的数进行数论计算。
为使用计算机解决大数运算，需要巧妙的做一些安排，以使得运算过程中效率最优、表达简单、转换便捷。下面逐条介绍大数运算需要解决的问题。
一.大数表达
>大数在计算机中的表示,包括存储方式和存储顺序。
A ：{ 0,1,2...};
二.大数基本运算
>大数加法。
w = u + v;
>大数增量。
w = u + 1;
>大数减法。
w = u - v;
>大数减量。
w = u - 1;
>大数乘法。
w = u * v;
>大数乘方（含平方）。
w = u * u ... * u;
>大数除法。
q = u / v;
>带余大数除法。
q = u / v ... r;
三.模算术
>大数模计算。
r = u mod m;
>大数模加法。
r = (u + v) mod m;
>大数模减法。
r = (u - v) mod m;
>大数模乘计算。
r = (u * v) mod m;
>大数模乘方。
r = (u * u * ... * u) mod m;
>大数模逆。
r = (u ^ -1) mod m;
四.位运算
>大数位置0，1。
w = setbit(u,pos,(0,1));
>大数位测试。
bool = testbit(u,pos,(0,1));
>大数位与。
w = u and v;
>大数位或。
w = u or v;
>大数位异或。
w = u xor v;
>大数左位移。
w = shl(u,n);
>大数右位移。
w = shr(u,n);
五.数论运算
>大数完全平方检验。
bool = issql(u);
>大数开方。
w = u root v;
>大数最大公约数。
w = gcd(u,v);
>大数最小公倍数。
w = lcm(u,v);
>大数素性检验。
bool = isprime(u)；
>大数素数产生。
u,v < prime();
六.伪随机数
>大数随机数初始化。
initrand(seed);
>大数随机数产生。
u = rand(seed);
七.比较
>大数比较。
bool = compare(u,v);
>大数是否是0。
bool = IsZero(u);
八.赋值
>大数赋值。
w = u;
>大数补码运算。
w = neg(u);
九.IO
>大数转换ASCII码。
w = itoa(u,base);
>ASCII码转换大数。
u = atoi(w,base);
>大数打印。
print(u);
>大数输入。
u = scanf();
十.大数应用
>大数RSA算法。
w = rsa(u,v,m); 以前曾看过该文。该文主要是讨论接口的，对算法没有深入，因此也就没再关注它。 文章在哪 无心人已经转载了，内容差不多了 大数运算中不应强求非要实现“RSA算法”的应用。
如果提供的算法函数模块够丰富，要实现某一具体加解密算法是很简单的。 因为RSA是个经典的应用实例，弄个例子也不错 可惜只是罗列了问题，
却没有给出每个问题的具体实现 关于如何写一个大数库，有很多开源的思想和代码，我比较欣赏的是Tom St Denis（及其团队）弄的个
数据加密的开源站，为了支撑这个Crypt项目，又扩展了对大数库的开发，我仔细的看过其代码和算法思想，并且在学习的过程中一个一个的敲了下来，感受很深。对大数库的编写有了一个详细的了解和全局的把握。
值得注意的是Tom St Denis写了一本关于这个库的书：《BigNum Math: Implementing Cryptographic Multiple Precision Arithmetic 》我看的是中文版，《BigNum Math：加密多精度算法的理论与实现》当你看完此书，一个大数库就实现了。像RSA公钥算法并不属于大数库的范畴，但大数库中的基本的数论算法是RSA必要的组成部分。
其开源站为：http://libtom.org/ 对于开源加免费，Tom St Denis的回答，我表示感触很深。
他说：“我有这个能力，并且我愿意”。
写的很好，好东西要分享，呵呵....Good Luck!! Mark, 有时间好好读一下 我上个月在学校图书馆就看到了这本书，那本书选择了libtom作为教学，而没有选择GMP，说是因为libtom的代码是平台无关的，而GMP的代码有太多的平台相关的if控制语句。
页:
[1]
2