一个Z[X]上多项式泰勒展开算法

文[1]、[2]中分别研究了计算机代数中的两类重要问题,即z[x]上多项式因式分解问题和求有理函数不定积分问题。这里我们将研究另一类重要问题——z[x]上多项式泰勒展开问题。这一问题的现有算法的计算复杂性是0((n1log~2)_2n),[3],而我们这里给出的算法,其计算复杂性是0(n),因此该算法提高了运算速度。     

多项式时间复杂度的可计算实数域

近来,联系于著名的P与NP问题,开展了对构造分析(递归分析或可计算分析)的计算复杂性研究(见文献[1]、[2])。本文在Aberth的程序设计系统的计算模型里给出了两个可计算实数子类:多项式时间复杂度确定型可计算实数类PR与多项式时间复杂度非确定型可计算实数类NPR,证明了它们都是实数域与Rice可计算实数域的真子域。我们在该程序设计系统中引入了Oracle(神喻)集变元、Oracle函数变元以及随机变元,使用了Oracle指令与随机指令,从而建立了相对化的多项式时间复杂度可计     

指数、代数混合插值样条和它的变分性质

多项式样条的变分性质已有讨论(见[1]、[2]、[3]、[5]).在[6]中已讨论了指数、代数混合插值样条,本文推广了多项式样条的变分性质,得出了两种不同的变分问题,由此获得了对应于这两种变分问题的几种指数、代数混合插值样条。     

多元整系数多项式因式分解（Ⅱ）——关于时间复杂度算法的讨论

多元整系数多项式因式分解（Ⅱ）——关于时间复杂度算法的讨论余新国黄文奇赖楚生（计算机科学与工程系）摘要给出了多项式时间复杂度算法的证明．并进一步分析得到了整个算法的一个多项式时间复杂度的上界．这是多元整系数多项式的因式分解算法的多项式时间复杂度的上界...     

多项式零点模的界限的确定

设1≤P≤n-1,n≥2,则多项式P(z)的零点都在闭圆域 |z|≤1 ξA_p上,ξ是由b_j确定的最佳数。还给出了确定多项式零点模的界限的几个定理。本文拓广了翁祖荫[1]以及Brham Datt和N.K.Covil[2]的结果,并对[1]和[2]及A.Joyal,G.Labelle与Q.I.Rahman[3]中所给的多项式的零点模的下界及上界作了改进。     

关于自然数乘法分拆数的一个猜想

本文讨论了自然数n的乘法分拆数f(n)的上界,证明了[1]中的猜想成立。     

非负矩阵的Hadamard积谱半径上界的估计

非负矩阵是一类特殊矩阵,广泛地应用于数值计算、图论、线性规划、计算机科学、自动控制等领域。两个非负矩阵的Hadamard积的谱半径问题是非负矩阵理论中一个重要问题。关于两个非负矩阵的Hadamard积A°B,我们给出A°B谱半径的新上界,这一上界改进了文献[1]、文献[2]和文献[3]中的结果。     

多项式乘除运算的简捷计算方法

讨论了代数多项式运算中多项式乘法与多项式除法的公式化计算问题,给出了多项式乘法的简捷系数计算方法,以及多项式除法中商函数与余函数的计算方法.     

一类具有全局中心的可积非Hamilton系统的Abel积分

文章讨论了一类具有全局中心的可积非Hamilton系统在n次多项式扰动下的系统的Abel积分零点个数估计问题，我们将利用格林公式，通过计算二重积分来计算Abel积分，最后得到的结论是：该系统的Abel积分的零点个数的上界为2[n 1/2]。     

多项式乘法在量子统计中的应用

本文简要介绍了多项式的乘法,总结了多项式乘法的一般步聚,用多项式乘法计算了量子统计中有代表性的多项式gn(z)的除法与维里展开系数.     

关于Strassen矩阵乘法的探讨

本文从两个线性多项式乘积的一般形式出发,讨论用7次乘法求两个2×2矩阵乘积问题,给出了一套在图形上寻找7次乘法的技巧。利用这套技巧,很容易找到64种用7次乘法和18次加、减法求两个2×2矩阵乘积的方法。本文结果突破了文献[1]认为“正好有36种方法”的论断。     

