当前位置：文档之家 › 大整数乘法的实现与分析

大整数乘法的实现与分析

  • 格式：doc
  • 大小：1.16 MB
  • 文档页数：63

课程设计大整数乘法的实现与分析课程名称______________________ 题目名称______________________ 学生学院______________________ 专业班级______________________ 学号______________________学生姓名______________________ 指导教师______________________2008年 6 月摘要随着计算机信息安全要求的不断提高,密码学被大量应用到生活中。

RSA、ElGamal、DSA、ECC 等公钥密码算法和数字签名算法都建立在大整数运算的基础上，比较耗时的大整数乘法、模乘、幂运算、模幂乘运算等却被上述算法大量使用，它们的运算速度对这些算法的高效实现起着重要的作用，如何快速实现上述几种运算是公钥密码领域普遍关注的热点问题。

本文基于32位的系统，首先采用模块化的思想建立大整数运算库的基础框架，在实现一些辅助函数后在此框架上讨论并实现多精度大整数的基本乘法、Comba乘法、Karatsuba乘法、各种平方算法、Barrett缩减、Mentgomery缩减、模乘、Mentgomery 模幂乘等算法及相关的算法。

本文讨论的所用程序均采用C语言编写，所采用的优化也均建立在C语言这一层面上，在保证算法有足够高的效率的同时力求代码清晰易懂，函数接口简单明了，具有可移植性和稳定性。

关键词：多精度大整数，缩减，模幂乘，滑动窗口AbstractNowadays, as computer information security requirements improve continuously, the cryptology is widely applied to life. Public key cryptographic algorithms and digital signature algorithms such as RSA, ElGamal, DSA, ECC are all base on multiple precision arithmetic. Multiple precision multiplication, modular multiplication ,exponentiation, modular exponentiation which need more working time is used by public key cryptographic algorithms widely, their speed is very important to the implementations of those algorithms. How to fast implement those arithmetic above is the hot topic in the public key cryptographic field.This paper is based on the 32 bit system. First, we found the modular foundation of multiple precision arithmetic library; After some auxiliary function is formed, we discuss and implement the multiple precision integer basic multiplication, Comba multiplication, Karatsuba multiplication, kinds of square algorithms, Barrett reduction, Montgomery reduction, Montgomery Modular Exponentiation algorithm and some relational function. All the algorithms discuss in this paper is implement entirely in portable ISO C and the optimization of those algorithms implementations is built on the c language level. Clear code, simple application programming interface is as important as the efficiency, the robustness and the portability.Key words:Multiple Precision Integer，Reduction，Modular Exponentiation，Sliding Window目录1 绪论 (1)1.1题目背景 (1)1.2国内外研究状况 (1)1.3本文构成及研究内容 (2)2 基础设置 (3)2.1大整数的表示 (3)2.2部分预定义的量 (4)2.3底层函数 (5)2.3.1 初始化大整数 (5)2.3.2 清除大整数 (6)2.3.3 扩展大整数的精度 (6)2.3.4 把一个大整数赋值给另一大整数 (6)2.3.5 格式化的表示 (6)3 特殊优化 (7)3.1字移位 (7)3.2乘以2或除以2 (7)3.3乘以或除以2的幂 (8)3.4模2的幂 (10)4 乘法 (12)4.1传统的乘法 (12)4.2使用C OMBA思想的乘法 (14)4.3只计算低半部或高半部的乘法 (17)4.4K ARATSUBA乘法 (17)4.5平方 (22)4.5.1 基本的平方算法 (22)4.5.2 使用Comba思想的平方 (24)4.5.3 Karatsuba平方 (26)5 模缩减 (27)5.1B ARRETT缩减 (27)5.2M ONTGOMERY缩减 (30)6 幂乘 (33)6.1幂乘概述 (33)6.1.1 字幂乘 (34)6.2K-RAY幂乘 (35)6.2.1 滑动窗口幂乘 (36)6.3模幂乘 (36)结论 (43)参考文献 (44)附录 (46)1 绪论1.1 题目背景科技的发展特别是网络的发展使计算机深入到了各行各业的方方面面，计算机在带来方便和提高了工作效率的同时却也带来了各种各样的新问题，其中信息安全问题最为突出，随着计算机信息安全要求的不断提高, 计算机保密系统已变得越来越重要，密码学应用不再是局限于军事、国防等有限领域，而是迅速的走进了千家万户，如CA 认证、电子政务、电子商务、数字签名、身份认证、密钥分发等。

