基于有限域上Chebyshev多项式的密钥协商方案

利用传统RSA算法和有限域上离散对数问题,提出一种新的基于混沌映射的密钥协商方案。该方案基于有限域上Chebyshev多项式良好的半群特性,运用RSA算法巧妙地隐藏通信双方产生的有限域上的Cheby-shev多项式值,从而避免了以往的种种主动攻击,保证了密钥协商的安全;同时,该密钥协商方案还实现了身份认证功能。理论分析和软件实现证明了该方案的可行性、正确性和安全性。     

用线性码构造DNA计算编码的海明距离

最小海明距离是DNA计算编码性能的重要评价标准。利用线性码来构造DNA计算编码的最小海明距离是一种有效的方法,关键在于构造相应的监督矩阵。为了寻找监督矩阵,提出了监督矩阵的搜索算法和优化方法,及两个必要性定理;作为介于最小海明距离上限与下限之间的编码存在性的判断依据,给出了两个关于线性码存在性定理;最后给出了三字母表DNA计算编码相关的监督矩阵搜索算法结果,以及当最小海明距离一定时,接近编码数量上限的部分线性码的存在性结果。根据这些结果和存在性定理,可以推断常用DNA计算编码最小海明距离的存在性。     

Chebyshev polynomials over finite fields and reversibility of σ-automata on square grids

Using number theory on function fields and algebraic number fields, we prove results about Chebyshev polynomials over finite prime fields to investigate reversibility of two-dimensional additive cellular automata on finite square grids. For example, we show that there are infinitely many primitive irreversible additive cellular automata on square grids when the base field has order two or three.     

Involution codes: with application to DNA coded languages

For an involution θ : Σ^* → Σ^* over a finite alphabet Σ we consider involution codes: θ-infix, θ-comma-free, θ-k -codes and θ-subword-k-codes. These codes arise from questions on DNA strand design. We investigate conditions under which both X and X⁺ are same type of involution codes. General methods for generating such involution codes are given. The information capacity of these codes show to be optimized in most cases. A specific set of these codes was chosen for experimental testing and the results of these experiments are presented.     

基于有限域分圆陪集的BCH码参数盲估计

BCH码作为一种循环码在通信领域有很广泛的应用,提出一种基于有限域分圆陪集的BCH码参数估计方法。由于该方法利用了BCH码的汉明码特性,实现了码组同步时刻和码长的快速估计,利用分圆陪集原理,准确估计出BCH码的生成多项式。仿真实验结果表明,该方法具有所需数据量少、识别速度快、抗误码性能好的特点。     

Deterministic distinct-degree factorization of polynomials over finite fields

A deterministic polynomial time algorithm is presented for finding the distinct-degree factorization of multivariate polynomials over finite fields. As a consequence, one can count the number of irreducible factors of polynomials over finite fields in deterministic polynomial time, thus resolving a theoretical open problem of Kaltofen from 1987.     

环F2+uF2+u2F2上的线性码及其Gray像

记R=F₂+uF₂+u²F₂,R₁=F₂+uF₂,定义了从Rⁿ到F³ⁿ₂的Gray映射Ф以及从Rⁿ₁到Rⁿ的映射f。通过对环R上线性码C的生成矩阵的研究,给出了线性码C的对偶码C^⊥和Gray像Ф（C）的生成矩阵,并且Ф（C）与Ф（C^⊥）是F₂上的对偶码。通过映射f将环R₁上的线性码与环R上的一类线性码对应起来。     

A class of 1-generator quasi-cyclic codes over finite chain rings

Using another method, which is different with the one given by Cao [1-generator quasi-cyclic (QC) codes over finite chain rings, Appl. Algebra Eng. Commun. Comput. 24 (2013), pp. 53–72], we investigate the structural properties of a class of 1-generator QC codes over finite chain rings. We give the structure of the annihilator of 1-generator QC codes, the conditions for 1-generator QC codes to be free and the minimum distance bounds on 1-generator QC codes. Under some conditions, we also discuss the enumeration of 1-generator QC codes and describe how to obtain the one and only one generator for each 1-generator QC code.     

环F2+vF2上线性码的MacWilliams恒等式*

定义了环F2 vF2上码字的李重量分布的概念,利用域F2上线性码和对偶码的重量分布的关系及gray映射,给出了该环上线性码与对偶码之间各种重量分布的MacWilliams恒等式。     

