GF（3^m）-ECC算法及其软件实现

研究GF（3^m）有限域算术、GF（3^m）上的椭圆曲线群算术和椭圆曲线密码协议。设计并实现椭圆曲线密码算法库,对各种GF（3^m）-ECC密码算法进行仿真和性能分析,结果表明GF（3^m）-ECC算法与GF（2^m）和GF（p）上的ECC算法效率相当,可以应用到基于ECC的各种安全协议设计中。     

基于GF(2m)域上椭圆曲线数字签名的快速实现

椭圆曲线数字签名是基于乘法群的离散对数数字签名在椭圆曲线上的模拟。本文讨论了椭圆曲线数字签名算法(ECDSA)在GF(2^m)域上的软件实现，提出了一种基于固定基的核心点乘运算的快速算法，提高了数字签名和签名验证的速度。     

两种智能卡芯片的ECDSA实现

探讨了有限域GF（2^n）上椭圆曲线密码算法基本理论、快速实现和ECDSA算法（椭圆曲线数字签名算法）实现的相关理论；然后采用INFINEON公司的携带域上求模运算的加速协处理模块（DDES-EC2）的智能卡芯片SLE66CL160S和SLE66CX320P，实现了基于有限域GF（2^n）上密钥长度为163bits的椭圆曲线数字签名算法，并对这两种实现进行了对比分析；最后对实现进行测试，证明是成功高效的。     

有限域GF（2^m）幂运算的一种新方法

在有限域GF（2^m）引进了开平方运算,描述了有限域GF（2^m）上利用开平方求幂的一种新方法。与经典的平方一乘求幂算法相比,在只增加少量预计算的情况下,新的方法所需GF（2^m）上的乘法运算少33％。     

GF（p）上安全椭圆曲线产生算法

研究素数域GF（p）（p〉3）上的椭圆曲线,讨论阶为素数的椭圆曲线的产生算法,在此基础上,分析阶为2个素数之积的椭圆曲线产生问题,并提出一种GF（p）上安全椭圆曲线的产生算法,给出椭圆曲线及其全体有理点的随机产生实例。仿真实验结果表明,该算法是有效可行的。     

具有防御功耗攻击性能的双域椭圆曲线密码处理器设计

提出了一种新型椭圆曲线密码处理器设计方案．采用OJW（最优联合权重）点乘调度算法加速点乘运算，该方法对椭圆曲线数字签名算法的验证运算尤为有效．通过引入双域求逆与Montgomery模乘相统一的算法和数据通路，处理器能进行任意GF（p）和GF（2^n）域上的有限域运算．同时针对简单功耗攻击和差分功耗攻击，本文提出了有效的抗攻击措施．基于SMIC 0．18CMOS工艺的实现结果表明，该设计在面积、速度、芯片抗攻击性能方面较同类设计有明显优势．     

一种双域Montgomery求逆算法与硬件实现

有限域上的求逆运算是椭圆曲线密码算法的关键运算之一。分别对GF（p）和GF（2ⁿ）域上的Montgomery模逆算法进行分析,并将GF（2ⁿ）域上的Montgomery模逆算法中对变量阶数的比较进行了改进,这样不仅利于GF（p）和GF（2ⁿ）域上的模逆运算在统一的硬件结构上实现,也解决了数据位数较大时进行阶数比较延迟较大的问题,在此基础上提出一种基于GF（p）和GF（2ⁿ）双域上统一的模逆算法,并根据算法,采用双域可伸缩运算单元,实现了一种可扩展的统一Montgomery模逆硬件结构。设计采用Verilog-HDL语言进行硬件描述,并基于0.18 μm工艺标准单元库进行了综合,结果表明该设计与其他设计相比具有灵活性好、性能高的特点。     

GF（2^m）上自适应正规基乘法器的FPGA实现

本文从实际应用出发,研究了GF：2^m）上基于正规基的乘法运算的FPGA的实现.采用w-SMPOⅡ算法,FPGA实现了任意域长m上的任意字长w的乘法器.并给出了几个域上的乘法器的面积和速度的比较分析.     

无移位操作的快速comb乘法算法

有限域GF(2n)上乘法运算是影响GF(2n)上椭圆曲线密码实现效率的关键运算之一.基于窗口技术的comb乘法算法,被认为是目前有限域GF(2n)上乘法运算最快的算法之一.但是,它仍然使用了移位操作,而移位操作恰好又是域GF(2n)乘法运算中很耗时的操作.提出并实现了一种新的基于窗口技术的快速comb乘法算法,该算法避免了移位操作,且不增加异或运算次数.理论分析和实验结果表明,新算法有很好的实现效率,适合于有限域GF(2n)上椭圆曲线密码算法的软件实现.     

并行可配置ECC专用指令协处理器