基于NAFw的二进制域乘法算法

椭圆曲线上的乘法运算速度是提高椭圆曲线加密(ECC)性能的一个关键;分析了宽度w的非相邻表示型(NAF)算法和多项式乘法算法,提出了一个基于NAFw的二进制域乘法算法;算法减少了运算中的异或运算次数和预计算个数,缩短了运算时间且节省了存储空间;经建模仿真,结果表明本算法运算效率较comb多项式乘法平均快14.7%左右,预计算只需要计算2w-1-1个,从存储预计算个数和时间消耗综合考虑w=4也是较优的窗口宽度选择。     

任意域上多项式的几个性质

给出了特征为零的域上两个多项式的某线性组合无重因式的几个特征性质,给出了由这两个多项式线性组合生成的多项式有重因式的个数的一个上界.这个上界小于已有文献的结果,在某些方面有较大的改进.     

互运问题解法的进一步改进与推广

本文根椐定理2,在对[1]中的算法改连的基础上,给出了变量有上界的互运问题的解法,与[1]中的算法相比,该方法同样具有计算量小,逻辑结构简单和容易用计算机实现等优点。     

一种并行的有限域乘法器结构

提出了一种并行的有限域GF(2^m)乘法器结构．有限域乘法由多项式乘法和模不可约多项式f(x)两步实现．把多项式被乘数和乘数各自平分成3个子多项式,多项式乘法由子多项式的乘法和加法实现．当多项式的度m=500时,与传统的Mastrivito多项式乘法相比,所提出的多项式乘法结构可以减少33．1％的异或门,减少33．3％的与门．为了简化,采用特殊不可约多项式来产生有限域,此有限域乘法器结构适合高安全度的椭圆曲线密码算法的VLSI设计．     

关于Hermite—Fejèr插值多项式的一个渐近估计式

设f(x)∈C[-1,1],R_n[f(t);x]为具有第二类Chebyshev零点的Hermite—Fejer 插值多项式,则对一切x∈(-1,1),有如下估计式成立: 关于以第二类多项式U_n(x)的零点作为结点的Hermite—Fejer插值多项式对C[-1,1]类函数的渐近估计问题,已有不少人相继作了许多有价值的研究,其主要结果已综述在文[3]中。最近,王仁宏同本文的作者之一共同证得,当f′(x)∈Lipα(0<α<     

具有非常数上界的多项式

本文,讨论了在[-1,1]上以e~x为上界的多项式,并改进了开波曼和劳伦兹的结果。     

实现乘法计算的增广PETRI网模型

本文提出一个能实现乘法准确运算的增广Petri网模型。同[1]比较,本文所用的模拟工具(增广Petri网)比[1]所用的(普通Petri网)模拟能力要强一些,因而模型的性能(实现乘法准确计算)也比[1]所提出的模型的性能(只能实现乘法弱计算)好。     

考虑节点与边失效的网络全端可靠性上界拓展算法

拓展了Jan R H的网络全端可靠性上界。根据网络失效类型(节点自身失效与边失效造成节点孤立的两类网络系统失效状态),给出了节点与边均不可靠的网络系统全端可靠性上界的计算方法。在多项式时间内,该上界计算精度较以往的一个上界算法有显著提高。该上界适用于交通网络、ER随机网络、BA无标度网络等不同网络结构的可靠性评价与可靠性设计。     

Fp上不可约与本原多项式的高效确定算法

对于一大类整数n(n为素数乘于素数或1的积),分别给出有限域Fp上n次多项式是不可约多项式与本原多项式的一个充要条件,该条件可通过O(n3)次Fp上乘法加以验证,易于硬件实现.提出可约多项式一个充分条件,借此减少验证时间,并得到用O(n4)次Fp上乘法确定一个n次不可约多项式及一个n次本原多项式的高效算法.对于ECC中构造Fnp上椭圆曲线、序列密码中构造LFSR,有重要的应用价值.