MIRACL用户手册(译).doc

MIRACL用户手册译：叶道全 摘要Miracl库包含100余个例程，涉及多倍精度运算（multiprecision arithmetic）的各个方面。定义了两种新的数据类型表示大整数的big类型和表示有理数的flash（short for floating-slash）类型。大整数例程基于Knuth算法（在他的著作“The Art of Computer Programming”第四章中提出）。floating-slash（不固定斜杠？）算法基于圆整小数，最初由D.Matula和P.Kornerup提出。所有例程都针对速度和效率进行了全面的优化，同时也是标准的，可移植的C程序。另外，对于某些时间要求非常严格的算法，Miracl也针对流行的Intel 80x86系列处理器提供了汇编语言实现。Miracl还提供了C+接口。Miracl的所有源代码都包含于此。第二章 安装通过Microsft C/C+、Borlands Turbo C/C+、Watcom C以及DJGPP GNU编译器，MIRACL库已经成功安装到VAX11/780，各种UNIX工作站（Sun，SPARC、Next以及IBM RS/6000），IBM PC等机器上。还有ARM机器和Apple Macintosh。最近MIRACL也已经在Itanium和AMD 64位处理器上运行过了。MIRACL分发包中包含了库中所有模块的完整源代码以及各自的示例程序。大部分是用标准的ANSI C编写的，可用任意规范的ANSI C编译器进行编译。一些模块包含大量的内联汇编代码，用于优化在某些特定编译器/处理器组合上的性能。通过条件编译，它们可以透明地调用，并且不会影响到其它编译器。批处理文件xxdoit.xxx包含在多种编译器上生成库文件和示例程序的命令。请打开并检查与你的配置相关的文件。分发包包含了部分流行的编译器的预编译库文件：ready-to-run版本，它们可立即使用，为了节省空间，其中并没有包含所有的示例程序。要生成一个库，必须使用编译器，文本编译器，链接器，库管理实用程序（librarian utility）以及汇编器（assembler，可选），请阅读编译器文档以获取更多细节。mrmuldv.any文件包含了时间关键（time-critical）的例程muldiv，muldvd，muldvd2和muldvm的汇编语言版本，它们可能需要根据配置作一些改动。当编译器不支持一个可用于保存两个单字长整数乘积的双倍长度类型时，这些模块尤为必要。许多现代编译器支持这一点（通常称为long long），在这种情况下，一般使用这些模块的C版本mrmuldv.ccc（直接拷贝到mrmuldv.c）就足够了。更多细节请仔细阅读手册以及mrmuldv.any的注释。必须指定硬件/编译器规格文件mirdef.h。为了协助此过程，提供了此头文件的五个示例：mirdef.h16（16位处理器）、mirdef.h32（32位处理器）、mirdef.haf（工作在16位模式的32位处理器）以及mirdef.hpc（工作在16位环境中的伪32位）。请注意完整的32位版本是最快的，但只是在使用一个32位处理器及一个32位编译器的时候如此。在Unix环境中使用gcc和g+时尽量用mirdef.gcc。config.c用于协助配置过程。在目标处理器上编译和运行它，它会自动生成mirdef.h文件，并给出常规的配置建议。它还生成一个miracl.lst文件，其中包含建立相关库时应包含的MIRACL模块列表。强烈建议尝试此程序。编译它时请务必关掉所有编译器优化选项。mirdef.h文件包含一些可选定义：当无法满足muldvd，muldvd2和muldvm在mrmuldv.c中的版本时，定义MR NOFULLWIDTH；若要在程序中使用flash变量，定义MR_FLASH；MR_LITTLE_ENDIAN 与 MR_BIG_ENDIAN，必须定义其中之一，config.c会自动决定哪一个适用于你的处理器。省略MR_FLASH时，big变量可以更大，并且生成的库也更小。定义MR_STRIPPED_DOWN将忽略错误消息，可以进一步节约生成的代码空间，请小心使用！如果不想要任何汇编器，请定义MR_NOASM。这将以内联的方式生成四个时间关键例程的标准C代码。这稍快一些节省了函数调用的开销这也是最优编译器得考虑的一点（原文：and also gives an optimising compiler something to chew on）。使用Microsoft Visual C+时，msvisual.txt中提供了一些有用的建议。Linux操作系统对应的是linux.txt，Borland编译器用户则可以查看borland.txt。预生成库或.txt文件中提供的建议不可用的时候，通过下列步骤多半能成功地生成MIRACL库：1. 在目标处理器上编译并运行config.c。2. 将生成的mirdef.tst重命名为mirdef.h。3. 根据config程序的建议，从mrmuldv.any中提取一个合适的mrmuldv.c或将标准C版本的mrmuldv.ccc拷贝到mrmuldv.c）。如果是纯汇编，则可以命名为mrmuldv.s或mrmuldv.asm。4. 如果选择了快速KCM或Comba模乘算法，则编译并运行mex.c实用程序（在任意工作站上）。使用它自动生成mrcomba.c或mrkcm.c，其中需要一个处理器/编译器规格文件xxx.mcs，同时编译器必须支持内联汇编。5. 确保编译器能访问所有MIRACL头文件。通常标志-I或/I允许访问当前目录中的所有头文件。6. 编译miracl.lst文件中列出的MIRACL模块并创建库文件，通常是miracl.a或miracl.lib。这可以通过将miracl.lst编译为一个合适的批处理文件或make文件来实现。在UNIX上可以像这样简单：gcc -I. -c -O2 mr*.car rc miracl.a mr*.o7. 若要使用MIRACL的C+包装，编译所需的模块，例如zzn.cpp和（或）big.cpp等。8. 将MIRACL库和所需的任意C+模块编译并链接到你的应用程序（原文：Compile and link your application code to any C+ modules it requires and to the MIRACL library）。记住MIRACL是可移植软件，它可以移植到任意支持某个ANSI C编译器的计算机上。请注意MIRACL是一个C库，而不是C+。它总是应该作为一个C库来生成，否则你可能得到编译器错误。为在C程序中包含MIRACL例程，请在程序的开始处include头文件miracl.h（在stdio.h之后）。虽然大部分情况下使用C+包装更为可取，你也还是可以通过以下方式在C+程序中直接调用MIRACL例程：extern C#include miracl.h2.1 优化在MIRACL的上下文中，这意味着更快的速度。配置MIRACL时需要作的一个关键决策就是确定要使用的底层类型（经常是int类型）。如config所要求的，通常应定义尽可能大的底层类型。如果你有一个64位处理器，你就应该可以指定一个64位的底层类型。在某些场合，使用一个双精度浮点型的底层类型可能更快。显然纯C的MIRACL产品是最慢的（当然它依然相当地快），它也是最容易入门的。这需要一种宽度是底层类型的两倍的整数类型。在这样的背景下，请注意目前大多数的编译都支持一种long long（有时称为_int64）类型，其尺寸是int的两倍。如果你的处理器是低端的RISC类型并且不支持整数乘除指令，或需要使用非常大的模数，则Karatsuba-Montgomery-Comba快速模乘技术可以使乘幂加密系统（exponentiation cryptosystems）更快。config程序将同样针对此点为你提供引导。有时用汇编语言实现mrmuldv模块会更快。这不需要双倍尺寸的数据类型。如果够幸运你的编译器也支持自动调用内联汇编，则将更变更快。可以在miracl.h中查看哪些编译器支持这种方法。为获得终极速度，可以使用mrkcm.c，mrcomba.c中实现的非常（extreme，极品）技术，kcmcomba.txt中有关于如何用mex实用程序自动生成这些文件的操作指南。2.2 从版本3升级版本4引入了MIRACL实例指针（MIRACL Instance Pointer，mip）。之前的版本使用一些全局和静态变量存储内部状态信息。这主要有两个问题。首先是为了避免冲突，这些全局变量取了一些令人费解的名字；其次是它使得开发多线程应用程序变得更困难。所以从版本4开始，这些变量声明到一个miracl结构中，作为实例变量来引用，必须通过指向miracl结构的指针来访问它们。现在全局指针是MIRACL维护的唯一全局/静态变量。它的值由负责初始化MIRACL库的mirsys例程返回。C+程序员应注意miracl与Miracl命名上的区别，mip可以通过对Miracl实例取址来获得：Miracl precision = 50;.mip = &precision;.etc2.3 多线程编程从版本4.4开始，通过若干特性，MIRACL对多线程编程提供了完整的支持。要解决的问题是MIRACL需要通过mip指针来访问许多实例相关的信息。理想的状态是没有全局变量，但MIRACL有一个这样的指针。不幸的是每个使用MIRACL的线程都需要一个属于自己的mip，用来指向它自己的独立状态信息。这是多线程的一个众所周知的焦点（原文：This is a well-known issue that arises with threads）。第一个解决方案是修改MIRACL，将mip作为所有MIRACL函数的参数来传递，用来替代全局变量。通过在mirdef.h中定义MR_GENERIC_MT，MIRACL将自动更改以支持此方式。现在（几乎所有）MIRACL例程都改为第一个参数是mip。一些简单的函数例外，它们不需要mip参数参考手册中用星号来标识它们。brent_mt.c是一个使用以这种方式建立的MIRACL库工作的示例程序。请注意这种解决方案不适用于使用MIRACL的C+包装的应用程序，只适用于直接访问MIRACL例程的C程序。另一种可选方案是使用Key，这是一种线程特定的“全局”变量。Key不是C/C+标准的一部分，而是操作系统的特殊扩展，通过特殊的函数调用来实现。MIRACL对Microsoft Windows和UNIX操作系统提供了支持。对于前者，Key称为线程本地存储（Thread-Local Storage）；对于后者，MIRACL对POSIX标准接口提供了多线程支持。一个对Windows和Unix都非常有用的参考是Walmsley。对多线程的这种支持实现在模块mrcore.c中（位于文件的起始处的初始化例程mirsys中）。对于Windows，在mirdef.h中定义MR_WINDOWS_MT。对Unix则定义MR_UNIX_MT。在两种场合都有一定的程序涵义（源文：In either case there are some programming implications.）。在第一种场合中，用于保存mip的Key必须由程序的主线程初始化和销毁（最后）。这些功能通过调用相应的特殊例程mr_init_threading和mr_end_threading来完成。在C+程序中，这些函数可能与全局变量的构造函数和析构函数相关联Walmsley这将确保它们会在主线程创建新的线程分支前的一个适合的时候被调用。它们必须在线程显式（或隐式）地调用missys（通过创建线程特定的Miracl实例）之前被调用。强烈建议程序在开发时不要实现对多线程的支持。只有程序经过完整的测试和调用，它才应转换到一个线程中（原文：should it be converted into a thread）。线程编程可能要求其它的操作系统的特殊机制在链接特殊的库或访问特殊的堆函数方面。这里值得指出的是MIRACL堆访问都是通过mralloc.c模块完成的。threadwn.cpp程序是一个Windows C+多线程示例。阅读其中的注释它可以编译和从Windows命令提示符运行。类似地threaduc.cpp是一个Unix的多线程示例。2.4 受限环境在版本5的中，有一个对在非常小和受限的环境中的MIRACL实现的新支持。使用config实用程序，它现在支持各种时空交换（time/space trade-offs），最主要的革新是在一个不支持堆的环境中生成和使用MIRACL。通常big变量的空间从堆中分配，但通过在配置头文件中指定MR_STATIC，可以生成一个总是尝试从静态内存或栈，而不是堆中分配内存的版本。这带来的主要负面影响是big变量的最大尺寸必须在编译时确定（生成库的时候）。如往常一样，在这个过程中最好让config实用程序引导你创建一个合适的配置头文件mirdef.h。对于C程序员，使用下列方式从栈中为big变量分配内存：big x, y, z;char memMR_BIG_RESERVE(3);memset(mem, 0, MR_BIG_RESERVE(3);为三个big变量分配的空间都在栈上并且被清零，然后每个变量应如下初始化：x = mirvar_mem(mem, 0);y = mirvar_mem(mem, 1);z = mirvar_mem(mem, 2);从单个内存块中为多个big变量分配所有空间是有意义的，那样可以更快的初始化，而且可以对变量对齐进行完整的控制编译器有时会出错。请注意big初始化函数mirvar在这种模式中不再有效，分配操作应像上面描述的那样实现。最后，可以选择性地在函数末尾调用memset来在离开前清空内存块出于保密原因，这可能很重要。请参考示例程序brent.c。这种机制在实现一个使用椭圆曲线的非常小的程序时可能非常有用。椭圆曲线要求的big数字要比其它加密技术的小得多。从栈中为椭圆曲线的点分配内存：epoint *x, *y, *z;char memMR_ECP_RESERVE(3);memset(mem, 0, MR_ECP_RESERVE(3);初始化这些点：x = epoint_init_mem(mem, 0);y = epoint_init_mem(mem, 1);z = epoint_init_mem(mem, 2);同样，在离开函数前清空相关内存是明智的。此机制对C+编程同样支持得很好，它与第7章描述的栈分配方法联合工作。pk-demo.cpp是一个使用示例。在一些极端场合中，可能要求从栈中分配所有内存。这允许使用和重用最多的内存，并且避免宝贵的RAM出现碎片。对于C程序，这可以通过在mirdef.h中定义MR_GENERIC_MT来实现。这种场合中的典型mirdef.h头文件可能是这个样子的：/* MIRACL compiler/hardware definitions - mirdef.h* Copyright (c) 1988-2005 Shamus Software Ltd.*/#define MR_LITTLE_ENDIAN#define MIRACL 32#define mr_utype int#define MR_IBITS 32#define MR_LBITS 32#define mr_unsign32 unsigned int#define mr_dltype _int64#define mr_unsign64 unsigned _int64#define MR_STATIC 7#define MR_ALWAYS_BINARY#define MR_NOASM#define MAXBASE (mr_small)1(MIRACL-1)#define MR_BITSINCHAR 8#define MR_SHORT_OF_MEMORY#define MR_GENERIC_MT#define MR_STRIPPED_DOWN关于使用这种类型的头文件的示例程序，请查看ecsgen_s.c，ecsign_s.c，ecsver_s.c，ecsgen2s.c，ecsign2s.c和ecsver2s.c。这些程序使用Microsoft C+在Pentium上实现了非常小而快速的ECDSA密码生成，数字签名以及校验算法。ecdh.c是另一个很棒的示例，它使用导航预行计算（precomputation）来加速一个EC Diffie-Hellman实现。注意：不使用堆有一些小问题：结构不能再是可变大小的，因此在这种模式中MIRACL的许多特性都不再可用。例如中国剩余定理（Chinese remainder theorem）程序要求的导航预行计算（precomputation）就无法支持。但在一个受限环境中，有理由假定诸如导航预行计算（precomputation）将脱机实现，以使将程序固化到ROM中成为可能。MIRACL模块经过了周密的设计以使对于给定的任务，应用程序都只需要从库中引入最少的模块。这可以帮助应用程序保持最小的尺寸。但是如果程序的尺寸是一个大话题（big issue），则可以手工从模块中删除不需要的函数来达到额外的节约。2.5 平台特定的信息2.5.5 Microsoft Visual C+在Microsoft C+6.0上创建MIRACL应用程序的步骤如下：1. 创建一个Win32 Console Application的空工程。2. 选择菜单“Project”“Add to Project”“File”。3. 选择“Library files(.lib)”文件类型，查找预编译的MIRACL库文件ms32.lib，将它添加到工程。4. 添加一个工程的主文件（例如limlee.cpp）。5. 如果是C+主工程文件，则再添加其它所需的文件，如big.cpp、zzn.cpp等。主文件的头部注释中列出了所需的文件。6. 选择菜单“Project”“Setting”。选中C/C+ Tab页，选择“Preprocesser”目录，在“Additional Include Directoryies”中指定MIRACL头文件路径。7. 确保应用程序运行目录中的所有程序所需文件均可用，如*.key，*.dss或*.ecs等文件。8. 生成并运行程序。在Microsoft C+6.0上创建MIRACL库的步骤：1. 编译并运行config.c实用程序，将生成的mirdef.tst重命名为mirdef.h。注意Microsoft C拥有一个64位整数类型_int64。2. 新一个“Win32 Static Library”类型的工程。3. 添加适当的mr*.c文件，它们在miracl.lst中列出。4. 选择菜单“Project”“Setting”。选中C/C+ Tab页，选择“Preprocesser”目录，在“Additional Include Directoryies”中指定MIRACL头文件路径。5. 编译工程生成MIRACL库。在Microsoft C+.NET上创建MIRACL应用程序的步骤：1. 创建一个Win32 Console Application的空工程。2. 去掉工程中的空主文件，用MIRACL提供的文件（如limlee.cpp）将其替换。请注意现在主函数称为_tmain。3. 选择菜单“Project”“Add to Project”“File”。选择“All files”文件类型，查找预编译的MIRACL库文件ms32.lib，将它添加到工程。4. 如果是C+主工程文件，则则再添加其它所需的文件，如big.cpp、zzn.cpp等。主文件的头部注释中列出了所需的文件。5. 选择菜单“Project”“Properties”。打开C+标签页，到“Precompiled Headers”，选择“Not using precompiled headers”。再打开“General”标签页，指定MIRACL头文件的路径。6. 生成并运行程序。在Microsoft C+.NET上创建MIRACL库的步骤：创建一个“Win32 Project”类型的Visual C+工程。选择“Application Settings“，选择”Static Library“。添加相应的mr*.c文件。选择“Project”“Properties”。打开C+标签页，到“Precompiled Headers”，选择“Not using precompiled headers”。再打开“General”标签页，指定MIRACL头文件的路径。生成工程。若要在基于MFC Win32工程中使用MIRACL，这里有一些相关建议：1. 使用config.c实例程序生成mirdef.h，并在其中定义MR_NO_STANDARD_IO，再生成MIRACL库。2. 如果使用C+ MIRACL类，别忘了在工程设置中将big.cpp等MIRACL实现文件设置为“not using pre-compiled headers”。3. 别忘了MIRACL是一个C库，若要直接调用MIRACL例程，必须：extern C#include miracl.h使用C+时，通过C+包装来访问MIRACL可能更合适。4. 要显示一个big值，先将它转换为string。见big.h头部的注释。对于Visual C+8.0，预编译的ms32.lib无法工作，必须首先生成一个新的库文件。第三章 接口下面是一个一个计算并输出1000!（1000的阶乘）的程序：/* Program to calculate factorials.*/#include #include miracl.h /* include MIRACL system */void main()/* calculate factorial of number */big nf; /* declare big variable nf */int n;miracl *mip = mirsys(5000, 10);/* base 10, 5000 digits per big */nf = mirvar(1); /* initialise big variable nf=1 */printf(factorial programn);printf(input number n= n);scanf(%d, &n);getchar();while (n 1)premult(nf, n-, nf); /* nf=n!=n*(n-1)*.2*1 */printf(n!= n);otnum(nf, stdout); /* output result */若要在程序中使用MIRACL，则必须先包含声明：#include “miracl.h”这告诉编译在继续编译前将C头文件miracl.h包含到当前主程序中来。此文件包含用户可以使用的所有MIRACL例程。mirach.h中的子头文件mirdef.h包含硬件/编译器特定的细节。在主程序中，必须调用mirsys来初始化MIRACL系统，通过mirsys指定基数和big、flash变量的最大尺寸，同时它还将初始化随机数系统，并创建一些工作区变量（big类型）供内部使用。返回的值是Miracl实例指针（Miracl Instance Pointer，mip）。此指针可用于访问与当前MIRACL实例相关的各种内部参数。例如设置ERCON标记可以写为：mip-ERCON = TRUE; 对mirsys的调用还会初始化MIRACL包集成的错误跟踪系统。Whenever an error is detected the sequence of routine calls down to the routine which generated the error is reported, as well as the error itself。一条典型的错误消息类似：MIRACL error from routine powltrcalled from isprimecalled from your programRaising integer to a negative power这些错误报告能够协助我们在开发过程中更方便地调试这些例程。一个相关的实例变量是TRACER，初始为OFF，若设置为ON，将导致对MIRACL例程中的程序流程的跟踪输出到屏幕上。实例标记ERNUM初始为0，用于记录最近发生的MIRACL发生的错误的编号。如果标记ERCON设置为FALSE（默认），错误消息将直接输出到stdout并通过系统调用exit(0)终止进程。如果你的系统不支持exit例程，则编程人员必须提供一个替代品。若ERCOM设置为TRUE，则不会发出错误消息，取而代之由编程人员来负责检查和处理错误。在这种情况下，程序将继续执行。编程人员可以选择处理错误并将ERNUM重围为0。但错误经常是致命的，如果ERNUM非零，接下来的所有MIRACL例程调用都将“失败（fall-through）”并立即退出。可能的错误列表请参见miracl.h。用户程序中的每个big或flash变量都通过调用mirvar初始化，它也允许对变量赋一个整数作为初值。miracl.h中声明的所有的算术和数论例程均在在这些变量上使用。这些例程在参数使用上（几乎总是）具有完全的灵活性。例如调用multiply(x,y,z)将把x和y的乘积保存到z中，调用multiply(x,y,x)、multiply(y,y,x)或multiply(x,x,x)都是同样有效的。请注意按照约定第一个参数通常是例程的输入。所提供的例程不仅可以用于对big和flash进行算术运算，也可以在内置的整形和双精度浮点型变量上进行运算。类型转换例程也有提供，细节请参考参考手册中的有关文档。输入输入到文件或I/O设备由例程innum，otnum，cinnum，cotnum处理。前两个使用mirsys中指定的固定基数。后两者与可由用户动态更改的实例变量IOBASE联合使用。一个简单的规则是若程序是CPU边界的（原文：A simple rule is that if the program is CPU bound），或涉及基数的变动，则初始应将基数设置为MAXBASE（或0当完全宽度的基数可行时），并使用cinnum和cotnum。另一方面，如果程序是I/O边界的（原文：If the program is I/O bound），或需要访问数字中的特定位（通过getdig，putdig和numdig），则使用innum和otnum。例程instr，otstr，cinstr和cotstr以类似的方式支持从字符串输入或输出到字符串。输入例程可用于为big或flash设置一大的常量值。通过输出到字符串，可在实际输出文件或I/O设备之前完成格式化。最大可表示基数为256的值，基数小于等于60的数使用0-9，A-Z以及a-z中的符号。64进制数字强制使用base64编码。如有必要，base64数字输出时将在结尾后以 =符号填充（不会有其它格式）。输入时，空白字符会被跳过，并忽略填充部分。不要对flash数字使用base64。不要使用base64输出负数（会忽略符号）。如果基数大于64且不等于64，则将使用ASCII码0-255。基数256在将一行文件当作大整数来解析时有用，如在第8章描述的公钥加密程序中。例程big_to_bytes和bytes_to_big允许直接在内部的big格式和二进制之间进行转换。字符串通常是以零结尾的。但在使用基数256时会产生一个问题。在这种情况下0-255中的任何一个数字都可出现在一个数中，所以零不应当作字符串的终止符。输入时应采用别的方式来指定字符串中数字的数量。通过在调用innum或instr之前设置实例变量INPLEN（例如置为25），输入将在送入25个字符后终止。INPLEN初始为0，并且每次相关操作都会在返回之前将它重置为0。例如，先初始化一个使用400字节长的big变量的MIRACL实例：miracl *mip = mirsys(400,256);使用此基数，内部计算将非常高效。将一个ASCII字符串作为一个256进制数输入，它以0结尾，因为不需要INPLEN：innum(x, stdin);现在再输入一个1024位的随机值：mip-INPLEN=128;innum(y, stdin);以16进制查看输出：mip-IOBASE = 16;cotnum(w, stdout);以64进制查看输出：mip-IOBASE = 64;cotnum(w, stdout);有理数可以使用小数点形式（例如0.3333）或分数形式（例如1/3）来输入。也可以通过设备实例变量RPOINT为ON或OFF来选择以哪一个形式输出。第四章 内部表示大部分语言的编译器通常提供一到两种浮点类型用于表达所有实数，与一到多种整数类型一起用来描述所有数字。这些内置数据类型与底层的计算机架构密切相关，它们通常合理地设计为对出现频率更高的较小数运算得更快，而不是与那些出现频率领很低的大数字一样慢。浮点类型允许使用相对来说小范围的二进制数字（例如32位）来以足够的精度在一个大的动态范围内表示实数。整数类型直接使用相同的二进制值来表示一个限值内的所有整数，或用二进制补码来表示负数。传统的计算机运算方式存在几个缺陷：1. 浮点和整数类型是不相容的。整数集虽然是无穷的，但依然是有理数的一个子集，而有理数则是实数的一个子集。因此每个整数都有一个等价的浮点表示。不幸的是这两种表示通常是不一样的。例如整数类型会用等价的二进制来表示一个小的正整数，而浮点类型则会用分开的尾数和幂来表示。这意味着需要用转换程序来从一种形式转换为另一种形式。2. 大部分有理数都无法被精确的表示（例如1/3,译注：貌似1/3是无理数啊）。事实上浮点系统只能精确地表示那些分母是底层表示的基数的因子的整数倍的有理数。例如我们熟悉的十进制系统只能精确地表示分母是2或5的倍数的有理数；1/20是0.05，而1/21是0.0476190476190.3. 浮点的圆整是依赖于基数的，而且也是不明显的错误的一个根源。4. 一个事实是整数和浮点数据类型的尺寸由计算机架构决定，这使语言设计者难以保持它们的语言能够真正可移植。5. 数字只能以固定的依赖机器的精度来表示。在许多应用程序中这是严重的缺陷，例如在新兴的正在成长的公钥加密算法领域。6. 基数依赖的现象是不易考虑的。例如很难从传统的整形中访问十进制数的某一位。这里描述了一组用于直接操作多倍精度有理数的C例程，多倍精度整数是其一个兼容子集。同时也可以进行近似的实数运算。两个新的数据类型是big和flash。前者用于存储多倍精度整数，后者以floating-slash(不固定斜杠)的形式用分子和分母来存储小数。两者的格式都是一个固定长度的数字数组，外加一个包含符号和长度信息的独立32位整数。需要用一种内置类型来储存数字，这个类型定义为mr_small，它可以是int、long甚至double。struct bigtypemr_unsign32 L;mr_small *d;typedef struct bigtype *big;typedef struct bigtype *flash;定义变量：big x, y10, z1010;要注意一个big变量仅仅是一个指针，big(或flash)变量实体所需要的内存是从堆(也可以从栈)中分配的。因此使用前必须进行初始化。分母长度为0意味着实际上分母是1，分子长度为0意味着实际上分母是1。零本身定义为一个首元素是0的数字。flash中的斜杠并不在一个固定位置，它依赖于分子和分母的相对尺寸。操作flash时，会将它拆分为分别等于分子和分母的两个big值。big的操作由提取并操作其中的每个mr_small元素组合而成。为避免可能的溢出，每个元素中的值通常限定在一个比完整的变量所能表示的最大值小的范围，例如在16位机上是0-32767（2的15次方 - 1），但基于2的16次方进行编程也是可以的，C语言不会报告整数溢出错误。系统初始化时用户必须指定一个固定的尺寸（以字或字节为单位）和基数，这两个值将应用于所有big和flash变量。基数的上限与机器字长有关，可以使用不超过上限的任意值作为基数。当使用一个偏小的基数b时，系统实际上将使用b*n作为基数（这能够更高的效率），n是一个满足使b*n能被单个机器字表示的最大整数。当使用一个完整宽度的基数时，程序通常运行得最快。若使用这个基数，请在调用mirsys时指定基数为0。需要注意的是对某些时间关键的例程，这种模式在部分常用的编译器/处理器组合中是由大量的汇编代码支持的。例如，对于使用Borland/Turbo C和80x86处理器，可以查看mrarth1.c中的源程序。将符号和分子、分母的大小信息编码到单个字中是可行的，C语言包含位操作的完整结构。第五章 实现big类型的算术运算的实现并没有太大的创造性，使用的算法是KnuthKnuth81。但是做了一些速度优化的工作。在耗时的乘除法内部，典型的实现是对操作数的每一位相乘，加上上一次操作的“进位”，将结果分为一个数字和对下一个操作的“进位”。以10进制乘法为为例，考虑8723536221 * 9：为了正确地处理数字5所在的列，需要计算5 * 9 = 45，加上前一列的进位3，得到48，将其中的8作为结果，4作为对下一列的进位。基本的原始操作是计算(a * b + c) / m的商和余数。在上例中：a = 5, b = 9, c = 3, m = 10这个操作具有惊人的广泛用途，并且它处算法的最里层循环中，因此它的高效实现是非常必要的。对这个MAD(Multiply, Add and Divide)操作，高级语言在实现时通常具有三个难点：1. 慢。2. 商和余数不能同时作为一次除法的结果，因此计算过程执行两次，一次用来获得商，一次用来获得余数。3. 即使操作结果是两个单值，但中间结果ab + c可能是双倍长度的。很庆幸地C语言拥有long整形可以用来临时保存这个乘积。因为这些原因，最好用汇编语言来实现这些关键操作。即使C语言的long类型不是双倍长度（在32位机器上，大部分C编译器的int和long都是32位），在机器语言层也通常能处理一个临时的双倍长度的结果。有关详细资料可以查看mrmuldv.any文件。MIRACL对big和flash类型使用固定长度的数组，这是为了避免可变长度方式下需要进行内存分配和碎片收集的困难度和时间消耗。这也意味着在对big值进行计算时，所有的结果和中间数者必须小于等于在mirsys中指定的固定尺寸。在实践中，稳态计算中涉及的数字的尺寸大多相近。除非两个数相乘导致产生一个双倍长度的中间结果，但这也通常会接下来立即在一次除法操作中缩小。这种情况的一个典型的例子是Pollard-Brentl因式分解。请注意上面提到的问题的另一个微观表现。只是为了拷贝这些偶然出现的中间值，而为每个变量分配所需大小的两倍的存储是很可惜的。因此，MIRACL库提供了一个特殊的Multiply,Add,Divide例程(名为mad)。它已经被证明在内存受限的机器上实现大型程序（像Pomerance-Silverman-Montgomery因式分解）时非常有用。除了基本的算法运算，以下例程也有提供：1. 生成和判断质数，使用概率质数判断方法Knuth81。2. 生成随机big和flash，基于subtract-with-borrow生成器Marsaglia。但是请注意内部实现的的基本随机数生成器并不具有秘密安全性（cryptographicly secure，保密性？）。在真实的加密应用程序中，它是不够可靠的。mrstrong.c中提供了一个强保密生成器。3. 计算幂和根。4. 实现了普通的和扩展的欧几里得最大公约数(Euclidean GCD)算法。5. 实现了中国剩余定理Knuth81，以及计算雅可比符号(Jacobi Symbol)Reisel。6. 超大数的乘法，使用快速傅里叶变换(Fast Fourier Transform)Pollard71。在进行大规模模运算(modular arithmetic)时，一个时间上的关键操作是模乘，就是对两个数进行乘法之后再除以一个固定的n，取其余数。一个明显的解决方案是用之前提到的mad例程来完成，但Montgomery提出了一种替代方案，这要求要求先将两个数转换为特殊的n-residue样式，在n-residue样式下可以通过一个完全没有用到除法的特殊例程更快的完成模乘操作，然后再将结果转换为普通格式。请注意n-residue的模加与模减操作与普通的类似，使用相同的例程。 鉴于要求对变量进行n-residue格式转换，Montgomery算法只应考虑用于对同一个模数进行大量模运算的计算场合。这在C+环境中使用更为方便，因为屏蔽了这些细节。MIRACL库中的许多要进行大量模运算的例程在内部使用了蒙哥马利算法，如高度优化的模幂(modular exponentiation)函数powmod，以及实现GF(P)椭圆曲线运算的函数，可以在参考手册中找到相关信息。为了达到最快的模运算，同时还必须使用汇编，针对特定的模数或特定尺寸的模数进行优化等方法。有相当数量的技术可供使用：首先是Comba和KCM方法，其实现分别在mrcomba.c和mrkcm.c文件中。这些文件通过向模板文件mrcomba.tpl和mrkcm.tpl中插入.mcs文件中的宏来创建。这是通过宏展开程序mex自动完成的。在目标机器上编译并运行config.c以自动创建合适的mirdef.h和获取继续操作的建议。同时也请阅读kcmcomba.txt。为使嵌入的程序获得尽可能快的性能，当没有与您的编译器/处理器对应的x.mcs文件时，建议你自己创建一个。另外有两种在一定程序上属于实验性的技术，分别实现在mr87v.c和mr87f.c文件中，仅适合于80x86系列处理器和Borland C+编译器。在满足条件时，相应的代码将被自动调用。请务必注意上述四种技术要求编译器支持内联汇编，而且后两者仅用Borland C+ V4.5编译器在80x86系列处理器上进行过测试。第一种方法的思路是对乘法和归约过程(multiplication and reduction process)中隐含的循环进行完全的分解和重组，由Comba首先提出，Scott96对其进行了修改，见mrcomba.tpl。这种方法必须使用固定宽度的模数并在编译时确定(在mirdef.h中定义MR_COMBA宏为模数尺寸，以字为单位)。对中小尺寸的模数这种方法工作得很好，尤其是在GF(p)椭圆曲线加密算法中。若要获得比这还要快的速度，归约过程可对某些具有特别简单的样式(particularly simple form)的模数进行优化。这可以通过手工向mrcomba.tpl插入相应的代码来完成。针对模数p = 2 192 - 2 64 - 1的示例代码在例程comba_redc中给出，要运行此特殊的代码，必须在mirdef.h中定义MR_SPECIAL。这项技术可以与Karatsuba的快速乘法Knuth81联合用于提高对大模数的模乘运算速度。可在mirdef.h中定义MR_KCM以调用此Karatsuba-Comba-Montgomery (KCM)方法。以机器字为单位的模数尺寸限定为必须等于MR_KCM*2n，n可为(合理范围内的)任意正整数，这是使用Karatsuba算法的一个后果。例如若在32位机器上定义MR_KCM为8，则可用的模数尺寸为512，1024，2048位等。另一个选择是利用浮点协处理器(floating point co-processor)，如果存在的话。它的乘法指令通常要比整数单元的要快Rubin。Intel Pentium处理器内嵌的协处理器可以用三个周期完成一次乘法，而一次整数乘法需要10个周期。不过对Pentium Pro,II或III情况可能不同。同时协处理器有8个额外的寄存器，可直接操作64位数字。这个特性给程序员提供了一些额外的可以加以利用的灵活性。一些实验性的代码在mr87f.c和mr87v.c中提供，可通过在mirdef.h中定义MR_PENTIUM加以利用。使用config.c来生成mirdef.h这时底层类型必须选择double。模块mr87v.c实现了简洁的循环代码(compact looping code)，可工作于小于某个最大值的任意模数。模块mr87f.c展开了这些循环以获得更快的速度，但也因此更为宠大并且要求固定尺寸的模数。请注意这些运行方式与完全宽度基数(full-width base)是不兼容的，它们通常在基数为228或229(config.c会为你计算出这个值)的数字上工作得最好。同时也请注意即使这些方法可以加速Pentium上的模幂运算，但它也可能在大部分的其它80x86处理器上更慢，所以请小心使用。在一次测试