采用软硬件结合的方法,给出一种基于VLIW的并行可配置椭圆曲线密码体制（ECC）专用指令协处理器架构。该协处理器采用点加、倍点并行调度算法,功能单元微结构采用可重构的思想,具有高度灵活性与较高运算速度,能支持域宽可伸缩的GF（p）与G只2″）有限域上的可变参数Weierstrass曲线,签名认证算法可升级。实验结果表明,GF（p）域上192bit的ECC点乘运算只需0．32ms,比其他同类芯片运算速度提高了116％～350％。     

椭圆曲线中直接计算7P的方法及其应用

为了提高椭圆曲线标量乘法的效率,根据将求逆转换为乘法运算的思想,提出了在二进制域F2n上用仿射坐标直接计算7P的两种算法。两种算法分别通过引入公因子和除法多项式来计算7P,其运算量分别为2I+7S+14M和I+6S+20M,比Purohit等提出的算法(PUROHIT G N, RAWAT S A, KUMAR M. Elliptic curve point multiplication using MBNR and Point halving. International Journal of Advanced Networking and Applications, 2012, 3(5)： 1329-1337)分别节省了一次和两次求逆运算。同时还给出直接计算7kP的快速算法,该算法比重复计算k次7P更有效。最后结合半点运算和扩展多基表示形式将这些新算法应用到标量乘法中。实验结果表明,在美国国家标准技术研究所(NIST)推荐的椭圆曲线上,当预存储点的个数为2和 5时,新算法比Purohit算法效率提高了30%和37%,比洪银芳等所提的算法(洪银芳,桂丰,丁勇.基于半点和多基表示的标量乘法扩展算法.计算机工程,2011,37(4)：163-165)效率提高了9%和13%。新算法以增加少量的预计算存储为代价,能有效降低标量乘法的运算量。     

High-speed multidimensional convolution

Fast computation algorithms are developed for twodimensional and general multidimensional convolutions. Two basic techniques (overlap-and-add, overlap-and-save) are described in detail. These techniques allow speed and storage requirement tradeoffs and they define a decomposition of the total convolution into partial convolutions that can be easily found by parallel use of fast sequential cyclic convolution algorithms. It is shown that unlike what is the case in one dimension, the ``overlap-and-save' method enjoys a clear advantage over the ``overlap-and-add' method with respect to speed and storage in multidimensional convolution. A specific computational burden is assessed for the case where these methods are used in conjunction with radix-2 fast Fourier transform algorithms.     

Parallel Shear-Warp Factorization Volume Rendering Using Efficient 1-D and 2-D Partitioning Schemes for Distributed Memory Multicomputers

3-D data visualization is very useful for medical imaging and computational fluid dynamics. Volume rendering can be used to exhibit the shape and volumetric properties of 3-D objects. However, volume rendering requires a considerable amount of time to process the large volume of data. To deliver the necessary rendering rates, parallel hardware architectures such as distributed memory multicomputers offer viable solutions. The challenge is to design efficient parallel algorithms that utilize the hardware parallelism effectively. In this paper, we present two efficient parallel volume rendering algorithms, the 1D-partition and 2D-partition methods, based on the shear-warp factorization for distributed memory multicomputers. The 1D-partition method has a performance bound on the size of the volume data. If the number of processors is less than a threshold, the 1D-partition method can deliver a good rendering rate. If the number of processors is over a threshold, the 2D-partition method can be used. To evaluate the performance of these two algorithms, we implemented the proposed methods along with the slice data partitioning, volume data partitioning, and sheared volume data partitioning methods on an IBM SP2 parallel machine. Six volume data sets were used as the test samples. The experimental results show that the proposed methods outperform other compatible algorithms for all test samples. When the number of processors is over a threshold, the experimental results also demonstrate that the 2D-partition method is better than the 1D-partition method.     

Improved algorithms for searching restriction maps.

We present algorithms for searching a DNA restriction enzyme map for a region that best matches a shorter 'probe' map. Our algorithms utilize a new model of map alignments, and extensive experiments prove our model superior to earlier approaches for certain applications. Let M be the number of map sites and P be the number of probe sites. Our first algorithm, which optimizes only over a restricted class of alignments, requires O(MP log P) worst-case time and O(M + P) space. Our second algorithm, which optimizes over all alignments, runs in O(MP3) time and O(M + P2) space, under reasonable assumptions about the distribution of restriction enzyme cleavage sites. Combining the algorithms gives a map-searching method that optimizes over all alignments in O(MP log P) time in practice. The algorithms' effectiveness is illustrated by searches involving a genomic restriction map of Escherichia coli.     

ENVISAT/AATSR derived land surface temperature over a heterogeneous region

