模n的大整数幂乘的一种快速算法

在RSA公钥密码体制中，要提高模n的大整数幂乘的运算效率，主要是解决两个方面的问题：（1）大整数的算术运算，特别是大整数的乘除法；（2）降低幂模运算的实际次数。文章从这两个方面进行研究，实现了大整数幂乘的一种快速计算。并给出了关键部分的算法，分析了算法的效率。     

RSA密码系统有效实现算法

大整数模幂乘运算一直是制约RSA广泛应用的瓶颈,在对传统算法剖析的基础上,提出了一种新的快速模乘算法,借鉴生成Wallace tree的思想,结合查找表和并行乘法运算进行RSA模幂运算。理论分析和试验证明新算法时间复杂度降低到O(logn)。     

公开密钥算法芯片的设计与实现

以RSA算法为例,探讨公钥密码处理芯片的设计与优化。首先提出公钥密码芯片实现中的核心问题,即大整数模幂运算算法和大整数模乘运算算法的实现;然后针对RSA算法,提出Montgomery模乘算法的CIOS方法的一种新的快速硬件并行实现方法,其中采用加法与乘法并行运算以及多级流水线技术以提高性能,较大地减少乘法运算时间,显著提高模乘器的运算性能。     

基于n-bit协处理器的2n-bit RSA实现

借助模幂乘协处理器是提升RSA性能最有效的方法,但当RSA模幂运算长度超过协处理器能支持的最大运算长度时,协处理器将不再适用。本文针对这个问题,基于中国剩余定理和Fischer、Seifert算法,在n－bit模幂乘协处理器的基础上实现了模长为2n-bitRSA算法,并利用模幂乘协处理器实现了n－bit大数乘法和除法,进一步提高了RSA运算效率。     

动态组合RSA算法

大整数模幂乘运算一直是制约RSA广泛应用的瓶颈，研究该课题具有重要的实际意义。提出了一种新的动态组合RSA算法。该算法在运用SMM算法和2k进制算法的基础上，结合模n和可变底数a对指数m动态取最优的幂后进行模幂乘运算。理论分析和试验证明新算法的最优时间复杂度可达到O（ln^2n）。     

大整数模幂的固定基窗口组合算法

模幂乘运算是实现公钥密码体制的一个很重要的运算,其运算速度从整体上决定了公钥密码体制的实现效率。通过采用预处理技术,将椭圆曲线的定点标量乘的固定基窗口方法应用在模幂运算中,与SMM算法进行组合得到一种新的求模幂乘算法——固定基窗口方法。对算法的原理与效率进行了分析,实验结果表明,算法的运算速度得到了有效提高。     

模幂运算安全外包算法的新设计

由于模幂运算的计算成本较高,资源有限的本地客户端可以将模幂运算外包给计算能力强大的云服务器。该算法主要研究形如ua(modN)的模幂运算的外包算法,其中N是两个大素数的乘积。其利用欧拉定理设计了一个基于双服务器模型的模幂运算安全外包方案。在运算外包过程中,保证底数u、指数a,以及运算结果对两个服务器的隐私保护。通过安全、效率分析和实验仿真表明,相较于现有方案,新方案具有更好的执行效率和可验证性,在用户端的效率更高,且新方案的可验证概率为1.     

实对称双线性函数与多精度整数的快速乘法

多精度整数乘法运算的效率对公钥密码系统中的模乘、模幂的运算效率起着决定性的作用.Toom-Cook算法是一类应用广泛的多精度整数的快速乘法算法,目前主要的研究方法是插值理论.本文利用实对称双线性函数和二次型的方法研究多精度整数的乘法和平方的快速计算,给出了Toom-Cook算法参数的所有代数表现形式和搜索快速算法的基本方法,提出了一些在实际应用中与目前已知结果相同或优于目前已知结果的快速乘法和平方算法.研究结果表明,利用实对称双线性函数和二次型表示Toom-Cook算法,更有利于判断算法的优劣程度和得到最优算法.     

