特征3有限域上的椭圆曲线算法改进

减少求逆运算次数是快速计算椭圆曲线密码的主要方法之一。若采用逐次累加的方法计算特征3有限域上椭圆曲线标量乘法2kP,需要k次求逆运算。本文根据递推归纳、转换求逆为乘法的思想,推导了直接计算2kP的公式,使求逆运算降至1次。从理论上比较了两种计算方法的运算效率:所提出的新算法在k=4时比逐次累加计算量减少1%,并且减少量随着k的增大而增多,在极限情况下可减少约26%。     

构造有限域上具有给定阶点的椭圆曲线

考虑有限域上椭圆曲线的构造.设q是一个奇素数的方幂,l是一个素数.证明了,如果GF(q)[x]上的方程U²-D(x)V2=ε(x-a)^l有本原解,其中,D(x)∈GF(q)[x]是一个首1三次无平方因子的多项式,则椭圆曲线y²=D(x)上的点(a,b)的阶是l.由此,给出了一种构造具有给定阶点的椭圆曲线的算法.     

Idempotent Computation over Finite Fields

In this paper, we provide an account of several new techniques for computing the primitive idempotents of a commutative artinian algebra over a finite field. Examples of such algebras include the center of a finite group algebra or any finite dimensional quotient of a polynomial ring. The computational methods described are applicable in fairly general situations and the algorithms presented are easily programmed. Both pseudocode and operation counts are provided. As an application, the problem of factoring polynomials over finite fields is discussed.     

Factoring in Skew-polynomial Rings over Finite Fields

Efficient algorithms are presented for factoring polynomials in the skew-polynomial ringF[x;σ], a non-commutative generalization of the usual ring of polynomialsF[x], whereFis a finite field and σ:F → Fis an automorphism (iterated Frobenius map). Applications include fast functional decomposition algorithms for a class of polynomials inF[x] whose decompositions are “wild” and previously thought to be difficult to compute.     

有限域上稀疏多元多项式插值算法

稀疏插值是一种降低计算机代数算法时间复杂度的有效方法,在信号处理、压缩感知、结式计算、图像处理等领域都有广泛应用。为了提高稀疏多元多项式插值算法的效率,对Javadi/Monagan稀疏插值算法进行了改进。首先,消除了必须预先给定项数界T的限制,通过计算特定的矩阵行列式,得到插值多项式f的准确项数。然后,消除了必须预先给定次数界D的限制,通过构造辅助函数,利用概率法结合提前终止技术的Cauchy插值法,得到插值多项式f的准确次数,解决了Javadi和Monagan论文中提出的次数界D过高而导致的高计算复杂度的问题。理论分析和实验结果表明了改进算法的优势,特别是在给定的次数界D过高的情况下,相较于Javadi/Monagan算法,改进算法的性能有较大提高。更进一步,由于改进算法无须给定项数界T和次数界D,对于实际问题在利用插值恢复或近似时更具实用性。     

一类有限域上的置换多项式

有限域上的置换多项式在科学工程中的多个领域有着广泛的应用,尤其应用于现代通讯、密码学等领域中。基于Zha等人在文献[23]中提出,当t为偶数时,有限域Fpⁿ上形如(xp^k－x+δ)^t+γx+βTr(x)的多项式是置换的,通过进一步研究,运用证明置换多项式的一般方法,将其改进为无论t为奇数或偶数,(xp^k+1－x^p+δ)^t+γx+βTr(x)形式的多项式在Fpⁿ上均是置换的。     

有限域上椭圆曲线 Jacobian 群求阶算法综述与比较

关于椭圆曲线密码体制（ECC）的研究,如今无论是 ECC 理论还是 ECC 的标准化、产业化都趋于成熟。在 ECC 的设计中,安全椭圆曲线的选取是 ECC 实现的基石,也是其安全性的重要保证。目前,随机选取法是最好的安全椭圆曲线选取方法,其核心思想是对随机生成的椭圆曲线计算其 Jacobian 群的阶。文章主要介绍了几类经典的计算椭圆曲线 Jacobian群阶的算法：Schoof 算法、SEA 算法、Satoh 算法、AGM 算法。在详细介绍 Schoof 算法的基础上,提出了其基于离散对数问题的改进算法：袋鼠算法和大步小步（BSGS）算法的改进方法,并用实验结果说明加速后的算法得到了提升。针对 SEA 算法,文章也提出了其 BSGS 改进算法并通过实例分析比较了原 SEA 算法与 BSGS 改进算法的实现效率。针对 Satoh 算法、AGM算法,文章介绍了算法的理论依据和具体实现,并通过实例分析比较了其优劣性和适用情况。     

素数域上亏格为3的超椭圆曲线快速算法

本文给出了素数域上亏格为3的超椭圆曲线退化除子加法和倍点运算的确定性公式,这些公式在有固定基点的超椭圆曲线密码算法,如ElGamal型加密算法、Diffie-Hellman协议的发送方及HECDSA的标量乘算法中都有应用。与标准除子标量乘算法相比,给出的1次和2次退化除子标量乘算法可分别获得33．4％和16．7％的加速,同时基点的表示长度可压缩至标准除子表示长度的1／3或2／3。     

Efficient Decomposition of Associative Algebras over Finite Fields

We present new, efficient algorithms for some fundamental computations with finite-dimensional (but not necessarily commutative) associative algebras over finite fields. For a semisimple algebra A we show how to compute a complete Wedderburn decomposition of A as a direct sum of simple algebras, an isomorphism between each simple component and a full matrix algebra, and a basis for the centre of A. If A is given by a generating set of matrices inF^m × m, then our algorithm requires aboutO (m³) operations inF, in addition to the cost of factoring a polynomial inF[ x ] of degree O(m), and the cost of generating a small number of random elements from A. We also show how to compute a complete set of orthogonal primitive idempotents in any associative algebra over a finite field in this same time.     