In this paper a method for evaluating land surface temperature (LST) algorithms over heterogeneous areas is presented. The evaluation was made for a set of 12 algorithms derived by using the split-window (SW) and dual-angle (DA) techniques for estimating sea and land surface temperature (SST and LST) from Advanced Along-Track Scanning Radiometer (AATSR) data. A validation of the proposed algorithms was carried out over a heterogeneous region of Morocco in the framework of the WATERMED (WATer use Efficiency in natural vegetation and agricultural areas by Remote sensing in the MEDiterranean basin) project. AATSR data and in situ measurements over this heterogenous region were compared by implementing a classification based strategy over a higher spatial resolution Landsat image. Three reference classes were considered when performing the classification from the Landsat image. Ground based measurements where then used to assign an effective surface radiometric temperature to each of these three classes. Finally, an averaging procedure based on class proportion was implemented for deriving surface radiometric temperature at the AATSR pixel scale. For this heterogeneous site, the results showed that LST can be obtained with a root mean-square error (RMSE) lower than 1.7 K from the split-window algorithms. Dual-angle algorithms, on the other hand, provided greater RMSE due to the different surfaces observed in the nadir and forward views. The results suggest that to retrieve LST from 1 km pixels over heterogeneous surfaces spatial averaging is required to improve accuracy on temperature estimation.     

Efficient time domain decomposition algorithms for parabolic PDE-constrained optimization problems

Optimization with time-dependent partial differential equations (PDEs) as constraints appears in many science and engineering applications. The associated first-order necessary optimality system consists of one forward and one backward time-dependent PDE coupled with optimality conditions. An optimization process by using the one-shot method determines the optimal control, state and adjoint state at once, with the cost of solving a large scale, fully discrete optimality system. Hence, such a one-shot method could easily become computationally prohibitive when the time span is long or time step is small. To overcome this difficulty, we propose several time domain decomposition algorithms for improving the computational efficiency of the one-shot method. In these algorithms, the optimality system is split into many small subsystems over a much smaller time interval, which are coupled by appropriate continuity matching conditions. Both one-level and two-level multiplicative and additive Schwarz algorithms are developed for iteratively solving the decomposed subsystems in parallel. In particular, the convergence of the one-level, non-overlapping algorithms is proved. The effectiveness of our proposed algorithms is demonstrated by both 1D and 2D numerical experiments, where the developed two-level algorithms show convergence rates that are scalable with respect to the number of subdomains.     

椭圆曲线中一种计算7P和7kP的改进算法

为了提高椭圆曲线底层域运算的效率,基于将乘法运算转换为平方运算的思想,提出在素数域[GFP]上用仿射坐标直接计算[7P]和[7kP]的改进算法,其运算量分别为[I+18M+12S]和[I+(17k+2)M+(14k+1)S],与已有的最好算法相比,效率分别提升了8.3%和10.3%。另外,基于相同的思想给出了素数域[GFP]上用仿射坐标系直接计算[5kP]的改进算法,其运算量为[I+(9k+2)M+(14k+1)S],与徐凯平和Mishra等人所提的算法相比,效率分别提升了17.2%和35.7%。     

分层并行遗传算法和遗传复合形算法及其应用

基于复合形算法、遗传算法、分层和并行思想,设计了一种求解复杂多目标、多约束和多变量工程优化问题的分层并行遗传或复合形算法,编制了界面友好和计算可靠性高的VC++软件。对于一类复杂三多工程综合优化问题,进行了遗传算法、复合形算法、分层并行遗传算法和分层并行遗传复合形算法的大量计算,结果表明：分层并行遗传算法计算效率最高;为解决复杂的三多工程综合优化问题提供了有效的可行方法。     

Efficient computation of Zernike and Pseudo-Zernike moments for pattern classification applications

Two novel algorithms for the fast computation of the Zernike and Pseudo-Zernike moments are presented in this paper. The proposed algorithms are very useful, particularly in the case of using the computed moments, as discriminative features in pattern classification applications, where the computation of single moments of several orders is required. The derivation of the algorithms is based on the elimination of the factorial computations, by computing recursively the fractional terms of the orthogonal polynomials being used. The newly introduced algorithms are compared to the direct methods, which are the only methods that permit the computation of single moments of any order. The computational complexity of the proposed method is O(p ²) in multiplications, with p being the moment order, while the corresponding complexity of the direct method is O(p ³). Appropriate experiments justify the superiority of the proposed recursive algorithms over the direct ones, establishing them as alternative to the original algorithms, for the fast computation of the Zernike and Pseudo-Zernike moments.     

Parallel Poisson and Biharmonic solvers

In this paper we develop direct and iterative algorithms for the solution of finite difference approximations of the Poisson and Biharmonic equations on a square, using a number of arithmetic units in parallel. Assuming ann×n grid of mesh points, we show that direct algorithms for the Poisson and Biharmonic equations require 0(logn) and 0(n) time steps, respectively. The corresponding speedup over the sequential algorithms are 0(n ²) and 0(n ²logn). We also compare the efficiency of these direct algorithms with parallel SOR and ADI algorithms for the Poisson equation, and a parallel semi-direct method for the Biharmonic equation treated as a coupled pair of Poisson equations.