几类线性码的扩展码及其在密钥共享中的应用

极小线性码在构造安全高效访问结构上的密钥共享方案中应用广泛。研究了几类线性码的扩展码,并得出了其参数和重量分布。结果表明,这些扩展码都是极小码,可用于构造密钥共享方案。此外,还给出了一些最优码或几乎最优码。     

对偶距离为5的极大自正交码及其子码

研究了自对偶码与其删截得到的极大自正交码的等价性问题。利用删截法构造出码长n满足21≤n≤29、对偶距离为5的二元极大自正交码。再用随机搜索算法研究了所得到的二元极大自正交码的子码,构造出它们的对偶距离为3和5的子码的生成矩阵。研究了这些子码构成的码链以及它们的对偶码构成的码链。利用所得到的码链,由Steane构造法构造出距离为5的具有很好参数的量子纠错码。     

An efficient algorithm for decomposing multivariate polynomials and its applications to cryptography

In this paper, we present an efficient and general algorithm for decomposing multivariate polynomials of the same arbitrary degree. This problem, also known as the Functional Decomposition Problem (FDP), is classical in computer algebra. It is the first general method addressing the decomposition of multivariate polynomials (any degree, any number of polynomials). As a byproduct, our approach can be also used to recover an ideal I from its kth power I^k. The complexity of the algorithm depends on the ratio between the number of variables (n) and the number of polynomials (u). For example, polynomials of degree four can be decomposed in , when this ratio is smaller than . This work was initially motivated by a cryptographic application, namely the cryptanalysis of 2R⁻ schemes. From a cryptographic point of view, the new algorithm is so efficient that the principle of two-round schemes, including 2R⁻ schemes, becomes useless. Besides, we believe that our algorithm is of independent interest.     

Quotients of Gaussian graphs and their application to perfect codes

A graph-based model of perfect two-dimensional codes is presented in this work. This model facilitates the study of the metric properties of the codes. Signal spaces are modeled by means of Cayley graphs defined over the Gaussian integers and denoted as Gaussian graphs. Codewords of perfect codes will be represented by vertices of a quotient graph of the Gaussian graph in which the signal space has been defined. It will be shown that any quotient graph of a Gaussian graph is indeed a Gaussian graph. This makes it possible to apply previously known properties of Gaussian graphs to the analysis of perfect codes. To illustrate the modeling power of this graph-based tool, perfect Lee codes will be analyzed in terms of Gaussian graphs and their quotients.     

DNA编码限制条件与编码策略

以评价DNA编码的基本限制条件之一——Hamming距离为出发点分析了DNA编码的三个参量：码字个数、码字长度与Watson-Crick Hamming距离,并得到它们之间的内在联系;讨论了Watson-Crick Hamming距离与DNA码字重量之间的关系;在此基础上得到了DNA编码的编码策略;提出了适合DNA编码的改进Watson-Crick Hamming距离及DNA编码模块化的定义,对DNA编码的优化做出了详细分析,为DNA计算的发展注入了活力。     

Decomposition of algebras over finite fields and number fields

We consider the boolean complexity of the decomposition of semi-simple algebras over finite fields and number fields.We present new polynomial time algorithms for the decomposition of semi-simple algebras over these fields. Our algorithms are somewhat simpler than previous algorithms, and provide parallel reductions from semi-simple decomposition to the factorization of polynomials. As a consequence we obtain efficient parallel algorithms for the decomposition of semi-simple algebras over small finite fields. We also present efficient sequential and parallel algorithms for the decomposition of a simple algebra from a basis and a primitive idempotent. These will be applied in a subsequent paper to obtain Las Vegas polynomial time algorithms for the decomposition of matrix algebras over and .     

Single-factor lifting and factorization of polynomials over local fields

Let f(x)$f\left(x\right)$ be a separable polynomial over a local field. The Montes algorithm computes certain approximations to the different irreducible factors of f(x)$f\left(x\right)$, with strong arithmetic properties. In this paper, we develop an algorithm to improve any one of these approximations, till a prescribed precision is attained. The most natural application of this “single-factor lifting” routine is to combine it with the Montes algorithm to provide a fast polynomial factorization algorithm. Moreover, the single-factor lifting algorithm may be applied as well to accelerate the computational resolution of several global arithmetic problems in which the improvement of an approximation to a single local irreducible factor of a polynomial is required.