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.     

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

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

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.     

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

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

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.     

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...     

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

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

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)对低差分函数的下一步研究进行了展望.     

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

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

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.     

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

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

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

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

Applying SAT Solving in Classification of Finite Algebras

The classification of mathematical structures plays an important role for research in pure mathematics. It is, however, a meticulous task that can be aided by using automated techniques. Many automated methods concentrate on the quantitative side of classification, like counting isomorphism classes for certain structures with given cardinality. In contrast, we have devised a bootstrapping algorithm that performs qualitative classification by producing classification theorems that describe unique distinguishing properties for isomorphism classes. In order to fully verify the classification it is essential to prove a range of problems, which can become quite challenging for classical automated theorem provers even in the case of relatively small algebraic structures. But since the problems are in a finite domain, employing Boolean satisfiability solving is possible. In this paper we present the application of satisfiability solvers to generate fully verified classification theorems in finite algebra. We explore diverse methods to efficiently encode the arising problems both for Boolean SAT solvers as well as for solvers with built-in equational theory. We give experimental evidence for their effectiveness, which leads to an improvement of the overall bootstrapping algorithm.     

弱可逆有限自动机的分解

有限自动机公开钥密码体制的提出进一步激励了有限自动机可逆性的研究．在有限自动机公开钥密码体制中首次提出了自动机化合的概念．易知,两个弱可逆有限自动机的化合仍然是一个弱可逆有限自动机并且它的延迟步数不大于前两个有限自动机延迟步数之和．然而,另一方面,如何将一个弱可逆有限自动机分解为两个弱可逆有限自动机的化合却是一个非常困难的问题．该文主要考虑了一类n元严格延迟τ步弱可逆有限自动机M的延迟步数的分解问题．给出了一类特殊的n元弱可逆有限自动机分解的条件和结果．首先证明了如果对M中的每个状态s有T（s,τ）枝等,则M可分解为τ个延迟1步弱可逆有限自动机的化合．然后证明了M可分解为一个τ—m步弱可逆有限自动机和m阶延迟元的充要条件是对M中的每个状态s有T（s,m）枝等．     

Some Classes of Balanced Functions over Finite Fields with a Small Value of the Linear Characteristic

Problems of Information Transmission - We present balanced functions over finite fields with a small value of the linear characteristic. Previously, linear characteristics of similar classes of...     

Simulation Preorder over Simple Process Algebras

We consider the problem of simulation preorder/equivalence between infinite-state processes and finite-state ones. First, we describe a general method how to utilize the decidability of bisimulation problems to solve (certain instances of) the corresponding simulation problems. For certain process classes, the method allows us to design effective reductions of simulation problems to their bisimulation counterparts and some new decidability results for simulation have already been obtained in this way. Then we establish the decidability border for the problem of simulation preorder/equivalence between infinite-state processes and finite-state ones w.r.t. the hierarchy of process rewrite systems. In particular, we show that simulation preorder (in both directions) and simulation equivalence are decidable in EXPTIME between pushdown processes and finite-state ones. On the other hand, simulation preorder is undecidable between PA and finite-state processes in both directions. These results also hold for those PA and finite-state processes which are deterministic and normed, and thus immediately extend to trace preorder. Regularity (finiteness) w.r.t. simulation and trace equivalence is also shown to be undecidable for PA. Finally, we prove that simulation preorder (in both directions) and simulation equivalence are intractable between all classes of infinite-state systems (in the hierarchy of process rewrite systems) and finite-state ones. This result is obtained by showing that the problem whether a BPA (or BPP) process simulates a finite-state one is PSPACE-hard and the other direction is co -hard; consequently, simulation equivalence between BPA (or BPP) and finite-state processes is also co -hard.