模重复平方算法的rho改进算法

利用循环二进制方法给出了适合大指数模乘运算的模重复平方算法的rho改进算法,以提高模幂乘法的计算速度。新算法的实质是一种指数约减算法,可以有效减少模重复平方算法中的模乘运算。通过实例计算表明,新算法可以极大地提高运算速度。     

模幂与点乘m_ary算法中窗口大小的最优化估计

提出一种新大数模幂与点乘m_ary算法中窗口大小的最优化估计方法.该方法不同于传统的暴力搜寻方法,也不同于在窗口的取值范围内通过逐一测试程序来获得最优窗口大小的方法.其基于以下理论分析:模幂 m_ary算法的基本运算为大数乘法,其中包括大数平方算法和一般大数乘法;椭圆曲线加密算法中点乘的m_ary算法步骤与模幂的m_ary算法相同,后者的基本运算为倍乘和加法.根据m_ary算法的基本运算的调用次数,推算出了最优窗口大小的估计公式.通过实验对m_ary算法进行实现,并测试分析了根据估计公式计算出窗口大小的算法实现时间效率与理论分析基本吻合.     

C++中超长整数的存储与表示

提出在C++中利用32位汇编语言直接对内存操作的方法,实现对任意超长整数在计算机中的存储,给出任意超长整数的输入和输出的表示方法,以及主要程序算法框图和程序流程图.对其时间复杂度及所需空间复杂度进行分析,为直接在C++中调用提供便利条件,为实现在计算机中用超长整数运算代替浮点运算提供技术支持.     

Advanced Arithmetic for the Digital Computer,Design of Arithmetic Units

Advances in computer technology are now so profound that the arithmetic capability and repertoire of computers can and should be expanded. Nowadays the elementary floating-point operations +, −, ×, / give computed results that coincide with the rounded exact result for any operands. Advanced computer arithmetic extends this accuracy requirement to all operations in the usual product spaces of computation: the real and complex vector spaces as well as their interval correspondents. This enhances the mathematical power of the digital computer considerably. A new computer operation, the scalar product, is fundamental to the development of advanced computer arithmetic.This paper studies the design of arithmetic units for advanced computer arithmetic. Scalar product units are developed for different kinds of computers like personal computers, workstations, mainframes, super computers or digital signal processors. The new expanded computational capability is gained at modest cost. The units put a methodology into modern computer hardware which was available on old calculators before the electronic computer entered the scene. In general the new arithmetic units increase both the speed of computation as well as the accuracy of the computed result. The circuits developed in this paper show that there is no way to compute an approximation of a scalar product faster than the correct result.A collection of constructs in terms of which a source language may accommodate advanced computer arithmetic is described in the paper. The development of programming languages in the context of advanced computer arithmetic is reviewed. The simulation of the accurate scalar product on existing, conventional processors is discussed. Finally the theoretical foundation of advanced computer arithmetic is reviewed and a comparison with other approaches to achieving higher accuracy in computation is given. Shortcomings of existing processors and standards are discussed.     

利用剩余数制简化DNA算术运算

在DNA算术运算的理论模型中,普遍应用固定基数制,比如二进制、三进制。但是由于受到进位的影响,难以实现并行运算。基于Adleman-Lipton模型,分析了剩余数制的基本原理,改进了整数的DNA链表示,并将其应用于DNA算术运算,给出了剩余数制下进行DNA算术运算的算法模型。由于在剩余数制中,算术运算（加、减、乘）在剩余位之间无须进行进位计算,故可以降低运算过程的复杂度,而且有利于进行各个剩余位上的并行计算。     

基于超盒的装备系统灵敏度离散化分析

灵敏度分析是装备系统研究和开发过程中的重要环节,装备指标参数的灵敏度分析关系着装备系统研发的成败,但是在以往的灵敏度分析中,并没有针对超盒展开分析.对灵敏度分析方法进行了研究和分析.通过对灵敏度分析流程、作用和意义的介绍.在超盒理论的基础上,分析了连续性灵敏度分析算法,并进行了离散化分析,通过对计算量的试验仿真,将离散化分析和连续性分析的计算量进行对比,指出了离散化分析对于大型复杂系统存在计算量激增的风险.     

