大整数算法[00] 概述

★ 为啥要做这个

        早在大一的时候，我便对密码学产生兴趣。那时在计算机导论后面看到RSA加密的计算原理，觉得十分有趣，于是就很想自己实现一个RSA加密，不过我很快就放弃了，因为实在搞不定那超长的整数计算。C里面最长的整数类型也就64位，对于动辄就1024位的RSA密钥，这连个零头都没有。为了完成这个目标，我便开始琢磨着弄一个用来计算大整数的库。原本我也打算使用别人已经写好的大数库，不过最终还是决定自己搞一个，因为凡是效率高速度快的大数库 （OpenSSL, Crypto++, GMP），要么使用的数据结构很复杂，要么编码风格比较奇葩，对于刚学编程的我来说水平和耐心都实在是有限，以至于无法完全读懂这些东西，有一些我能看明白的代码，其实现方式又比较幼稚，效率很低速度慢得一塌糊涂，最后想想，自己做一个的话不仅能弄明白大整数计算是如何实现的，而且也顺带提升一下自己的编码能力，何乐而不为呢？

        ★ 用途

        做一个项目，清晰的定位还是十分有必要的，不然容易偏离自己的初衷。对于这个大整数库，我的定位就是用于密码学（准确的说是公钥密码学），只做整数的计算，不做浮点数计算（那是给科学计算用的，加密完全用不上）

         ★ 要求

         虽然大整数算法的计算开销比其他算法的开销要大，但是通过精心的优化，大部分开销还是可以保持在较小的水平。对于我自己做的这个库，只要能接近OpenSSL的效率，我就满足了，但是代码尽量做到简洁易懂，不要像OpenSSL或者GMP那样太复杂。编程使用C语言，对于一些关键的地方，考虑使用内联汇编进行优化。

         ★ 本系列博文的内容

         本系列博文，主要是介绍大整数算法的实现，分享一些编程心得，顺带讲讲算法背后的一点点理论。

         ★ 参考的资料 本文章由 造句大全 www.zaojuzi.com 整理发布

         Handbook of Applied Cryptography ( HAC )

         BigNum Math-Implementing Cryptographic Multiple Precision Arithmetic

         OpenSSL

         PolarSSL

         LibTomMath

         ★ 结尾

         这个大整数库在2014年年初便开始动工，花了有大半年的时间来做，目前已经完工了，虽然跟其他的库比起来可能还有一些不足，但是我花在这上面的心血还是很大的，所以决定写点博文来分享一些自己的心得。

            为了方便阅读，把本系列博文的目录整理如下

         01. 大整数的表示和相关定义

         02. 基本的操作（维护算法）

         03. 比较操作

         04. 位设置操作

         05. 移位操作

         06. 绝对值加法

         07. 绝对值减法

         08. 有符号加法和减法

         09. Comba乘法

         10. Karatsuba乘法

         11. 有符号乘法

         12. Comba平方

         13. Karatsuba平方

         14. 有符号平方

         15. 带余数除法

          未完待续........

本文章由 造句大全 www.zaojuzi.com 整理发布