Polynomial Interpolation of the Discrete Logarithm

Recently, Coppersmith and Shparlinski proved several results on the interpolation of the discrete logarithm in the finite prime field by polynomials modulo p and modulo p-1, respectively. In this paper most of these results are extended to arbitrary .     

The Xedni Calculus and the Elliptic Curve Discrete Logarithm Problem

Let be an elliptic curve defined over a finite field, and let be two points on E. The Elliptic Curve Discrete Logarithm Problem (ECDLP) asks that an integer m be found so that S=mT in . In this note we give a new algorithm, termed the Xedni Calculus, which might be used to solve the ECDLP. As remarked by Neal Koblitz, the Xedni method is also applicable to the classical discrete logarithm problem for and to the integer factorization problem.     

The index calculus method using non-smooth polynomials

We study a generalized version of the index calculus method for the discrete logarithm problem in , when , is a small prime and . The database consists of the logarithms of all irreducible polynomials of degree between given bounds; the original version of the algorithm uses lower bound equal to one. We show theoretically that the algorithm has the same asymptotic running time as the original version. The analysis shows that the best upper limit for the interval coincides with the one for the original version. The lower limit for the interval remains a free variable of the process. We provide experimental results that indicate practical values for that bound. We also give heuristic arguments for the running time of the Waterloo variant and of the Coppersmith method with our generalized database.

     

Discrete Logarithm Based Cryptosystems in Quadratic Function Fields of Characteristic 2

We present a key exchange scheme similar to that of Diffie and Hellman using the infrastructure of quadratic function fields of even characteristic. This is a modification of the results of Scheidler, Stein and Williams who used quadratic function fields of odd characteristic. We also extend these results to give a digital signature scheme similar to that of ElGamal. These schemes are possible in this structure even though it is not a group. Finally we examine the security of such systems, and give a possible attack based on Pohlig and Hellman's attack on discrete logarithms in finite groups.     

Linear Complexity of the Discrete Logarithm

We obtain new lower bounds on the linear complexity of several consecutive values of the discrete logarithm modulo a prime p. These bounds generalize and improve several previous results.     

A General Polynomial Sieve

An important component of the index calculus methods for finding discrete logarithms is the acquisition of smooth polynomial relations. Gordon and McCurley (1992) developed a sieve to aid in finding smooth Coppersmith polynomials for use in the index calculus method. We discuss their approach and some of the difficulties they found with their sieve. We present a new sieving method that can be applied to any affine subspace of polynomials over a finite field.     

求解车辆路径问题的离散蝙蝠算法

根据车辆路径问题的数学模型,分析了它的具体特征,从而对BA的操作算子又进行了重新定义,设计了求解VRP问题的离散蝙蝠算法,并通过实例测试将离散蝙蝠算法与其他算法进行比较,验证了该算法求解VRP问题的有效性与可行性.     

New results on quasi-subfield polynomials

Quasi-subfield polynomials were introduced by Huang et al. together with a new algorithm to solve the Elliptic Curve Discrete Logarithm Problem (ECDLP) over finite fields of small characteristic. In this paper we provide both new quasi-subfield polynomial families and a new theorem limiting their existence. Our results do not allow to derive any speedup for the new ECDLP algorithm compared to previous approaches.     

Mean-Square Filtering Problem for Discrete Volterra Equations

Abstract

The mean-square filtering problem for the discrete Volterra equations is a nontrivial task due to an enormous amount of operations required for the implementation of optimal filter. A difference equation of a moderate dimension is chosen as an approximate model for the original system. Then the reduced Kalman filter can be used as an approximate but efficient estimator. Using the duality theory of convex variational problems, a level of nonoptimality for the chosen filter is obtained. This level can be efficiently computed without exactly solving the full filtering problem.     

约束非线性l_1问题的光滑近似算法

针对约束非线性l_1问题不可微的特点,提出了一种光滑近似算法.该方法利用" "函数的光滑近似函数和罚函数技术将非线性l_1问题转化为无约束可微问题,并在适当的假设下,该算法是全局收敛的.初步的数值试验表明算法的有效性.     

A Semi-Conjugate Matrix Boundary Value Problem for General Orthogonal Polynomials on an Arbitrary Smooth Jordan Curve

In this article, the author characterizes orthogonal polynomials on an arbitrary smooth Jordan curve by a semi-conjugate matrix boundary value problem, which is different from the Riemann-Hilbert problems that appear in the theory of Riemann -Hilbert approach to asymptotic analysis for orthogonal polynomials on a real interval introduced by Fokas, Its, and Kitaev and on the unit circle introduced by Baik, Deift, and Johansson. The author hopes that their characterization may be applied to asymptotic analysis for general orthogonal polynomials by combining with a new extension of steepest descent method which we are looking for.     

Filtering Problem for Discrete Volterra Equations with Combined Disturbances

