CSK.Blog--个人原创Weblog

« 暑假回顾gift:多彩Console输出函数 »

我写的大整数以及素域运算库

这个库叫做CiperLib,是我暑假在密码学实验室作的作品。比较工程化的东西,不过比较实用,所以就公布了。

下面是他的简介,我直接从他的说明文档中复制了,如果你完全知道他的作用,那么直接去文章末尾的链接下载。

 

 

CipherLib是一个使用C++和汇编代码实现的用于多精度大整数运算和密码学领域素域基本运算的函数库。由陈士凯(CSK)开发。
这个函数库实现的操作有:

  1. 支持任意精度的大整数:精度可以通过代码设定,支持符号数
  2. 对大整数的四则运算和求模运算,以及2进制化的移位操作
  3. 使用类将大整数加以封装,支持直接用传统运算符进行大整数的运算代码编写
  4. 支持从文本串和系统内置整型数据中读取大整数,支持将大整数输出为2进制、8进制、10进制和16进制文本串
  5. 实现了Marsaglia & Zaman的长周期随机数(本机支持的整型格式)
  6. 支持模加、模乘、模幂计算
  7. 支持Rabin-Miller方法的素性验证
  8. 支持大素数产生

 简单的说可以利用这个库实现一些高精度计算和密码算法,比如RSA。


 

该函数库在设计上参考了mircal库,在核心的运算操作上使用了x86汇编语言和C语言2种版本代码编写。默认采用汇编语言执行。因而具有很高的运行效率(具体见Benchmark部分)
 
CipherLib的一些技术信息:
项目
说明
运行环境
32x86指令系统下的windows环境
开发环境
VC++ 2005版本
是否多线程安全
函数库形式
静态链接库或者直接嵌入代码
第三方库依赖
需要C运行库

 

Benchmark

 

下面是我写的对于CipherLib和mircal的一个运行效率比较(不过不是很科学,但是基本可以说明问题):

使用附带的程序CiperBench进行测试。
         测试程序在开发者电脑环境:Intel Pentium M 1.6G ,2G RAM,WinXP sp2环境中,对于静态库的本函数库和Mircal进行比较。
 
         由于采用了timeGetTime() API获取时间,因此精度可能会受偶尔系统调度的影响。
下面是对1000次的四则运算的执行时间对比,本函数库表现较优:

对于乘法的实测情况

对于加法的实测情况

对于减法的实测情况

对于除法的实测情况

对于求大素数的实测情况

 

 

 

 

对于素域运算,使用了产生一个大素数的运算作为衡量指标,因为其中需要进行素性验证和模乘和模幂运算。本函数库效率较低,原因是没有针对素性验证是的模幂运算单独进行优化。


我用于求模幂的算法是Koch提出的Sliding Window法。但是对于求素性验证来说不是最优的。

 


 使用范例

 

下面是用本函数库求解1000!的代码,从代码风格上可以看出他的易用性,具体代码和使用办法见文章末尾给出的文件中的操作手册。

#include "CiperLib.h"
#include <iostream>
using namespace std;
int _tmain(int argc, _TCHAR* argv[])
{
    Integer::Init(409600);
    char output[20000];
    Integer Base(1000),Ans(1);
    while(!Base.isZero())
    {
        Ans *= Base;
        Base -= 1;
    }
    Ans.toString(output,20000);
    cout<<"Finished, Ans is:"<<endl<<output <<endl;
    system("pause");
}

 

下面很简单的说下实现的细节

大整数是采用2^32进制保存的,也就是用一个DWORD存储一个“位”。对于四则运算均使用汇编优化,其中算法参见Knuth的the Art of Computer Program 第二卷的多精度计算。

对于素域的计算,主要采用的就是窗口法求模幂,素性验证使用了Rabin-Miller法,并且进行了100次判断,可以确保相当高的正确概率。

注意的是,我不能保证潜在的bug,同时一些算法并不是最优的,所以使用时请自己注意。而且今后基本无法维护了。对于具体的实现,可以看代码注释以及我附在其中的实习报告

代码/Demo/文档的下载:

http://www.csksoft.net/data/legacyftp/Products/code_and_lib/CiperLib_release_by_csk.rar

教育网:ftp://great_csk:public@public.sjtu.edu.cn/public-files/CiperLib_release_by_csk.rar

  • 相关文章:
  • quote 1.TonyHuang
  • 写的很好。。。
    比较认同采用2^32进制的做法,可以很好的利用机器的指令优化:)
    让toString慢去吧,毕竟用的很少:)
  • 9/10/2007 8:21:44 PM 回复该留言
  • quote 2.默默
  • 学习:能不能用VB做RSA的大素数运算?怎么编?
    谢谢……
  • 4/24/2008 1:16:30 AM 回复该留言
  • quote 6.pinuo
  • 最近搜大整数运算找到这里来了,谢谢楼主的代码,先下来研究研究
  • 2/10/2010 9:26:21 AM 回复该留言

发表评论:

注意:为了有效防止SPAM,任何含有http://字样的消息会被阻止发布同时,本站仅供技术交流,请不要讨论任何政治敏感话题或者低级趣味问题。

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

日历

最新评论及回复

最近发表

Copyright Shikai Chen 2000-2012. Powered By Z-Blog(CSK Modified)