MIRACL用户手册(译)(5)

2019-08-30 19:41

图5说明了在Pentium Pro 200MHz处理器上使用Borland C 32位编译器编译时,各个方法所需的相对时间。基线对应mrarth2.c和mrmonty.c中用汇编直接实现的方法。Comba和KCM的汇编实现在文件ms86.mcs中。x轴表示模数尺寸,y轴表示时间。请注意在计算(ab mod n)时:

1. 假定a、b、n是随机生成的,拥有相同的位长度,并且没有特殊的格式。 2. 假定Comb(见[HAC]和brick.c)等优化技术均未应用。

图中8192位的模数相关的时间是准确的。与更小的模数相关的时间是以一个递增的放大比例显示的(比例以8为单位递增)。因此对4096位模数,应将其时间除以8,对2048位模数,应将其时间除以64,等等。对一些很大的模数进行完全的展开是不切实际的,因此图中并未提供相关算法的相关时间。

请注意Comba是针对512位及以下尺寸的模数进行过优化的。这意味着它是快速GF(p)椭圆曲线算法、1024位RSA加密算法(要求两个512位乘幂和一个中国剩余定理的程序)的实现的最佳选择。但这个结论是与处理器相关的,不适用于全部。而且Comba会产生大量的代码,这在某些程序中是需要慎重考虑的。在一些环境中(例如高速缓存非常小),使用非展开的汇编实现可能更明智。

从5.20版本开始,MIRACL直接用C提供了一个新类型,称为zzn2,它实际上由两个n-residue格式的big组成。

typedef struct {

big a; big b; } zzn2;

其中a和b分别表示实部和虚部,一个zzn2的值为a+ib,i为平方非剩余(quadratic non-residue)的虚平方根(imaginary square root)。一个zzn2变量是一个与某个素数模数相关的二次展开域的元素的表示(原文:A zzn2 variable is a representation of an element of a quadratic extension field with respect to a prime modulus p)。例如若 p ≡ 3 (mod 4),则i可取-1的平方根,and the analogy to complex numbers with their real and imaginary parts becomes clear。这在实现密码配对时尤其有用。作为一个使用范例,请参考cardona.cpp中一个解三次方程的例子。实例变量qnr中保存了一个默认的平方非剩余值,目前仅支持-1和-2。

为协助程序员产生针对非标准环境(例如嵌入式控制器)中的处理器的代码,动态内存分配的代码总是从mralloc.c中调用。默认情况下这将调用C运行库函数calloc和free。但很容易更改为其它内存分配机制。出于同样的原因,所有屏幕/键盘的输入输出都通过标准库函数fputc和fgetc执行,通过截取对这些函数的调用,I/O可以重定向到非标准设备。

第六章 Floating-Slash数字

一种直观的表示有理数的方式是通过简化的分数,用消去公因数的分子和分母来表示。这样的数字可以用直观的方式进行加减乘除,其结果也可以通过消去分子、分母的最大公约数(Greatest Common Divisor)来简化。MIRACL包含了一个高效的GCD子例程,该例程使用古典欧几里得(Euclidean)算法的一个针对多倍精度数的Lehmers变种。

另一种可选方案是使用有限连分数(finite continued fraction,[ Knuth81])来表示有理数。任何有理数p/q都可以表示为:

上式可以简洁的表示为:p/q = [a0/a1/a2/.../an],ai为正整数,通常很小。例如277/642 = [0/2/3/6/1/3/3]。

请注意连分数中的ai,它们是在对q和p进行Euclidean GCD计算时的次生产物”商“,因此很容易找出。 当我们用固定长度来表示有理数时,一个问题是一些操作的结果可能超过了固定的长度。这就需要一些方案来作截断或圆整。虽然并没有直观的截断大分数的方式,但截断一个连分数表达式却很简单。作为其结果得到的稍小的分数称为原分数的一个最佳有理近似或渐近分数(a best rational approximation, or a convergent)。

考虑截断277/642 = [0/2/3/6/1/3/3],简单地去掉CF表达式中最后一个元素,得到[0/2/3/6/1/3/3] = 85/197,这与277/642仅相差0.0018%。继续截断至22/51,19/44,3/7,1/2直至0/1,随着分数越来越小,误差逐渐增大。

上面提到的圆整称为“中间数圆整(Mediant rounding)“。若p/q和r/s是两个相邻的可表达数,则它们的中间数是不可表达数p+r/q+s。处于中间数与p/q之间的数圆整为p/q,处于中间数与r/s之间的数圆整为r/s,中间数本身圆整为p/q或r/s中较简单者。