RSA、ElGamal、DSA、ECC 等公钥密码算法和数字签名算法都建立在大整数运算的基础上，耗时的大整数乘法、模乘、幂运算、模幂乘运算等更是被上述算法大量使用，它们的运算速度对这些算法的高效实现起着重要的作用，如何快速实现上述几种运算是公钥密码领域普遍关注的热点问题。

1.2 国内外研究状况长期以来，各方面的工作者对大数模幂的快速实现问题进行了大量研究，主要围绕模幂算法设计与优化、模乘算法设计与优化、专用芯片设计等，并且已经取得不少研究成果。

模幂通常都转化为一系列模乘和模平方运算，目前较好的算法已经能够将1次n 比特数的模幂运算转化为约5n/4 次n比特的模乘运算，再减少模乘的次数的难度很大，因此，提高模乘的速度是模幂快速实现的关键[1]。

目前，模乘主要有估商型、加法型和Montgomery 型3 类方法。

1960 年，Pope 和Stein 就提出了采用估商方法将模乘转化为一系列乘法和除法进行计算的思想；1981 年，Knuth具体给出了一种转换为乘法和除法的估商型模乘算法[2]；1987年，Barrett 提出了一种转换为乘法和加法而没有除法的估商型模乘算法[3]。

1983 年，Blakley 提出了一种加法型模乘算法，其设计思想是将模乘转换为一系列加法[4]。

为减少加法次数，人们提出了窗口模乘算法和滑动窗口模乘算法，并相继提出了不少改进方法，获得较理想的结果。

1985 年Montgomery 提出了一种计算模乘的有效算法，其设计思想是将普通模乘转换为易于计算的特殊模乘[5]。

此后，人们提出了不少基于Montgomery思想的改进算法，并得到了广泛的实际应用。

大多数情况下，一种算法的理论描述和实际实现之间有不小的差距，是两个完全的不同的概念，因此，众多学者为这些优秀算法的具体的软、硬件实现、优化付出了辛勤的汗水，在软件实现方面这些算法多数被包含在某些算法库中，其中也有不少是开放源代码的算法函数库，最著名的就是GNU的号称地球上最快的多精度大数库GMP，还有Miracl、openssl、cryptopp、cryptlib、flint等优秀的算法库，而我国的郭先强先生的HugeCalc.dll库也同样出名，虽然它不是开放源码的，但它的速度赶得上GMP甚至在某些方面超越了GMP[6]。

然而，正如Tom St Denis所说，不存在一个易懂的大数库[7]！从目前收集到的信息看，凡是效率高的算法实现，要么结构复杂、层次庞大，要么编码风格奇特；所有速度快的库都使用了汇编，同时大部分都使用了MMX、SSE2、SIMD系列指令作加速，也对多核心CPU进行了优化，使用了多线程等，甚至运行时监测CPU类型而使用相关的特殊优化，最大限度地榨取CPU的性能。

然而，这些很好的优化技术却大大地降低了代码的可读性，极大地提高了理解、学习的门槛。

在学术专著方面，大数算术也备受欢迎，Donald E.Knuth也用了一整本书——《The Art of Computer Programming Volume 2》来从理论的角度讲述了多精度算术，并讲解了高效的算法背后关键的数学概念；《Handbook of Applied Cryptography》[8]也讲述了应用密码学相关的大数算术算法的有效实现；而《Kryptographie in C und C++》[9]和《BigNum Math: Implementing Cryptographic Multiple Precision Arithmetic》等则从编码学的角度对大数算术进行了多方面的讨论。

1.3 本文构成及研究内容本文基于32位的系统，首先采用模块化的思想建立大整数运算库的基础框架，在实现一些辅助函数后在此框架上讨论并实现多精度大整数的基本乘法、Comba乘法、Karatsuba乘法、各种平方算法、Barrett缩减、Mentgomery缩减、模乘、Mentgomery 模幂乘等算法及相关的算法。

合集下载

分治法解决大整数乘法问题

分治法解决大整数乘法问题

