查找整系数不可约多项式的新算法与实现程序

本文利用一种独特的映射方法将整系数多项式映射为计算机容易处理的真分数。运用该映射方法建立了一种新的算法，编写了FoxPro程序，找出了整系数不可约多项式，并且可以对这些不可约多项式按需要进行排序或查找。因此，为扩频通信与信道密码等寻找和利用不可约多项式提供了一种可行且实用的算法和程序。     

找到不可约多项式的研究与FoxPro程序实现

在扩频通信与传统的密码体制中广泛使用的伪随机序列,大部分是利用不可约多项式通过反馈位移寄存器和其他非线性逻辑来产生的。同时,多项式理论,特别是不可约多项式的性质对分析各种伪随机序列有着特殊的作用。 (1)找到非负整系数不可约多项式的原理 建立非负整系数多项式与正整数的符号对应和运算对应:设α_0,α_1,α_2,α_3,…,α_n是非负整数,2,3,5,7,…,p_n是n+1个相邻的素数。用正整数2~(α_0)3~(α_1)5~(α_2)(?)p_n~(α_n)表示非负整系数多项式α_0+α_1x+α_2x~2+…+α_nx~n。记作:{α_0+α_1x+α_2x~2+…+α_nx~n}←→2~(α_0)3~(α_1)5~(α_2)(?)p_n~(α_n)。     

广义预测控制的deadbeat性质研究*

本文利用广义预测控制中对象与闭环特征多项式之间的系数映射关系，分析了闭环系统特征多项式系数为零的条件，导出了ＧＰＣ闭环系统ｄｅａｄｂｅａｔ性质完善而新颖的理论结果，并提供了一种基于系数空间映射的新思路来研究ＧＰＣ的性质。     

中国剩余算法在多元多项式最大公因式提取中的应用

本文研究了利用中国剩余算法提取多元整系数多项式的最大公因式的算法,首先将多项式通过同态映射进行逐元化简,直至化为一元多项式,并对一元多项式提取最大公因式,然后利用中国剩余算法对一元最大公因式进行逐元反复提升,最后可得到多元多项式的最大公因式。大量的算例表明该算法是求解多元整系数多项式最大公因式的一种有效算法。     

GF(2m)域上可配置ECC算术模块的设计与实现

提出一种应用于可配置椭圆曲线密码体制的有限域多项式算术模块结构,乘法器基于已有的digit-serial结构乘法器,利用局部并行的bit-parallel结构,省去了模约简电路,使乘法器可适用于任意不可约多项式。平方器结构利用LSB或LSD乘法器以及加法器来计算模平方,通过数据接口控制输入数据的格式,可以满足不同域值有限域点乘运算的需求。     

立方多变量公钥密码体制的最小秩分析

立方加密体制是经典的多变量公钥密码体制Square的改进方案,其中心映射由平方映射改为了立方映射,由此将公钥多项式从二次提升到三次来抵抗针对二次多变量公钥密码体制的最小秩攻击。针对这种体制,提出一种结合差分的最小秩攻击,旨在恢复它的私钥。首先,分析体制的中心映射差分,并根据差分后的结构来确定它的秩;然后,求解公钥差分,并提取二次项的系数矩阵;接着,由系数矩阵以及确定的秩构造一个最小秩问题;最后,结合扩展的Kipnis-Shamir方法对问题进行求解。实验结果表明,利用最小秩攻击可以恢复立方加密体制的私钥。     

一类非最小相位系统的PID控制器整定方法

针对非最小相位对象,提出了一种比例—积分—微分(PID)控制器的整定方法.将含有右半复平面零点的非最小相位系统近似拟合为一个稳定的大滞后系统,应用一种专门针对大滞后系统的PID参数两步整定方法可以对系统PID参数进行粗调,然后通过调整比例系数α,便可以成功地设置其PID控制器参数,达到抑制非最小相位时滞和负调的作用.仿真实验证明了两步整定方法的有效性和鲁棒性.     

计算机实现多项式分解的一种实用算法