从理论上说这是一种非常好的圆整方式,比浮点运算中相当随意且依赖基数的方式要好得多。此处(MIRACL)使用的即是这种方式。Matula和Kornerup描述了有关floating-slash运算的完整的理论基础[Matula85]。应注意到MIRACL的flash实际上是Matula和Kornerup分析的固定斜杠系统和非固定斜杠系统(fixed- and floating-slash systems)的混合产物,它的斜杠只能以字为单位浮动,而不是以位为单位。但由于精度的提升,flash的规格参数与floating-slash比较接近。

MIRACL例程mround实现了中间数圆整。若某个算术运算结果为p/q,则先对p和q应用Euclidean GCD算法,但此处目的不是为了获得最大公约数,而是为了获得商数来创建p/q的渐近分数,此过程直到渐近分数的尺寸大到无法用flash表示为止。完整的算法如下(Kornerup and Matula [Korn83]):

给定p>=0,q>=1,

从i = 0开始,依次递增。当

bi?1 >0时,用bi?2除以bi?1,得到商ai和余数bi,因此:

然后计算:

译注:因 当

xi / yi大到无法放到一个flash表达式中时,将xi-1/ yi-1作为圆整结果。

由于圆整过程必须应用到所有的运算结果上,并且也因为它可能会相当慢,因此我们作了许多对它的实现的优化工作。采用了Lehmer的思路[Knuth81]——尽可能久的只操作数字中最重要的部分,因此迭代过程中大多只需要作单精度运算。另外也特别留意了避免圆整结果超出flash表达式的限制[Scott89a]。诸如log(x),exp(x),sin(x),cos(x),tan(x)等初始函数的计算中使用的基本运算过程采用了Brent [Brent76]描述的快速算法。

大多时候程序都能够保证给出的结果是精确的,这可以通过检查实例变量EXACT来确认,EXACT初始为TRUE,只有发生了圆整操作,才会被置为FALSE。

使用可变的flash类型来逼近实数的运算的一个缺陷是可表达的值之间的间隙不固定(Matula and Kornerup[Matula85])。

考虑一个分子分母乘积不超过256的floating-slash系统,显然小于1/1的第一个可表示数是15/16,间隙为1/16;比0/1大的下一个分数是1/255,间隙为1/255。通常,对一个k位的floating-slash系统,间隙大小从2^(-k)至2^(-k/2)不等。在实践中这意味着一个处于某个比较大的间隙中的实数的表示精度将只有平常的一半。幸运的是这样的间隙非常少见,而且精度会越来越高,仅在简分数附近出现(原文:Fortunately such large gaps are rare, and increasingly so for higher precision, occurring only near simple fractions)。但这也说明实际结果中,小数部分只有一半是能够完全信任的。此问题的一个局部解决方案是直接用连分数来表示有理数,这在间隙尺寸上能够提供更好的一致性(Kornerup and Matula [Korn85]),但是很难用高级语言实现。

flash类型上的算术运算无疑要比同等尺寸的多倍精度浮点类型慢(例如[Brent78])。flash的优势在于它精确表示有理数的能力,以及对它们的精确运算。由于中间数圆整优先选择简分数(原文:prefer a simple fraction over a complex one)的倾向,即使需要圆整,通常也能得到正确的结果。例如roots程序先计算2的平方根,再对结果求平方,得到的结果依然为2——尽管内部做过多次圆整。

警告:不要将flash运算与内置的double运算混合。它们无法和平相处,如果决定用flash运算,就自始至终使用它,开始的时候就将所有常量转换为flash类型。若能将常量表示为分数则更好:

x = Flash(5,8) //x = 5/8 上式比x = 0.625更好。

第七章 C++接口

许多MIRACL包的用户对下述情况很失望,对一个flash变更x,其运算: t = x?x?1

必须使用下列顺序代码: fmul(x, x, t); fadd(t, x, t); fincr(t, 1, 1, t); 而不能简单的写为: t=x*x +x + 1;

当然某些人可以用MIRACL库来写一个有特殊目的的可解释这样的指令的C编译器(有关这种方式的一个示例,参见Cherry and Morris [Cherry])。但并没有必要采用这么极端的措施。C++是C的一个超集,它自然地继承了C并获得了广泛的认同。C++对C的增强主要在于使它成为一种面向对象语言。通过将big和flash定义为一种“类型“(C++术语),可以重载常用的数学运算符,因而编译器能够自动将连接big或flash变量的操作符替换为对适当的MIRACL例程的调用。此外C++还可以通过定义在类中的构造器/析构器自动进行初始化和清除工作。这可以使程序员从重复调用mirvar来初始化big和flash变量的单调工作中解脱出来。确实,

2


MIRACL用户手册(译)(5).doc 将本文的Word文档下载到电脑 下载失败或者文档不完整,请联系客服人员解决!

下一篇:上海到厦门航空货运当日达哪家靠谱?

相关阅读
本类排行
× 注册会员免费下载(下载后可以自由复制和排版)

马上注册会员

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信: QQ: