Bounded knapsack sharing

A bounded knapsack sharing problem is a maximin or minimax mathematical programming problem with one or more linear inequality constraints, an objective function composed of single variable continuous functions called tradeoff functions, and lower and upper bounds on the variables. A single constraint problem which can have negative or positive constraint coefficients and any type of continuous tradeoff functions (including multi-modal, multiple-valued and staircase functions) is considered first. Limiting conditions where the optimal value of a variable may be plus or minus infinity are explicitly considered. A preprocessor procedure to transform any single constraint problem to a finite form problem (an optimal feasible solution exists with finite variable values) is developed. Optimality conditions and three algorithms are then developed for the finite form problem. For piecewise linear tradeoff functions, the preprocessor and algorithms are polynomially bounded. The preprocessor is then modified to handle bounded knapsack sharing problems with multiple constraints. An optimality condition and algorithm is developed for the multiple constraint finite form problem. For multiple constraints, the time needed for the multiple constraint finite form algorithm is the time needed to solve a single constraint finite form problem multiplied by the number of constraints. Some multiple constraint problems cannot be transformed to multiple constraint finite form problems.     

一种新的增强ElGamal加密机制

针对传统的ElGamal加密机制不能抵抗自主选择密文攻击的问题,通过引入安全Hash函数和伪随机数发生函数给出了一种新的增强ElGamal加密机制.结果表明,该机制不仅能够抵抗自主选择密文攻击,且由于伪随机数发生函数的引入,解决了加密过程中随机数的暴露问题.该机制加密过程需要两次模幂运算,解密过程仅需一次模幂运算.完全适合于对安全性要求较高但是对系统资源要求消耗低的应用环境.     

The constrained compartmentalized knapsack problem: mathematical models and solution methods

The constrained compartmentalized knapsack problem can be seen as an extension of the constrained knapsack problem. However, the items are grouped into different classes so that the overall knapsack has to be divided into compartments, and each compartment is loaded with items from the same class. Moreover, building a compartment incurs a fixed cost and a fixed loss of the capacity in the original knapsack, and the compartments are lower and upper bounded. The objective is to maximize the total value of the items loaded in the overall knapsack minus the cost of the compartments. This problem has been formulated as an integer non-linear program, and in this paper, we reformulate the non-linear model as an integer linear master problem with a large number of variables. Some heuristics based on the solution of the restricted master problem are investigated. A new and more compact integer linear model is also presented, which can be solved by a branch-and-bound commercial solver that found most of the optimal solutions for the constrained compartmentalized knapsack problem. On the other hand, heuristics provide good solutions with low computational effort.     

基于最优扩域上的椭圆曲线密码系统的基点选取

本文讨论了重模二次剩余的定义、性质，完整地设计出选取最优扩域上的椭圆曲线密码系统的基点的算法，并给出了选取成功的概率和相关数学证明．     

Simultaneously lifting sets of binary variables into cover inequalities for knapsack polytopes

Cover inequalities are commonly used cutting planes for the 0–1 knapsack problem. This paper describes a linear-time algorithm (assuming the knapsack is sorted) to simultaneously lift a set of variables into a cover inequality. Conditions for this process to result in valid and facet-defining inequalities are presented. In many instances, the resulting simultaneously lifted cover inequality cannot be obtained by sequentially lifting over any cover inequality. Some computational results demonstrate that simultaneously lifted cover inequalities are plentiful, easy to find and can be computationally beneficial.     

Some properties of cliques in 0–1 mixed integer programs

Summary In this note we present new properties of cliques induced constraints straintsX(C _r ⁺ )-X(C _r ^- ) ≤ 1 - |C _r ^- | for λ εS, whereS is the set of cliques that are implied by 0–1 mixed integer programs. These properties allow to further fixing of 0–1 variables, to detect instance's infeasibility and to imply new cliques.     

The continuous collapsing Knapsack problem

A Collapsing Knapsack is a container whose capacity diminishes as the number of items it must hold is increased. This paper focuses on those cases in which the decision variables are continuous, i.e., can take any non-negative value. It is demonstrated that the problem can be reduced to a set of two dimensional subproblems. Strategies for elimination of subproblems and conditions permitting reduction to a set of one dimensional problems are also considered. Computational results indicate that the procedure is quite efficient. Even for large problems only a small number of subproblems have to be solved.     

How to Mask the Structure of Codes for a Cryptographic Use

In this paper we show how to strengthen public-key cryptosystems against known attacks, together with the reduction of the public-key. We use properties of subcodes to mask the structure of the codes used by the conceiver of the system. We propose new parameters for the cryptosystems and even a modified Niederreiter cryptosystem in the case of Gabidulin codes, with a public-key size of less than 4000 bits.Communicated by: P. WildAMS Classification: 11T71     

An Approach to the Subproblem of the Cutting Angle Method of Global Optimization

The solution of the Subproblem of the Cutting Angle Method of Global Optimization for problems of minimizing increasing positively homogeneous of degree one functions is proved to be NP-Complete. For the proof of this fact we formulate another problem which we call “Dominating Subset with Minimal Weight”. This problem is also NP-Complete. An O(n²)-time algorithm is presented for approximate solution of Dominant Subset with Minimal Weight Problem. This problem can be expressed as a kind of Assignment Problem in which it is allowed to assign multiple tasks to a single processor. Experimental analysis of the algorithm is performed using the program implemented in ANSI-C. The results of the analysis show the efficiency of the proposed algorithm.Mathematics Subject Classification (2000): 65K05, 90C27, 68Q25     

利用有限简单连分数的最佳逼近原理破译公钥密码RSA及其实现

攻击RSA密码体制最有效的方式就是计算出它的解密指数,即找出其密钥.介绍一种新的攻击方法:当RSA密码体制使用低加密指数时,利用有限简单连分数的最佳有理逼近原理,依次计算出它的渐近分数,逐一加以试用,直到找到其最佳收敛子,从而将模数分解并计算出它的解密指数,即密钥.使用这种方法可以准确地计算出解密指数,减少解密时间,加快解密过程.