非法计算检测的通用模型

非法计算是导致系统崩溃的一个常见故障.文中总结了Java语言中可能产生非法计算的运算符和数学库函数;建立了一个通用模型,用以检测一般函数(包括系统函数和自定义函数)在使用时是否合法;基于该通用模型提出了非法计算检测算法,并在此算法中引入区间运算.实验结果表明,文中模型及算法可以在检测出更多的非法计算故障的同时降低误报率.     

Dynamic Force Distribution in Multifingered Grasping by Decomposition and Positive Combination

This paper presents a general algorithm for computing the optimal dynamic force distribution in multifingered grasping. It consists of two phases. In the offline phase, we select a spanning set for the required dynamic resultant wrench and find a corresponding spanning set for the total contact force. Then, in the online phase, the total contact force is obtained by decomposition of the resultant wrench into the former spanning set and a coefficient vector followed by positive combination of the latter spanning set with the vector. To make the online computation as simple as possible, iterative operation is executed offline and only arithmetic operation is employed online. To improve the grasping quality, the two spanning sets are selected elaborately.     

Hardware Support for Interval Arithmetic

A hardware unit for interval arithmetic (including division by an interval that contains zero) is described in this paper. After a brief introduction an instruction set for interval arithmetic is defined which is attractive from the mathematical point of view. These instructions consist of the basic arithmetic operations and comparisons for intervals including the relevant lattice operations. To enable high speed, the case selections for interval multiplication (9 cases) and interval division (14 cases) are done in hardware. The lower bound of the result is computed with rounding downwards and the upper bound with rounding upwards by parallel units simultaneously. The rounding mode must be an integral part of the arithmetic operation. Also the basic comparisons for intervals together with the corresponding lattice operations and the result selection in more complicated cases of multiplication and division are done in hardware. There they are executed by parallel units simultaneously. The circuits described in this paper show that with modest additional hardware costs interval arithmetic can be made almost as fast as simple floating-point arithmetic.     

扩展双精度浮点并行计算:MPI方法

双精度浮点并行计算将不能满足高性能计算领域对计算精度的要求,但是目前还没有高性能的超双精度并行计算的解决方法。基于并行编程语言MPI,本文提出了扩展双精度浮点的并行计算实现方法,并且使用精度敏感的圆周率计算BBP算法验证了该方法的正确性和性能。     

The exact dot product as basic tool for long interval arithmetic

Computing with guarantees is based on two arithmetical features. One is fixed (double) precision interval arithmetic. The other one is dynamic precision interval arithmetic, here also called long interval arithmetic. The basic tool to achieve high speed dynamic precision arithmetic for real and interval data is an exact multiply and accumulate operation and with it an exact dot product. Pipelining allows to compute it at the same high speed as vector operations on conventional vector processors. Long interval arithmetic fully benefits from such high speed. Exactitude brings very high accuracy, and thereby stability into computation. This document, which has been incorporated into the draft standard for interval arithmetic being developed by IEEE P1788, specifies the implementation of an exact multiply and accumulate operation.     

一种基于积分投影的矢量量化器的设计与实现

提出了一种积分投影和矢量量化（VQ）相结合的图像压缩算法,将图像的每一个4×4分块先进行积分投影,然后再与积分投影后的码书进行量化匹配,大大减少运算量和码书存储面积,而图像的质量只有轻微损失。实验结果表明,与普通VQ相比,本文算法的编码速度有很大幅度的提高,而解码图像的峰值信噪比（PSNR）平均仅降低0.25%,对于某些单纯背景的图像,解码后的质量比普通VQ还会有所增加,此算法有很大的应用前景。设计了编码电路,并在FPGA上进行了验证。整个系统最高时钟频率可达78.12 MHz。