Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem

In this paper, we present several baby-step giant-step algorithms for the low hamming weight discrete logarithm problem. In this version of the discrete log problem, we are required to find a discrete logarithm in a finite group of order approximately , given that the unknown logarithm has a specified number of 1's, say , in its binary representation. Heiman and Odlyzko presented the first algorithms for this problem. Unpublished improvements by Coppersmith include a deterministic algorithm with complexity , and a Las Vegas algorithm with complexity

.

We perform an average-case analysis of Coppersmith's deterministic algorithm. The average-case complexity achieves only a constant factor speed-up over the worst-case. Therefore, we present a generalized version of Coppersmith's algorithm, utilizing a combinatorial set system that we call a splitting system. Using probabilistic methods, we prove a new existence result for these systems that yields a (nonuniform) deterministic algorithm with complexity . We also present some explicit constructions for splitting systems that make use of perfect hash families.

     

On the discrete logarithm problem for prime-field elliptic curves

In recent years several papers have appeared that investigate the classical discrete logarithm problem for elliptic curves by means of the multivariate polynomial approach based on the celebrated summation polynomials, introduced by Semaev in 2004. With a notable exception by Petit et al. in 2016, all numerous papers on the subject have investigated only the composite-field case, leaving apart the laborious prime-field case. In this paper we propose a variation of Semaev's original approach that reduces to only one the relations to be found among points of the factor base, thus decreasing drastically the necessary Groebner basis computations. Our proposal holds for any finite field but it is particularly suitable for the prime-field case, where it outperforms both the original Semaev's method and the specialised algorithm by Petit et al..     

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.     

Algorithm robust for the bicriteria discrete optimization problem

We apply Algorithm Robust to various problems in multiple objective discrete optimization. Algorithm Robust is a general procedure that is designed to solve bicriteria optimization problems. The algorithm performs a weight space search in which the weights are utilized in min-max type subproblems. In this paper, we experiment with Algorithm Robust on the bicriteria knapsack problem, the bicriteria assignment problem, and the bicriteria minimum cost network flow problem. We look at a heuristic variation that is based on controlling the weight space search and has an indirect control on the sample of efficient solutions generated. We then study another heuristic variation which generates samples of the efficient set with quality guarantees. We report results of computational experiments.     

Cauchy problem for integrable discrete equations on quad-graphs

Initial value problems for the integrable discrete equations on quad-graphs are investigated. We give a geometric criterion of when such a problem is well-posed. In the basic example of the discrete KdV equation an effective integration scheme based on the matrix factorization problem is proposed and the interaction of the solutions with the localized defects in the regular square lattice are discussed in details. The examples of kinks and solitons on various quad-graphs, including quasiperiodic tilings, are presented.Dedicated to S. P. Novikov on his 65 birthdayOn leave from Landau Institute for Theoretical Physics, Chernogolovka, Russia.     

Approximation algorithms for the stochastic priority facility location problem

In this article, we present a primal-dual 3-approximation algorithm for the stochastic priority facility location problem. Combined with greedy augmentation procedure, such performance factor is further improved to 1.8526.     

An ensemble of discrete differential evolution algorithms for solving the generalized traveling salesman problem

In this paper, an ensemble of discrete differential evolution algorithms with parallel populations is presented. In a single populated discrete differential evolution (DDE) algorithm, the destruction and construction (DC) procedure is employed to generate the mutant population whereas the trial population is obtained through a crossover operator. The performance of the DDE algorithm is substantially affected by the parameters of DC procedure as well as the choice of crossover operator. In order to enable the DDE algorithm to make use of different parameter values and crossover operators simultaneously, we propose an ensemble of DDE (eDDE) algorithms where each parameter set and crossover operator is assigned to one of the parallel populations. Each parallel parent population does not only compete with offspring population generated by its own population but also the offspring populations generated by all other parallel populations which use different parameter settings and crossover operators. As an application area, the well-known generalized traveling salesman problem (GTSP) is chosen, where the set of nodes is divided into clusters so that the objective is to find a tour with minimum cost passing through exactly one node from each cluster. The experimental results show that none of the single populated variants was effective in solving all the GTSP instances whereas the eDDE performed substantially better than the single populated variants on a set of problem instances. Furthermore, through the experimental analysis of results, the performance of the eDDE algorithm is also compared against the best performing algorithms from the literature. Ultimately, all of the best known averaged solutions for larger instances are further improved by the eDDE algorithm.     

A cooperative swarm intelligence algorithm for multi-objective discrete optimization with application to the knapsack problem

We propose a novel cooperative swarm intelligence algorithm to solve multi-objective discrete optimization problems (MODP). Our algorithm combines a firefly algorithm (FA) and a particle swarm optimization (PSO). Basically, we address three main points: the effect of FA and PSO cooperation on the exploration of the search space, the discretization of the two algorithms using a transfer function, and finally, the use of the epsilon dominance relation to manage the size of the external archive and to guarantee the convergence and the diversity of Pareto optimal solutions.We compared the results of our algorithm with the results of five well-known meta-heuristics on nine multi-objective knapsack problem benchmarks. The experiments show clearly the ability of our algorithm to provide a better spread of solutions with a better convergence behavior.     

Two algorithms for the Student-Project Allocation problem

We study the Student-Project Allocation problem (SPA), a generalisation of the classical Hospitals/Residents problem (HR). An instance of SPA involves a set of students, projects and lecturers. Each project is offered by a unique lecturer, and both projects and lecturers have capacity constraints. Students have preferences over projects, whilst lecturers have preferences over students. We present two optimal linear-time algorithms for allocating students to projects, subject to the preference and capacity constraints. In particular, each algorithm finds a stable matching of students to projects. Here, the concept of stability generalises the stability definition in the HR context. The stable matching produced by the first algorithm is simultaneously best-possible for all students, whilst the one produced by the second algorithm is simultaneously best-possible for all lecturers. We also prove some structural results concerning the set of stable matchings in a given instance of SPA. The SPA problem model that we consider is very general and has applications to a range of different contexts besides student-project allocation.     

Soliton solutions of an integrable boundary problem on the half-line for the discrete toda chain

We write formulas for soliton solutions of the discrete Toda chain and pose the integrable boundary value problem for this chain. We find conditions for the parameters (discrete spectrum points, transmission coefficients, and the corresponding factors) whereby solutions of the integrable boundary value problem are selected from all soliton solutions. As a result, we construct two hierarchies of soliton solutions of the specified problem with even and odd soliton numbers and find an explicit form of the conditions for the parameters. __________ Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 148, No. 3, pp. 387–397, September, 2006.     

Approximation algorithms for the test cover problem

In the test cover problem a set of m items is given together with a collection of subsets, called tests. A smallest subcollection of tests is to be selected such that for each pair of items there is a test in the selection that contains exactly one of the two items. It is known that the problem is NP-hard and that the greedy algorithm has a performance ratio O(log m). We observe that, unless P=NP, no polynomial-time algorithm can do essentially better. For the case that each test contains at most k items, we give an O(log k)-approximation algorithm. We pay special attention to the case that each test contains at most two items. A strong relation with a problem of packing paths in a graph is established, which implies that even this special case is NP-hard. We prove APX-hardness of both problems, derive performance guarantees for greedy algorithms, and discuss the performance of a series of local improvement heuristics. Partially supported by the Future and Emerging Technologies Programme of the EU under contract number IST-1999-14186 (ALCOM-FT).Partially supported by a Merck Computational Biology and Chemistry Program Graduate Fellowship from the Merck Company Foundation.Also Iceland Genomics CorporationPartially supported by subcontract No. 16082-RFP-00-2C in the area of ``Combinatorial Optimization in Biology (XAXE),' Los Alamos National Laboratories, and NSF grant CCR-0105548.Mathematics Subject Classification: 90B27     

Tilings,packings, coverings,and the approximation of functions

A packing (resp. covering) ? of a normed space X consisting of unit balls is called completely saturated (resp. completely reduced) if no finite set of its members can be replaced by a more numerous (resp. less numerous) set of unit balls of X without losing the packing property (resp. covering property) of ?. We show that a normed space X admits completely saturated packings with disjoint closed unit balls as well as completely reduced coverings with open unit balls, provided that there exists a tiling of X with unit balls. Completely reduced coverings by open balls are of interest in the context of an approximation theory for continuous real‐valued functions that rests on so‐called controllable coverings of compact metric spaces. The close relation between controllable coverings and completely reduced coverings allows an extension of the approximation theory to non‐compact spaces. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Rigorous Proof of the Waterloo Algorithm for the Discrete Logarithm Problem

In this paper we are concerned with the Waterloo variant of the index calculus method for the discrete logarithm problem in . We provide a rigorous proof for the heuristic arguments for the running time of the Waterloo algorithm. This implies in studying the behavior of pairs of coprime smooth polynomials over finite fields. Our proof involves a double saddle point method, and it is in nature similar to the one of Odlyzko for the rigorous analysis of the basic index calculus.     

一类无约束离散Minimax问题的区间调节熵算法

In this paper,a class of unconstrained discrete minimax problems is described,in which the objective functions are in C^1. The paper deals with this problem by means of taking the place of maximum-entropy function with adjustable entropy function. By constructing an interval extension of adjustable entropy function and some region deletion test rules, a new interval algorithm is presented. The relevant properties are proven, The minimax value and the localization of the minimax points of the problem can be obtained by this method. This method can overcome the flow problem in the maximum-entropy algorithm. Both theoretical and numerical results show that the method is reliable and efficient.     

Approximate algorithms for the travelling purchaser problem

In this paper we study the generalized savings heuristics of Golden, Levy and Dahl and propose several new heuristic procedures for solving the travelling purchaser problem. A comparative study of the four heuristics considered is provided.     

Helmholtz's inverse problem of the discrete calculus of variations

We derive the discrete version of the classical Helmholtz's condition. Precisely, we state a theorem characterizing second-order finite difference equations admitting a Lagrangian formulation. Moreover, in the affirmative case, we provide the class of all possible Lagrangian formulations.