基于二元Lagrange插值多项式的门限方案

针对基于一元Lagrange插值多项式的门限方案中存在的安全性不足及应用领域受限问题,通过研究现有的门限方案和实数域上的二元Lagrange插值理论,在有限域的基础上,提出一种基于二元Lagrange插值多项式的门限方案。给出了方案的构造及其数值算例,证明了方案的合理性和可行性。将该方案与基于一元Lagrange插值多项式的门限方案进行对比分析,表明新的方案中子秘密丢失所造成的损失更低、合谋难度更大,方案的安全性更高。同时,该方案可以拓宽门限方案的应用领域。     

The Longest Path Problem has a Polynomial Solution on Interval Graphs

The longest path problem is the problem of finding a path of maximum length in a graph. Polynomial solutions for this problem are known only for small classes of graphs, while it is NP-hard on general graphs, as it is a generalization of the Hamiltonian path problem. Motivated by the work of Uehara and Uno (Proc. of the 15th Annual International Symp. on Algorithms and Computation (ISAAC), LNCS, vol. 3341, pp. 871–883, 2004), where they left the longest path problem open for the class of interval graphs, in this paper we show that the problem can be solved in polynomial time on interval graphs. The proposed algorithm uses a dynamic programming approach and runs in O(n ⁴) time, where n is the number of vertices of the input graph.     

基于VB及MATLAB展开拉格朗日插值多项式

针对Lagrange插值多项式展开难的特点,给出了用VB的解决思路,完全用MATLAB展开的方案以及基于二者的混合编程方法。分析了三种方法的优缺点,指出了以COM组件为纽带的可行性,对高校软件实验室教学具有较实用的参考价值。     

基于Lagrange插值多项式的门限方案的实现

门限方案中,将秘密分割为若干份,需要多个秘密拥有者合作才能恢复秘密。可防止因一部分人原因而泄露秘密,使密钥的管理更加安全灵活。实现了一个基于Lagrange插值多项式的门限方案,包括秘密分割和秘密恢复两方面。并介绍了在基于DSP芯片的加密卡上的应用,实现密钥的管理,如卡内关键数据的备份、恢复等重要操作。     

An Interval Linear Tolerance Problem

This paper is concerned with a tolerance problem for an interval linear system A x = b requiring inner estimation of the admissible solution set {x ⁿ | (A A)(Ax b)} formed by vectors x for which the product Ax remains within b for any possible A A. Methods for verifying the emptiness and nonemptiness of admissible solution sets are developed. Formulas for the dimensions of the interval solution of a tolerance problem with known center are derived.     

Interval Partitions and Polynomial Factorization

The fastest algorithms for factoring a univariate polynomial f of degree n over a finite field use a baby-step/giant-step approach. The set {1,…,n} of potential factor degrees is partitioned into intervals. In a first stage, for each interval the product of all irreducible factors with degree in the interval is determined, generalizing the method of Cantor & Zassenhaus. In a second stage, each polynomial corresponding to a multi-factor interval—containing two or more irreducible factors—is completely factored. The goal in this work is to analyze the behavior of this algorithm on uniformly random squarefree input polynomials, for various partitions. To this end, we study several parameters such as the expected number of multi-factor intervals, the expected number of irreducible factors with degrees lying in multi-factor intervals, the number of gcds executed in the factoring process, the expected total degree among the irreducible factors with degrees in multi-factor intervals, and the probability of a polynomial to have no multi-factor interval. We concentrate on partitions with polynomially growing interval sizes, and determine the partition that minimizes the expected number of gcds.     

Polynomial Solution to Stabilization Problem for Multivariable Sampled-Data Systems

In polynomial form, necessary and sufficient conditions are given that provide for existence of a discrete controller stabilizing a multivariable sampled-data system.     

基于插值的Bernstein多项式复合及其曲线曲面应用

在曲线曲面造型中,Bernstein多项式复合被广泛用于许多几何操作,因而具有重要的理论和实际意义.基于多项式插值和符号计算的思想,研究了Bernstein多项式函数复合问题, 并将其应用于曲线曲面的情形.与两种已有方法相比,新方法具有速度快、易于编程实现、占用存储空间少的特点,但数值精度低于基于广义de Casteljau算法的多项式复合结果.     

A Collusion Problem and Its Solution

Consider a group of colluders, each with certain knowledge such as the identity of some other colluders, some cryptographic keys, and some data, possibly multiply encrypted. Two colluders can combine their knowledge if their current knowledge satisfies certain conditions. Their cryptographic keys can help decrypt each other's encrypted data, expanding their knowledge and revealing more collusion opportunities, and the process of collusion continues. The question we address is whether it is possible for the colluders to uncover a target set of unencrypted data. In this paper we formulate the collusion problem and provide an algorithm that determines whether a collusion problem has a solution and, if so, computes one. A solution is a specific way by which the colluders can uncover the hidden information. The solution generated by our algorithm is generally not one that involves the minimum number of colluders. We show, however, that to find such a solution is NP-complete. Complex communications protocols employing cryptographic building blocks are being developed to transfer information among some users and hide from others. The algorithm presented here can be applied to determine whether and how a subset of protocol users can discover during or after the protocol's execution the information that is to be hidden from them.     

