代数扩张域上的多项式分解在密码学中的应用

用有理数域或特征p的素域上的有n个独立变量的有理函数域的有限代数扩张域上的多项式的不可约分解,建议了一类密码系统.     

涉及坐标变换的微分多项式在求和约定下的化简和标准型

在n维微分几何中,基本的几何结构和性质常常用Einstein求和约定的带指标函数局部刻画．这种函数的符号计算虽然是计算机代数里最古老的研究课题之一,但直到现在也没有一个完全的算法来判定涉及不同坐标系的两个指标多项式是否相等．这是计算机代数里的一个挑战性问题． 本文针对一种典型的框架：当涉及的坐标变换矩阵的偏导不超过二次时（例如普通的曲率和挠率的局部计算）,提出了一个能消去指标多项式中所有冗余指标的消元算法,以及一个将指标多项式化为标准型,从而能完全判定两个指标多项式是否相等的算法．我们在Maple10中实现了以上算法,并用于研究微分几何中的张量判定等坐标变换下的规律问题．     

求鳞状循环因子矩阵的极小多项式的算法

提出了任意域上鳞状循环因子矩阵 ,利用多项式环的理想的Go bner基的算法给出了任意域上鳞状循环因子矩阵的极小多项式和公共极小多项式的一种算法 .同时给出了这类矩阵逆矩阵的一种求法 .在有理数域或模素数剩余类域上 ,这一算法可由代数系统软件Co CoA4 .0实现 .数值例子说明了算法的有效性     

二元整系数多项式因式分解的一种理论和算法

将二元多项式看成系数为一元多项式的一元多项式来进行分解，本文建立了二元整系数多项式因式分解的一种理论，提出了一个完整的分解二元整系数多项式的新算法．这个算法能自然地推广到多元整系数多项式的分解中去．     

带约束动力学辛算法的符号计算

首先对带约束动力学中的辛算法作了改进,利用吴消元法求解多项式类型Euler-Lagrange方程.在辛算法的基础上,根据线性方程组理论和相容条件提出了一个求解约束的新算法.新算法的推导过程比辛算法严格,而且计算也比辛算法简单,并且多项式类型的Euler-Lagrange仍可以用吴消元法求解.另外,对于某些非多项式类型的Euler-Lagrange方程,可以先化为多项式类型,再用吴消元法求解.利用符号计算软件,上述算法都可以在计算机上实现.     

谈谈双二次多项式的因式分解

形如 f(z)=x~4+px~2+q 的多项式称为双二次多项式。我们知道,在复数域上 f(x)总可按固定的方法分解为四个一次因式之积,此不赘述。本文打算分别谈谈 f(x)在实数和有理数域上的因式分解问题。在实数域上,当 p~2-4q≥0时,我们可以用     

吴消元法在Lagrange和Hamilton方程中的应用

主要借鉴吴消元法,研究带约束动力学中多项式类型Lagrange方程和Hamilton方程,提出了一种求约束的新算法．与以前算法相比,新算法无需求Hessian矩阵的秩,无需判定方程的线性相关性,从而大为减少了计算步骤,且计算更为简单．此外,计算过程中膨胀较小,且多数情形下无膨胀．利用符号计算软件,新算法可在计算机上实现．     

分解多项式升列为不可约升列的算法

对有理数域或特征为正的素域上的多项式升列,给出了把它的零点集分解为不可约分支的算法.该算法可以在计算机上用王定康的软件包“wsolve”实现.     

整系数多元多项式快速分解（1）——初始化算法

对于一般形式的整系数多元多项式Ｆ（ｘ１，ｘ２，…，ｘｔ）进行因式分解，通常总是首先选定一个变量，比如Ｘｔ，作为主变量，将下的因式分解转化为对关子Ｘｔ首１的，并使Ｆ＊（０，…，０，Ｘｔ）无重因式的多元多项式Ｆ＊进行分解．本文给出了这种转化的一个新算法．由此算法而得到的Ｆ＊之规模要明显地小于以前的方法的结果，从而使得进一步分解Ｆ＊以得到Ｆ的因式分解的计算时间复杂可以大大地降低．     

因式分解中常用的变形技巧

因式分解是初中代数的重要内容.教材中介绍了四种基本方法.因式分解的题型多、方法灵活,有些是不能直接应用四种基本方法的,而需要适当的恒等变形,改变多项式的原有结构,方能找到奏效方法.下面列举几例,向同学们介绍几类常用的变形技巧.     

An efficient algorithm for factoring polynomials over algebraic extension field

An efficient algorithm is proposed for factoring polynomials over an algebraic extension field defined by a polynomial ring modulo a maximal ideal. If the maximal ideal is given by its Gröbner basis, no extra Gröbner basis computation is needed for factoring a polynomial over this extension field. Nothing more than linear algebraic technique is used to get a characteristic polynomial of a generic linear map. Then this polynomial is factorized over the ground field. From its factors, the factorization of the polynomial over the extension field is obtained. The algorithm has been implemented in Magma and computer experiments indicate that it is very efficient, particularly for complicated examples.     

Sparse bivariate polynomial factorization

