大数运算需要解决的问题

无心人

转载此文仅作参考，并不表示追风同意该文全部观点

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);

liangbch

　以前曾看过该文。该文主要是讨论接口的，对算法没有深入，因此也就没再关注它。

wayne

文章在哪

qianyb

无心人已经转载了，内容差不多了

gxqcn

大数运算中不应强求非要实现“RSA算法”的应用。 如果提供的算法函数模块够丰富，要实现某一具体加解密算法是很简单的。

qianyb

因为RSA是个经典的应用实例，弄个例子也不错

wayne

可惜只是罗列了问题， 却没有给出每个问题的具体实现

G-Spider

关于如何写一个大数库，有很多开源的思想和代码，我比较欣赏的是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!!

liangbch

Mark, 有时间好好读一下

wayne

我上个月在学校图书馆就看到了这本书，那本书选择了libtom作为教学，而没有选择GMP，说是因为libtom的代码是平台无关的，而GMP的代码有太多的平台相关的if控制语句。