在计算机密码学和计算机通信研究过程中,关于多项式分解的方法灵活多变,技巧性强。本文给出了便于计算机高效准确地分解多项式的一种实用算法,并阐明了该算法的原理,同时介绍了多项式分解的详细步骤。     

Krylov方法在整矩阵计算中的应用

我们称元素全为整数的矩阵为整矩阵,n阶整矩阵的特征多项式、最小多项式、不变因子都是首1整系数多项式.如何通过计算机精确求出整矩阵的不变因子是本文讨论的主题. 根据向量空间分解为循环子空间直和的理论(参见本文5),求不变因子的问题可以归结为求一组商空间的最小多项式.因此,从计算角度考虑,求空间(或矩阵)的最小多项     

一种混沌分组密码的设计及分析

S(Substitution)-盒是分组密码算法中关键的非线性变换，本文首先通过量化函数把混沌系统作用的无限域映射到S-盒作用的有限域，分析了量化状态的一些特性，然后提出一种利用混沌量化状态构造S盒的方法。这种方法充分利用了混沌系统良好的伪随机特性、轨道的不可预测性和系统对初始状态及控制参数的敏感性，大大提高了构造高强度S-盒的效率。统计检验的结果表明，用混沌量化状态构造的S盒具有较强的安全性。     

Application of Symbolic Approach to the Bernstein Expansion for Program Analysis and Optimization

Mathematical packages for static analysis of programs have recently been developed. Although these packages are widely used, they have a number of limitations. In particular, they do not support multivariate polynomials with integer coefficients, which are often met in programs and used for the analysis of systems. Some methods to overcome this difficulty have already been suggested, but, unfortunately, they can be applied to only a subclass of such expressions. In this paper, we suggest a more general approach based on the Bernstein expansion, which facilitates the analysis of integer multivariate polynomials.     

Optimal Algorithm for Algebraic Factoring

This paper presents on optimized method for factoring multivariate polynomials over algebraic extension fields defined by an irreducible ascending set. The basic idea is to convert multivariate polynomials to univariate polynomials and algebraic extension fields to algebraic number fields by suitable integer substituteions.Then factorize the univariate polynomials over the algebraic number fields.Finally,construct mulativariate factors of the original polynomial by Hensel lemma and TRUEFACTOR test.Some examples with timing are included.     

Local Limit Properties for Pattern Statistics and Rational Models

Motivated by problems of pattern statistics, we study the limit distribution of the random variable counting the number of occurrences of the symbol a in a word of length n chosen at random in {a,b}^*, according to a probability distribution defined via a rational formal series s with positive real coefficients. Our main result is a local limit theorem of Gaussian type for these statistics under the hypothesis that s is a power of a primitive series. This result is obtained by showing a general criterion for (Gaussian) local limit laws of sequences of integer random variables. To prove our result we also introduce and analyse a notion of symbol-periodicity for irreducible matrices, whose entries are polynomials over positive semirings; the properties we prove on this topic extend the classical Perron--Frobenius theory of non-negative real matrices. As a further application we obtain some asymptotic evaluations of the maximum coefficient of monomials of given size for rational series in two commutative variables.     

Computing GCDs of Polynomials over Algebraic Number Fields

Modular methods for computing the gcd of two univariate polynomials over an algebraic number field require a priori knowledge about the denominators of the rational numbers in the representation of the gcd. A multiplicative bound for these denominators is derived without assuming that the number generating the field is an algebraic integer. Consequently, the gcd algorithm of Langemyr and McCallum [J. Symbolic Computation8, 429 - 448, 1989] can now be applied directly to polynomials that are not necessarily represented in terms of an algebraic integer. Worst-case analyses and experiments with an implementation show that by avoiding a conversion of representation the reduction in computing time can be significant. A further improvement is achieved by using an algorithm for reconstructing a rational number from its modular residue so that the denominator bound need not be explicitly computed. Experiments and analyses suggest that this is a good practical alternative.     

An Architecture-Independent Graphical Tool for Automatic Contention-Free Process-to-Processor Mapping