Hermite-Shannon-Cosine区间小波及其在图形自适应分划插值中的应用

动态曲线图是描述客观现象变换规律的常用工具,为实现动态曲线特征点的动态捕捉及精确表达,构造了同时具有插值性、光滑性、紧支撑性和对称性的Shannon-Cosine小波函数.首先利用Shannon小波函数的波动性和连续性,根据积分中值定理,设计了一种参数化的窗函数,通过参数调整,可满足Shannon-Cosine小波对支撑区间和光滑度的自适应控制的要求;其次,分析确定了对曲线进行小波变换时边界效应归因于曲线边界的不连续,因此,采用2点3次Hermite插值函数构建了区间小波;最后,采用多尺度Shannon-Cosine小波对冲击波传播曲线和反射Burger曲线进行多尺度自适应细分和逼近,自动捕捉曲线的特征点进行重构.实例结果表明,与其他方法相比,Hermite Shannon-Cosine区间小波逼近曲线具有较高的数值精度和较低的算法复杂度.     

基于三次拉格朗日插值的自适应图像缩放

传统的插值算法由于低通滤波效应通常会使目标图像边缘模糊,难以得到满意的视觉效果.为了取得较好的图像缩放质量,提出一种基于三次拉格朗日插值的自适应图像缩放算法.该算法首先计算目标像素点周围三组源像素点的方差,选取方差最小的一组源像素点,然后采用三次拉格朗日插值公式求得目标像素点的灰度值.实验结果表明,本文算法所得的目标图像边缘清晰,且算法复杂度较低,便于硬件实现,可以实现实时图像缩放.     

Implicitization of Parametric Curves via Lagrange Interpolation

A simple algorithm for finding the implicit equation of a parametric plane curve given by its parametric equations is presented. The algorithm is based on an efficient computation of the Bézout resultant and Lagrange interpolation. One of main features of our approach is the fact that it considerably reduces the problem of computing intermediate expressions.     

Sendmail的安全问题与解决方案

Semdmail是业内公认的电子邮件服务系统程序.本文分析了目前Sendmail的安全问题,解剖了Sendmail所提供的安全特性,并提供了一些额外的解决方案,以达到加强电子邮件系统安全的目的.     

局部形状可调的三角多项式插值曲线

对于给定的有序插值点列,给出了构造一类三角多项式插值曲线的方法。三角多项式曲线的控制点直接由插值点列计算产生,避免了求解方程组。所构造的插值曲线可作局部形状修改且具有G2m-1连续性。     

一种基于拉格朗日多项式的网格RBAC设计

在网格RBAC存取控制机制方面,本文利用Lagrange多项式建立RBAC的存取控制机制,通过Lagrange多项式的将使用者在每部服务器上所担任角色的角色值隐藏在一条Lagrange多项式中,从而简化了RBAC在使用者角色的管理以及减少需要大量表格储存空间的需求,并且Lagrange多项式计算简单.此外角色的权限管理分散到各个服务器,由服务器自己管理在该服务器上所属角色的存取权限,提高了它们权限管理的弹性.     

Sharp Bounds on Interval Polynomial Roots

An algorithm is developed for computing sharp bounds on the real roots of polynomials with interval coefficients. The procedure is introduced by studying interval quadratic equations.     

图像仿射变换的双二次Lagrange插值算法

构造了图像仿射变换的双二次Lagrange插值算法。与双立方插值算法相比,这种算法有效降低了计算量,是一种比较理想的图像插值算法。     

改进型的拉格朗日插值在视频分割处理的实现

视频分割技术常用于大显示屏的场合,分割技术的好坏决定着视频显示的清晰程度。采用三次拉格朗日插值算法,以改善视频分割处理时图片失真问题,提出改进算法,即重心拉格朗日插值法,用硬件描述语言VHDL来实现算法并进行软件仿真。     

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

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

Numerical Curve Length Calculation Using Polynomial Interpolation

In this paper we present a method and algorithm for computing curve length approximately using a fixed rule resulting from polynomial interpolation of the points on the curve. The method can applied efficiently calculating digital curves by considering the control points of the interpolation as the pixels centers points. In the paper several examples are presented and the calculated lengths are compared to other methods found in the literature and we have shown progress. We provided MATLAB^® code to simulate the algorithm. The advantage of the proposed method is in the approximation of the digital curve with the continuous curve rather than with piecewise linear sections used by most other methods.