一个门限RSA密码体制

传统的门限RSA密码体制由于都是在环Zψ（n )上进行的，而会遇到固有的困难；Zψ（n ）不是域且ψ（n）必须保密，提出了一个新的门限RSA密码体制，通过数学变换克服了以上的困难，并且对它的安全性进行了简要分析。     

Geometric quadrisection in linear time, with application to VLSI placement

We consider the following problem: given a set of points in the plane, each with a weight, and capacities of the four quadrants, assign each point to one of the quadrants such that the total weight of points assigned to a quadrant does not exceed its capacity, and the total distance is minimized.

This problem is most important in placement of VLSI circuits and is likely to have other applications. It is NP-hard, but the fractional relaxation always has an optimal solution which is “almost” integral. Hence for large instances, it suffices to solve the fractional relaxation. The main result of this paper is a linear-time algorithm for this relaxation. It is based on a structure theorem describing optimal solutions by so-called “American maps” and makes sophisticated use of binary search techniques and weighted median computations.

This algorithm is a main subroutine of a VLSI placement tool that is used for the design of many of the most complex chips.     

大整数因子分解新算法及对RSA密码制的解密

对一大类大整数的因子分解构造算法WZH,可在O(L(lnm)2)+O(lnm)3(L相似文献   

An optimization algorithm for a penalized knapsack problem

We study a variation of the knapsack problem in which each item has a profit, a weight and a penalty; the sum of profits of the selected items minus the largest penalty associated with the selected items must be maximized. We present an ILP formulation and an exact optimization algorithm.     

Lagrangean heuristics combined with reoptimization for the 0-1 bidimensional knapsack problem

First, this paper deals with lagrangean heuristics for the 0-1 bidimensional knapsack problem. A projected subgradient algorithm is performed for solving a lagrangean dual of the problem, to improve the convergence of the classical subgradient algorithm. Secondly, a local search is introduced to improve the lower bound on the value of the biknapsack produced by lagrangean heuristics. Thirdly, a variable fixing phase is embedded in the process. Finally, the sequence of 0-1 one-dimensional knapsack instances obtained from the algorithm are solved by using reoptimization techniques in order to reduce the total computational time effort. Computational results are presented.     

公开密钥体制与Euler-Fermat定理通俗证明

随着计算机的广泛使用，文件加密解密已成为相当频繁的工作．本文叙述了公开密钥体制中的一种方法，并对其使用的数学工具给出一个通俗证明，以使加密解密工作更加方便、有效．     

Stochastic on-line knapsack problems

Different classes of on-line algorithms are developed and analyzed for the solution of {0, 1} and relaxed stochastic knapsack problems, in which both profit and size coefficients are random variables. In particular, a linear time on-line algorithm is proposed for which the expected difference between the optimum and the approximate solution value isO(log^3/2 n). An(1) lower bound on the expected difference between the optimum and the solution found by any on-line algorithm is also shown to hold.Corresponding author.Partially supported by the Basic Research Action of the European Communities under Contract 3075 (Alcom).Partially supported by research project Models and Algorithms for Optimization of the Italian Ministry of University and Scientific and Technological Research (MURST 40%).     

A public-key cryptosystem utilizing cyclotomic fields

While it is well-known that the RSA public-key cryptosystem can be broken if its modulusN can be factored, it is not known whether there are other ways of breaking RSA. This paper presents a public-key scheme which necessarily requires knowledge of the factorization of its modulus in order to be broken. Rabin introduced the first system whose security is equivalent to the difficulty of factoring the modulus. His scheme is based on squaring (cubing) for encryption and extracting square (cube) roots for decryption. This introduces a 14 (19) ambiguity in the decryption. Various schemes which overcome this problem have been introduced for both the quadratic and cubic case. We generalize the ideas of Williams' cubic system to larger prime exponents. The cases of higher prime order introduce a number of problems not encountered in the quadratic and cubic cases, namely the existence of fundamental units in the underlying cyclotomic field, the evaluation of higher power residue symbols, and the increased difficulty of Euclidean division in the field.     

基于对Cao-Li公钥密码系统的分析和修改

指出Cao-Li公钥密码系统会由于某些参数选择而导致系统的安全问题；利用背包系统对Cao—Li系统的改进进行改进，解决原有系统的参数依赖性问题．