Mapping of parallel programs onto parallel computers for efficient execution is a fundamental problem of great significance in parallel processing. This paper presents an architecture-independent software tool for contention-free mapping of arbitrary parallel programs onto parallel computers with arbitrary configurations. This mapping tool is based on an efficient heuristic algorithm that runs in time O(n ³+m ⁴) in the worst case for mapping n tasks onto m processors, where m n in most practical cases. It is fully implemented and incorporated into a graph editing system to produce a graphical mapping tool which enables its user to monitor and control the mapping process. The user can assist the mapping process or employ the algorithm to map automatically. Our mapping tool has been tested and its performance evaluated extensively. Experimental results show that our tool combines user intuition and mapping heuristics effectively to make it a powerful mapping tool which is practical to use. Our mapping tool can be easily extended for use in the more general case when the link contention-degree is bounded to a fixed system-specified value without increasing its complexity.     

Guaranteed Stability of Polynomials Under Application of a Uniform Nonnegative Polynomial Mapping on Coefficients

This note presents a new result for the guaranteed stability of polynomials under uniform non-negative polynomial mapping on the coefficients.      

Construction of mappings with attracting cycles

In [1], two methods to construct polynomial mappings with periodic points are given with Lagrange interpolation and Newton interpolation, and a conjecture that such polynomial mappings with chaotic behaviors should be a “generalized primitive polynomial” is raised. In this paper, we additionally consider stability of periodic points and give a new method to construct polynomial mappings with attracting cycles or superstable cycles. Based on this construction, we show how to further construct a mapping which is not in polynomial forms but possesses the same periodicity. We also discuss properties of such polynomials with integer cycles. Finally, we point out a falsity in [1] and give counterexamples against the conjecture in [1].     

A Note on Robust Stability Analysis of Fractional Order Interval Systems by Minimum Argument Vertex and Edge Polynomials

By using power mapping (s=vm), stability analysis of fractional order polynomials was simplified to the stability analysis of expanded degree integer order polynomials in the first Riemann sheet. However, more investigation is needed for revealing properties of power mapping and demonstration of conformity of Hurwitz stability under power mapping of fractional order characteristic polynomials. Contributions of this study have two folds:Firstly, this paper demonstrates conservation of root argument and magnitude relations under power mapping of characteristic polynomials and thus substantiates validity of Hurwitz stability under power mapping of fractional order characteristic polynomials. This also ensures implications of edge theorem for fractional order interval systems. Secondly, in control engineering point of view, numerical robust stability analysis approaches based on the consideration of minimum argument roots of edge and vertex polynomials are presented. For the computer-aided design of fractional order interval control systems, the minimum argument root principle is applied for a finite set of edge and vertex polynomials, which are sampled from parametric uncertainty box. Several illustrative examples are presented to discuss effectiveness of these approaches.      

Reduction of 2-D rational functions

This paper presents a method of reducing a two-dimensional (2-D) rational function to an irreducible one. It is achieved by searching the first linearly dependent row, in order from top to bottom, of a generalized resultant. Some properties of the resultant are discussed. The result can be used to compute the greatest common divisor (g.c.d.) of two 2-D polynomials by carrying out one additional division. This procedure does not require the computation of primitive polynomials, which is required by all existing methods, and thus provides a potentially attractive method of computing g.c.d. The method can be readily extended to three-or higher-dimensional cases.     

Constrained intervals and interval spaces

Constrained intervals, intervals as a mapping from [0, 1] to polynomials of degree one (linear functions) with non-negative slopes, and arithmetic on constrained intervals generate a space that turns out to be a cancellative abelian monoid albeit with a richer set of properties than the usual (standard) space of interval arithmetic. This means that not only do we have the classical embedding as developed by H. Radström, S. Markov, and the extension of E. Kaucher but the properties of these polynomials. We study the geometry of the embedding of intervals into a quasilinear space and some of the properties of the mapping of constrained intervals into a space of polynomials. It is assumed that the reader is familiar with the basic notions of interval arithmetic and interval analysis.