分治法解决大整数乘法问题通常，在分析算法的计算复杂性时，都将加法和乘法运算当作基本运算来处理，即将执行一次加法或乘法运算所需的计算时间，当作一个仅取决于计算机硬件处理速度的常数。

这个假定仅在参加运算的整数能在计算机硬件对整数的表示范围内直接处理才是合理的。

然而，在某些情况下，要处理很大的整数，它无法在计算机硬件能直接表示的整数范围内进行处理。

若用浮点数来表示它，则只能近似的表示它的大小，计算结果中的有效数字也受到限制。

若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字，就必须用软件的方法来实现大整数的算术运算。

设X和Y都是n位的二进制整数，现在要计算它们的乘积Z。

可以用小学所学的方法来设计计算乘积XY的算法，但是这样做计算步骤太多，效率较低。

如果将每2个1位数的乘法或加法看作一步运算，那么这种方法要进行O(n^2)步运算才能算出乘积XY。

下面用分治法来设计更有效的大整数乘积算法。

将n位二进制数X和Y都分为两段，每段长n/2位（为简单起见，假设n是2的幂）。

则有：其中X1、Xo分别为X的高位和低位，Y1、Yo分别为Y 的高位和低位。

C2是它们的前半部分的积；Co是它们后半部分的积；C1是X、Y两部分的和的积减去C2与C0的积。

如果n/2也是偶数，我们可以利用相同的方法来计算C2、Co 的和C1。

因此我们就得到了一个计算n位数积的递归算法：在这种完美的形式下,当n变成1时,递归就停止了.或者当我们认为n已经够小了,小到可以直接对这样大小的数相乘时,递归就可以停止了.该算法会有多少次位乘呢?因为n位数的乘法需要对n/2位数做三次乘法运算,乘法次数M(n)的递推式将会是:当n>1时,M(n)=3M(n/2),M(1)=1当n=2^k时,我们可以用反向替换法对它求解:因为所以在最后一步中,我们利用了对数的一个特性:我们应当知道对于不是很大的数,该算法的运行时间很可能比经典算法长.有报告显示,从大于600位的整数开始,分治法的性能超越了笔算算法的性能.如果我们使用类似Java、C++和Smalltalk这样的面向对象语言，会发现这些语言专门为处理大整数提供了一些类。

python 大整数运算

python 大整数运算

python 大整数运算Python是一种强大的编程语言，具有广泛的应用。

它可以处理各种数据类型，包括整数、浮点数、字符串等等。

然而，在进行大量计算时，常规的整数类型可能会不够用。

这时，我们需要使用 Python 的大整数运算功能。

Python 中的大整数是通过内置的 int 类型实现的。

这种类型可以表示任意大小的整数，而不受固定大小的限制。

这使得 Python 成为进行大规模计算的理想工具。

在 Python 中，我们可以使用各种算术运算符对大整数进行运算，包括加、减、乘、除和取模。

此外，我们还可以使用内置的 math 模块进行一些高级的数学运算，例如幂运算、对数和三角函数等等。

大整数运算在 Python 中的实现方式与普通整数非常相似，只需使用 int 类型即可。

例如，我们可以执行以下操作：a = 123456789012345678901234567890b = 987654321098765432109876543210# 加法c = a + b# 减法d = a - b# 乘法e = a * b# 除法f = a // b# 取模g = a % b在进行大整数运算时，需要注意一些性能问题。

由于大整数的位数很大，因此它们的计算速度相对较慢。

为了提高性能，我们可以使用一些优化技巧，例如在必要时使用位运算代替乘法和除法。

总的来说，Python 的大整数运算功能非常强大，使得我们可以轻松地进行大规模计算和数值分析。

如果你需要处理大数字或进行高精度计算，Python 绝对是一个值得尝试的选择。

数字整型算法实验报告(3篇)

数字整型算法实验报告(3篇)

第1篇一、实验目的1. 理解数字整型算法的基本原理和方法。

2. 掌握常用的数字整型算法，如整数乘法、除法、取余、排序等。

3. 培养算法设计与分析能力，提高编程实践能力。

二、实验内容1. 整数乘法算法2. 整数除法算法3. 整数取余算法4. 快速排序算法5. 堆排序算法三、实验原理1. 整数乘法算法：利用位运算，将两个整数进行逐位相乘，然后求和得到最终结果。

2. 整数除法算法：利用长除法原理，将除数逐步减去被除数的倍数，直到余数小于除数，此时商即为最终结果。

