A shorter proof for an explicit formula for discrete logarithms in finite fields

A shorter proof for an explicit formula for discrete logarithms in finite fields is given.     

A bound-improving approach to discrete programming problems

This note deals with the extension of the bound-improving sequence idea to general discrete programming problems.Corresponding author.     

A hybrid approach to discrete mathematical programming

The dynamic programming and branch-and-bound approaches are combined to produce a hybrid algorithm for separable discrete mathematical programs. Linear programming is used in a novel way to compute bounds. Every simplex pivot permits a bounding test to be made on every active node in the search tree. Computational experience is reported.     

Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem

Recently, the first author introduced some cryptographic functions closely related to the Diffie-Hellman problem called P-Diffie-Hellman functions. We show that the existence of a low-degree polynomial representing a P-Diffie-Hellman function on a large set would lead to an efficient algorithm for solving the Diffie-Hellman problem. Motivated by this result we prove lower bounds on the degree of such interpolation polynomials. Analogously, we introduce a class of functions related to the discrete logarithm and show similar reduction and interpolation results.     

Security of meta-He digital signature scheme based on factoring and discrete logarithms

To enhance the security of signature schemes, Pon et al., recently, investigated all eight variants of the He’s digital signature scheme. The security of the proposed schemes is based on the difficulties of simultaneously solving the factoring and discrete logarithm problems with almost the same sizes of arithmetic modulus. This paper shows that the all eight variants of the He’s digital signature scheme, as well as two more variants, are not secure if attackers can solve discrete logarithm problems. Moreover, the attackers can easily forge signatures of the most optimal signature schemes of the generalized He’ signature schemes even though they can solve neither discrete logarithm problems nor factoring.     

A new discrete mechanics approach to swing-up control of the cart-pendulum system

This paper develops a new swing-up control method for the cart-pendulum system via discrete mechanics. The swing-up control law consists of two parts: the swing-up stage and the stabilization one. In the swing-up stage, we use a controller based on a discrete Lyapunov function and it can swing up the pendulum. Then, in the stabilization stage, we utilize a stabilizing controller based on the linearized system and discrete-time optimal regulator theory. In addition, transformation methods from discrete control inputs into continuous zero-order hold inputs are introduced. From some simulation results, we can confirm that the cart-pendulum system is swung up and stabilized by our new method.     

A determinantal approach to Appell polynomials

A new definition by means of a determinantal form for Appell (1880) [1] polynomials is given. General properties, some of them new, are proved by using elementary linear algebra tools. Finally classic and non-classic examples are considered and the coefficients, calculated by an ad hoc Mathematica code, for particular sequences of Appell polynomials are given.     

A critical review of discrete filled function methods in solving nonlinear discrete optimization problems

Many real life problems can be modeled as nonlinear discrete optimization problems. Such problems often have multiple local minima and thus require global optimization methods. Due to high complexity of these problems, heuristic based global optimization techniques are usually required when solving large scale discrete optimization or mixed discrete optimization problems. One of the more recent global optimization tools is known as the discrete filled function method. Nine variations of the discrete filled function method in literature are identified and a review on theoretical properties of each method is given. Some of the most promising filled functions are tested on various benchmark problems. Numerical results are given for comparison.     

A technique to study the correlation measures of binary sequences

Let E^N=(e₁,e₂,…,e_N) be a binary sequence with e_i∈{+1,−1}. For 2≤k≤N, the correlation measure of order k of the sequence is defined by Mauduit and Sárközy as

     

A characterization of discrete unimodality with applications to variance upper bounds

Bertin and Theodorescu (1984,Statist. Probab. Lett.,2, 23–30) developed a characterization of discrete unimodality based on convexity properties of a discretization of distribution functions. We offer a new characterization of discrete unimodality based on convexity properties of a piecewise linear extension of distribution functions. This reliance on functional convexity, as in Khintchine's classic definition, leads to variance dilations and upper bounds on variance for a large class of discrete unimodal distributions. These bounds are compared to existing inequalities due to Muilwijk (1966,Sankhy, Ser. B,28, p. 183), Moors and Muilwijk (1971,Sankhy, Ser. B,33, 385–388), and Rayner (1975,Sankhy, Ser. B,37, 135–138), and are found to be generally tighter, thus illustrating the power of unimodality assumptions.     

A finite sequence of Hahn-type discrete orthogonal polynomials

ABSTRACT

By considering a specific Sturm–Liouville problem, we introduce a finite sequence of Hahn-type discrete polynomials and prove that they are finitely orthogonal on the real line. We then compute their norm square value by using Dougall's bilateral sum and obtain all moments corresponding to the introduced polynomials.     

Solving the Multi-discrete Logarithm Problems over a Group of Elliptic Curves with Prime Order

In this paper, we discuss the expected number of steps in solving multi-discrete logarithm problems over a group of elliptic curves with prime order by using Pollard＇s rho method and parallel collision search algorithm. We prove that when using these algorithms to compute discrete logarithms, the knowledge gained through computing many logarithms does not make it easier for finding other logarithms. Hence in an elliptic cryptosystem, it is safe for many users to share the same curve, with different private keys.     

A unifying approach to the regularization of Fourier polynomials

In a previous paper [4] the following problem was considered:find, in the class of Fourier polynomials of degree n, the one which minimizes the functional: (0.1) $$J^* [F_n ,\sigma ] = \left\| {f - F_n } \right\|^2 + \sum\limits_{r = 1}^\infty {\frac{{\sigma ^r }}{{r!}}} \left\| {F_n^{(r)} } \right\|^2$$ , where ∥·∥ is theL ² norm,F _n ^(r) is therth derivative of the Fourier polynomialF _n (x), andf(x) is a given function with Fourier coefficientsc _k . It was proved that the optimal polynomial has coefficientsc _k ^* given by (0.2) $$c_k^* = c_k e^{ - \sigma k^2 } ; k = 0, \pm ,..., \pm n$$ . In this paper we consider the more general functional (0.3) $$\hat J[F_n ,\sigma _r ] = \left\| {f - F_n } \right\|^2 + \sum\limits_{r = 1}^\infty {\sigma _r \left\| {F_n^{(r)} } \right\|^2 }$$ , which reduces to (0.1) forσ _r =σ ^r /r!. We will prove that the classical sigma-factor method for the regularization of Fourier polynomials may be obtained by minimizing the functional (0.3) for a particular choice of the weightsσ _r . This result will be used to propose a motivated numerical choice of the parameterσ in (0.1).     

A discrete approach to the concept of derivative

The concept of derivative is a basic concept of calculus. It is closely related to the concept of function, the idea of rate of change, and the limit concept. In recent decades, teaching the concept of derivative in mathematics classrooms has changed: a quite formal approach—closely linked to the teaching of calculus at university and based on the sequence concept—has been transformed to or substituted by a new one. This means working with rates of change, an intuitive access to the concepts of limit and derivative. It includes working with real functions right from the beginning, a great emphasis on graphs, and the use of digital technologies. The meaning of sequences has decreased to a point where they are sometimes no longer even taught in the calculus course. In recent years this concept has been criticized for not developing adequate perceptions of the basic concepts of calculus and not sufficiently preparing the students for scientific courses at university. In this paper we present an alternative discrete step-by-step approach to the basic concepts of calculus by working with sequences and difference sequences, functions defined on \( \mathbb{Z}\) and discrete domains of \( \mathbb{Q}\) , and by subsequently developing the concept of rate of change in a discrete learning environment. The paper is based on general theoretical considerations and empirical investigations by the author and is meant as a contribution to classroom design-research or “design science” (Wittmann, Educ Stud Math 29(4):355–374, 1995).     

A groupoid approach to discrete inverse semigroup algebras

Let K be a commutative ring with unit and S an inverse semigroup. We show that the semigroup algebra KS can be described as a convolution algebra of functions on the universal étale groupoid associated to S by Paterson. This result is a simultaneous generalization of the author's earlier work on finite inverse semigroups and Paterson's theorem for the universal C^∗-algebra. It provides a convenient topological framework for understanding the structure of KS, including the center and when it has a unit. In this theory, the role of Gelfand duality is replaced by Stone duality.Using this approach we construct the finite dimensional irreducible representations of an inverse semigroup over an arbitrary field as induced representations from associated groups, generalizing the case of an inverse semigroup with finitely many idempotents. More generally, we describe the irreducible representations of an inverse semigroup S that can be induced from associated groups as precisely those satisfying a certain “finiteness condition.” This “finiteness condition” is satisfied, for instance, by all representations of an inverse semigroup whose image contains a primitive idempotent.     

A generic approach to proving NP-hardness of partition type problems

This note presents a generic approach to proving NP-hardness of unconstrained partition type problems, namely partitioning a given set of entities into several subsets such that a certain objective function of the partition is optimized. The idea is to represent the objective function of the problem as a function of aggregate variables, whose optimum is achieved only at the points where problem Partition (if proving ordinary NP-hardness), or problem 3-Partition or Product Partition (if proving strong NP-hardness) has a solution. The approach is demonstrated on a number of discrete optimization and scheduling problems.     

A variational approach to norm attainment of some operators and polynomials

If X is an Asplund space, then every uniformly continuous function on Bx＊ which is holomorphic on the open unit ball, can be perturbed by a w＊ continuous and homogeneous polynomial on X＊ to obtain a norm attaining function on the dual unit ball. This is a consequence of a version of Bourgain-Stegall＇s variational principle. We also show that the set of N-homogeneous polynomials between two Banach spaces X and Y whose transposes attain their norms is dense in the corresponding space of N-homogeneous polynomials. In the case when Y is the space of Radon measures on a compact K, this result can be strengthened.     

一种基于后验概率判决的one-by-one快速相关攻击算法(英文)

本文描述了一种基于后验概率判决的 one by one快速相关攻击算法.本文试图通过概率的观点来看待和分析快速相关攻击问题.该算法的优点有以下三点.首先,和文献[5]相比 one by one算法减少了对存储空间的需求.其次,提出了攻击失败概率的概念,并利用中心极限定理给出了它和密钥流序列长度的关系.最后,和文献[4]相比,该算法只需要更少的密钥流序列就可以达到几乎相同的攻击效果.     

A discrete Newton algorithm for minimizing a function of many variables

A Newton-like method is presented for minimizing a function ofn variables. It uses only function and gradient values and is a variant of the discrete Newton algorithm. This variant requires fewer operations than the standard method whenn > 39, and storage is proportional ton rather thann ².