Motivated by Sasaki’s work on the extended Hensel construction for solving multivariate algebraic equations, we present a generalized Hensel lifting, which takes advantage of sparsity, for factoring bivariate polynomial over the rational number field. Another feature of the factorization algorithm presented in this article is a new recombination method, which can solve the extraneous factor problem before lifting based on numerical linear algebra. Both theoretical analysis and experimental data show that the algorithm is efficient, especially for sparse bivariate polynomials.     

Factoring multivariate polynomials via partial differential equations

A new method is presented for factorization of bivariate polynomials over any field of characteristic zero or of relatively large characteristic. It is based on a simple partial differential equation that gives a system of linear equations. As in Berlekamp's and Niederreiter's algorithms for factoring univariate polynomials, the dimension of the solution space of the linear system is equal to the number of absolutely irreducible factors of the polynomial to be factored, and any basis for the solution space gives a complete factorization by computing gcd's and by factoring univariate polynomials over the ground field. The new method finds absolute and rational factorizations simultaneously and is easy to implement for finite fields, local fields, number fields, and the complex number field. The theory of the new method allows an effective Hilbert irreducibility theorem, thus an efficient reduction of polynomials from multivariate to bivariate.

     

A lifting and recombination algorithm for rational factorization of sparse polynomials

We propose a new lifting and recombination scheme for rational bivariate polynomial factorization that takes advantage of the Newton polytope geometry. We obtain a deterministic algorithm that can be seen as a sparse version of an algorithm of Lecerf, with a polynomial complexity in the volume of the Newton polytope. We adopt a geometrical point of view, the main tool being derived from some algebraic osculation criterion in toric varieties.     

To solving problems of algebra for two-parameter matrices. I

This paper starts a series of publications devoted to surveying and developing methods for solving algebraic problems for two-parameter polynomial and rational matrices. The paper considers rank factorizations and, in particular, the relatively irreducible and ΔW-2 factorizations, which are used in solving spectral problems for two-parameter polynomial matrices F(λ, μ). Algorithms for computing these factorizations are suggested and applied to computing points of the regular, singular, and regular-singular spectra and the corresponding spectral vectors of F(λ, μ). The computation of spectrum points reduces to solving algebraic equations in one variable. A new method for computing spectral vectors for given spectrum points is suggested. Algorithms for computing critical points and for constructing a relatively free basis of the right null-space of F(λ, μ) are presented. Conditions sufficient for the existence of a free basis are established, and algorithms for checking them are provided. An algorithm for computing the zero-dimensional solutions of a system of nonlinear algebraic equations in two variables is presented. The spectral properties of the ΔW-2 method are studied. Bibliography: 4 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 359, 2008, pp. 107–149.     

Piecewise Rational Approximations of Real Algebraic Curves

1.IntroductionAnaJgebraicplanecurveCofdegreedinn2isimplicitlydefinedbyasinglepolynomialequationf(x,y)=Oofdegreedwithcoefficientsinn.Arationalalgebraiccurveofdegreedinn2canadditionaJlybedefinedbyrationalparametricequationswhicharegivenas(x=G1(u),y=G2(u)),whereG1andG2arerationalfunctionsinuofdegreed,i.e-,eachisaquotientofpolynomiaJ8inuofmtalmumdegreedwithcoefficientsinn.ffetionalcurvesaxeonlyasubsetofimplicitalgebraiccurvesofdegreed+1.Whi1eaJldegreetwocurves(conics)arerational,oIilyasubsetof…     

The Numerical Factorization of Polynomials

Polynomial factorization in conventional sense is an ill-posed problem due to its discontinuity with respect to coefficient perturbations, making it a challenge for numerical computation using empirical data. As a regularization, this paper formulates the notion of numerical factorization based on the geometry of polynomial spaces and the stratification of factorization manifolds. Furthermore, this paper establishes the existence, uniqueness, Lipschitz continuity, condition number, and convergence of the numerical factorization to the underlying exact factorization, leading to a robust and efficient algorithm with a MATLAB implementation capable of accurate polynomial factorizations using floating point arithmetic even if the coefficients are perturbed.     

Algorithms for finding the minimal polynomials and inverses of resultant matrices

In this paper, algorithms for computing the minimal polynomial and the common minimal polynomial of resultant matrices over any field are presented by means of the approach for the Gröbner basis of the ideal in the polynomial ring, respectively, and two algorithms for finding the inverses of such matrices are also presented. Finally, an algorithm for the inverse of partitioned matrix with resultant blocks over any field is given, which can be realized by CoCoA 4.0, an algebraic system over the field of rational numbers or the field of residue classes of modulo prime number. We get examples showing the effectiveness of the algorithms.     

Computing generalized inverses of a rational matrix and applications

In this paper we investigate symbolic implementation of two modifications of the Leverrier-Faddeev algorithm, which are applicable in computation of the Moore-Penrose and the Drazin inverse of rational matrices. We introduce an algorithm for computation of the Drazin inverse of rational matrices. This algorithm represents an extension of the papers [11] and [14]. and a continuation of the papers [15, 16]. The symbolic implementation of these algorithms in the package mathEmatica is developed. A few matrix equations are solved by means of the Drazin inverse and the Moore-Penrose inverse of rational matrices.