3. 整数取余算法：与整数除法类似，只需取除法的余数即可。

4. 快速排序算法：采用分治策略，将待排序的序列分为两部分，一部分大于等于基准值，另一部分小于基准值，然后递归地对这两部分进行排序。

5. 堆排序算法：利用堆这种数据结构，通过调整堆的性质来实现排序。

四、实验步骤1. 整数乘法算法实现```cint multiply(int a, int b) {int result = 0;while (b != 0) {if (b & 1) {result += a;}a <<= 1;b >>= 1;}return result;}```2. 整数除法算法实现```cint divide(int a, int b) {if (a == 0) return 0;int sign = (a > 0) ^ (b > 0) ? -1 : 1;long long dividend = abs((long long)a), divisor = abs((long long)b); long long quotient = 0;while (dividend >= divisor) {dividend -= divisor;quotient++;}return sign (int)quotient;}```3. 整数取余算法实现```cint remainder(int a, int b) {return a % b;}```4. 快速排序算法实现```cvoid quickSort(int arr[], int low, int high) { if (low < high) {int pivot = partition(arr, low, high); quickSort(arr, low, pivot - 1);quickSort(arr, pivot + 1, high);}}int partition(int arr[], int low, int high) { int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);return i + 1;}```5. 堆排序算法实现```cvoid heapify(int arr[], int n, int i) {int largest = i;int left = 2 i + 1;int right = 2 i + 2;if (left < n && arr[left] > arr[largest]) { largest = left;}if (right < n && arr[right] > arr[largest]) { largest = right;}if (largest != i) {swap(&arr[i], &arr[largest]);heapify(arr, n, largest);}}void heapSort(int arr[], int n) {for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}for (int i = n - 1; i > 0; i--) {swap(&arr[0], &arr[i]);heapify(arr, i, 0);}}```五、实验结果与分析1. 整数乘法算法：通过位运算实现，效率较高，适用于大整数乘法运算。

长整数四则运算 实验报告

长整数四则运算 实验报告

“数据结构”课程设计报告长整数四则运算学生姓名：吴成杰徐文良指导教师：陈少军所在系：电子信息系所学专业：计算机科学与技术年级：2010计算机（1）班目录第1章需求分析 (1)1.1选题要求 (1)1.2选题背景和意义 (1)1.3选题目标 (2)1.4组员分配任务 (2)第2章概要分析 (2)2.1系统数据流图 (2)2.2原始数据 (3)2.3输出数据 (3)2.4对数据的处理 (3)2.5数据结构（存储方式） (4)2.6模块分析 (4)第3章详细设计 (4)第4章系统说明书 (11)第5章系统测试 (12)项目总结 (16)参考文献 (17)第1章需求分析1.1选题要求1、实现一个任意长度的整数进行四则运算的演示程序(1) 运算过程分步骤显示(2) 完成含有加法和减法的四则运算(3) 完成含有乘法和除法的四则运算(4) 包含括号的四则运算2、2个人对应完成2个人各自的任务1.2选题背景和意义（1）选题背景操作系统老师曾经布置我们做一道斐波拉契数列和求30的阶乘，但是计算的结果很大，还不知道该做样的存储，老师告诉我们需要用高精度数的知识能将计算的结果存储起来，数据结构老师也曾经布置过一个实验题，是计算长整数的加法的，但是长整数的位数是固定的。

于是我们试想计算任意长度的整数是不是能把所有的四则运算问题解决。

（2）选题意义我们选的这个课题能计算任意的四则运算，比如：1234567+7654321=8888888987654321-123456789=86419754123*456=5608884/42=2586-25*15+8*（9*2-144/12）=586-375+8*（18-12）=586-375+8*6=586-355+48=211+48=2591.3选题目标实现一个任意长度的整数进行四则运算的演示程序(1) 运算过程分步骤显示(2) 完成含有加法和减法的四则运算(3) 完成含有乘法和除法的四则运算(4) 包含括号的四则运算1.4组员分配任务我们组有两个成员，分别为吴成杰和徐文良，一个负责写主函数、函数整体的框架和写转换函数函数和对输入的字符进行处理，一个负责写出栈函数和写处理函数和拼接，程序出现错误，两个人一起在一起互相商量，修改。