Abstract

A minimax filtering problem for discrete Volterra equations with combined noise models is considered. The combined models are defined as the sums of uncertain bounded deterministic functions and stochastic white noises. However, the corresponding variational problem turns out to be very difficult for direct solution. Therefore, simplified filtering algorithms are developed. The levels of nonoptimality for these simplified algorithms are introduced as the ratios of the filtering performances for the simplified and optimal estimators.

In opposite to the original variational problem, these levels can be easily evaluated numerically. Thus, simple filtering algorithms with guaranteed performance are obtained. Numerical experiments confirm the efficiency of our approach.     

Message Recovery for Signature Schemes Based on the Discrete Logarithm Problem

The new signature scheme presented by the authors in [13] is the first signature scheme based on the discrete logarithm problem that gives message recovery. The purpose of this paper is to show that the message recovery feature is independent of the choice of the signature equation and that all ElGamal-type schemes have variants giving message recovery. For each of the six basic ElGamal-type signature equations five variants are presented with different properties regarding message recovery, length of commitment and strong equivalence. Moreover, the six basic signature schemes have different properties regarding security and implementation. It turns out that the scheme proposed in [13] is the only inversionless scheme whereas the message recovery variant of the DSA requires computing of inverses in both generation and verification of signatures. In general, message recovery variants can be given for ElGamal-type signature schemes over any group with large cyclic subgroup as the multiplicative group of GF(2n) or elliptic curve over a finite field.The present paper also shows how to integrate the DLP-based message recovery schemes with secret session key establishment and ElGamal encryption. In particular, it is shown that with DLP-based schemes the same functionality as with RSA can be obtained. However, the schemes are not as elegant as RSA in the sense that the signature (verification) function cannot at the same time be used as the decipherment (encipherment) function.     

Generalized Convolution for the Discrete Jacobi Transformation

We study the translation and the convolution associated to the discrete Jacobi transformation on complex sequences of slow and rapid growth. Also we establish new topological properties for these spaces of sequences. This revised version was published online in June 2006 with corrections to the Cover Date.     

一类高维重特征方程Goursat的问题中的离散现象

§1 引言人们对具体实的重特征方程的了解还很不充分。,B,B首先举例指出重特征方程在解的光滑性问题中有所谓离散现象,即方程中的参数取一些离散的值时,解突然失去了光滑性。之后,Treves,F又给出一个例子,发现这种离散也出现在Cauchy问题解的唯一性问题中。王光寅等,陆柱家又进一步研究了较Treves,F.例子广泛的一类方程,指出Cauchy问题和Goursat问题的存在性中都有所谓离散现象。为了进一步揭示重     

加权U—统计量的一个重对数律

证明了关于独立同分布随机变量序列的加权Ｕ－统计量的一个重对数律,类似于献「３」证明了一个加权Ｕ－统计量的解耦不等式。     

离散变量结构优化设计的组合算法*

本文首先给出了离散变量优化设计局部最优解的定义,然后提出了一种综合的组合算法.该算法采用分级优化的方法,第一级优化首先采用计算效率很高且经过随机抽样性能实验表明性能较高的启发式算法─—相对差商法,求解离散变量结构优化设计问题近似最优解 X ;第二级采用组合算法,在 X 的离散邻集内建立离散变量结构优化设计问题的(-1,0.1)规划模型,再进一步将其化为(0,1)规划模型,应用定界组合算法或相对差商法求解该(0,1)规划模型,求得局部最优解.解决了采用启发式算法无法判断近似最优解是否为局部最优解这一长期未得到解决的问题,提高了计算精度,同时,由于相对差商法的高效率与高精度,以上综合的组合算法的计算效率也还是较高的.     

离散模糊需求报童问题的可能性模型研究

基于可能性分布函数质心特征值,本文建立了确定离散模糊需求报童问题订货量的利润模型,并分析了成本模型和利润模型的关系。研究结果表明:1)基于可能性分布函数质心的模糊可能性成本和利润模型确定的订货量不一致;2)对应不同订货量,模糊可能性成本与利润之和不为固定常数。数值计算表明:该方法不可取。     

F2^n上4次正形置换多项式的形式与计数

分组峦码是现代密码学中一个重要的研究分支,而置换理论在分组密码中有重要的地位．199j年,美国Tcledyne电子技术公司的Lothrop Mittenthal博士提出了一种置换,即正形置换．止形置换是一类完全映射,完全映射是由Mann在1942年研究正交拉丁方的构造时引入的,其具有良好的密码学性质（良好的扩散性和完令平衡性）,因此,正形置换常用来构造密码系统的算法,研究正形置换也就非常订必要．本文根据文章[1]的方法讨论了F2^n（n=4,5）上的4次正形置换多项式的形式与计数,至于n〉5的情形我们将在以后的篇章中继续讨论．