有限域上二次型的密码学特性

该文给出有限域上二次型的紧致表示形式,讨论了它们的密码学特性;给出了特征等于2的有限域上．二次型是平衡函数的充要条件,并指出特征不等于2的有限域上．二次型都不是平衡函数;给出了二次函数是平衡函数的充要条件．从该文结果可以看出Pieprzyk等用二次函数构造的方案是错误的．     

一种基于有限域的快速乘法器的设计与实现

基于有限域上椭圆曲线公开密匙协议的离散对数计算算法正日益成为热点,而有限域上的计算尤其是乘法计算极大地影响其加／解密速度。为了提高椭圆曲线密码系统的计算速度,需要从很多方面考虑,但其中关键的一点在于如何提高乘法器的速度,且保持其规模在能够接受的范围。在对椭圆曲线的分析基础上提出了一种有限复合域GF((2^m1)^m2)上的快速乘法器。该乘法器采用并行计算和串行计算相结合的原则,在增加少量硬件规模将一次有限域乘法的计算速度由原来的m=m2m1个时钟周期降低到m2个时钟周期,从而极大地提高了乘法器的计算速度。通过FPGA的验证测试证明该方法在速度上完全适合椭圆曲线密码系统。     

Calculating Invariant Rings of Finite Groups over Arbitrary Fields

An algorithm is presented which calculates rings of polynomial invariants of finite linear groups over an arbitrary fieldK. Up to now, such algorithms have been available only for the case that the characteristic ofKdoes not divide the group order. Some applications to the question whether a modular invariant ring is Cohen—Macaulay or isomorphic to a polynomial ring are discussed.     

Multi-twisted Additive Codes with Complementary Duals over Finite Fields

Problems of Information Transmission - Multi-twisted (MT) additive codes over finite fields form an important class of additive codes and are generalizations of constacyclic additive codes. In this...     

Factorization of Polynomials over Finite Fields and Characteristic Sequences

A new factorization algorithm for polynomials over finite fields was recently developed by the first author. For finite fields of characteristic 2, it is known from previous work that this algorithm has several advantages over the classical Berlekamp algorithm. In this paper we show that the linearization step in the new algorithm is feasible—in the sense that it can be carried out in polynomial time—for arbitrary finite fields, by using an approach based on decimation operators and characteristic linear recurring sequences. We also introduce a general principle for the linearization of the factorization problem for polynomials over finite fields.     

基于有限域上圆锥曲线的公钥密码系统

随着Internet的迅猛发展,公钥密码系统以其算法简单、安全性高已经成为密码学领域的一个非常重要的研究课题.为了更加方便地构建公钥密码系统,文中在介绍了有限域上的圆锥曲线C(Fp)及其离散对数问题、明文嵌入与译码算法的基础上,给出了公钥密码系统在圆锥曲线C(Fp)上的模拟,这里户是奇素数,Fp为p元有限域.这些圆锥曲线密码系统的安全性是基于C(Fp)上离散对数的计算,较椭圆曲线密码系统更易于设计与实现.     

基于有限域上圆锥曲线的公钥密码系统

随着Internet的迅猛发展，公钥密码系统以其算法简单、安全性高已经成为密码学领域的一个非常重要的研究课题。为了更加方便地构建公钥密码系统，文中在介绍了有限域上的圆锥曲线C(Fp)及其离散对数问题、明文嵌入与译码算法的基础上，给出了公钥密码系统在圆锥曲线C(Fp)上的模拟，这里p是奇素数，Fp为p元有限域。这些圆锥曲线密码系统的安全性是基于C(Fp)上离散对数的计算，较椭圆曲线密码系统更易于设计与实现。     

Function Field Sieve Method for Discrete Logarithms over Finite Fields

We present a function field sieve method for discrete logarithms over finite fields. This method is an analog of the number field sieve method originally developed for factoring integers. It is asymptotically faster than the previously known algorithms when applied to finite fields F_pⁿ, where p⁶n.     

有限域上低差分函数研究进展

为了抵抗差分密码攻击,密码算法设计希望使用低差分函数.完全非线性函数(perfect nonli-near function, PN函数)、几乎完全非线性函数(almost perfect nonlinear function, APN函数)和4差分置换(differentially 4-uniform permutition)是最重要的几类低差分函数(low differential uniformity function).总结了近年来在PN函数、APN函数和4差分置换等低差分函数研究方面的主要进展.1)回顾了PN函数与半域等数学对象的联系,梳理了PN函数的已有构造以及伪平面函数的构造;2)分析了APN函数的性质与判定,总结了APN函数的已有构造以及它们之间等价性分析方面的结果;3)对于4差分置换,总结了其已有构造及其等价性分析结果;4)介绍了低差分函数在实际密码算法设计中的应用;5)对低差分函数的下一步研究进行了展望.     

Distributed Matrix-Free Solution of Large Sparse Linear Systems over Finite Fields

We describe a coarse-grain parallel approach for the homogeneous solution of linear systems. Our solutions are symbolic, i.e., exact rather than numerical approximations. We have performed an outer loop parallelization that works well in conjunction with a black box abstraction for the coefficient matrix. Our implementation can be run on a network cluster of UNIX workstations as well as on an SP-2 multiprocessor. Task distribution and management are effected through MPI and other packages. Fault tolerance, checkpointing, and recovery are incorporated. Detailed timings are presented for experiments with systems that arise in RSA challenge integer factoring efforts. For example, we can solve a 252,222 × 252,222 system with about 11.04 million nonzero entries over the Galois field with two elements using four processors of an SP-2 multiprocessor, in about 26.5 hours CPU time. Received June 1, 1997; revised March 10, 1998.