线性同余人字映射组合产生均匀随机数

研究了线性同余法与人字映射组合随机数发生器 :xn=Axn-1(mod M) ,wn=2 xn,　 xn≤ 0 .5 M,wn=2 (M-xn) +1 ,　 xn>0 .5 M,yn=wn/ M.该组合发生器比相应的线性同余法在空间结构上有明显改善 ,并通过统计检验     

伪随机数串叠加的渐近理论

用单一方式产生的伪随机数串,其随机性常不够理想。讨论当将大量这种串按同余的意义叠加时,其结果的渐近性态,得出了能收敛到真正的随机性的充要条件。     

随机数生成

本文讨论最有用的给定概率密度函数情形下的随机数生成问题,借助几何概率描述舍选法。     

伪补分配格的同余理想与同余关系

L是完备的伪补分配格,I是L的同余理想,本文得到以下结果：⑴θ是L的以I为核的最大同余关系的条件。⑵L的以I为核的同余关系是唯一的充分必要条件。⑶L的同余理想与同余关系之间有一一对应关系的充分必要条件。     

一种伪随机数产生器

本文给出一个基于矩阵的随机数产生器,线性同余随机数产生器是它的一个特例.     

伪补分配格上的主同余关系

本文研究了伪补分配格Ｌ的＊－同余关系的基本性质。主要给出了：⑴主同余θ＊（ａ,ｂ）的一个具体刻划;⑵理想Ⅰ成为同余理想的一个充要条件的以Ⅰ为核心的最小＊－同余θ＊（Ｉ）;⑶Ｌ上的格同余θＬ（ａ,ｂ）成为＊－同余的干充要条件。其中的大部分结果必进或包含了已有的结论。     

从二维结构分析乘同余伪随机数序列

本文指出由乘同余伪随机数序列构成的伪随机二维点集总呈现条状分布，通过实例表明这种有缺陷的几何结构可利用组合法予以改进。     

基于单模数线性同余方程组设计的公钥密码体系

本文基于MH-KPKC体系和HILL密码体系的构建思想,提出了基于单模数线性同余方程组设计的公钥密码体系.该体制无需利用超递增序列和贪心算法恢复明文.算例说明了该体制的可行性。     

纯正半群上的同余扩张(一)

刻划半群上的同余及其扩张是半群的代数理论中的一个非常重要的课题．本文讨论了带上的同余的正规性和不变性以及在其Ｈａｌｌ半群上的扩张，从同余扩张的角度刻划了带上的同余的性质，给出了扩张的极大、极小同余的描述．     

一类模数为合数的多模数线性同余方程组的数值解法

本文提出了模为合数的多模数线性同余方程组求解问题,研究了该类同余方程组的数值解法,得到了解的表达式,给出了算例,算例验证了解表达式的正确性。     

Pseudo random number generator based on quantum chaotic map

For many years dissipative quantum maps were widely used as informative models of quantum chaos. In this paper, a new scheme for generating good pseudo-random numbers (PRNG), based on quantum logistic map is proposed. Note that the PRNG merely relies on the equations used in the quantum chaotic map. The algorithm is not complex, which does not impose high requirement on computer hardware and thus computation speed is fast. In order to face the challenge of using the proposed PRNG in quantum cryptography and other practical applications, the proposed PRNG is subjected to statistical tests using well-known test suites such as NIST, DIEHARD, ENT and TestU01. The results of the statistical tests were promising, as the proposed PRNG successfully passed all these tests. Moreover, the degree of non-periodicity of the chaotic sequences of the quantum map is investigated through the Scale index technique. The obtained result shows that, the sequence is more non-periodic. From these results it can be concluded that, the new scheme can generate a high percentage of usable pseudo-random numbers for simulation and other applications in scientific computing.     

A linear time bin-packing algorithm

In the bin-packing problem a list L of numbers in (0, 1] is to be packed into unit capacity bins. Let $\text{L}{}^1$ denote the minimum number of bins required. We present a linear time bin-packing algorithm for the off-line version of this problem. The algorithm uses at most $\text{4}\text{3}\text{L1 + 2}$ bins.     

Approximating the fixed linear crossing number

We present a randomized polynomial-time approximation algorithm for the fixed linear crossing number problem (FLCNP). In this problem, the vertices of a graph are placed in a fixed order along a horizontal “node line” in the plane, each edge is drawn as an arc in one of the two half-planes (pages), and the objective is to minimize the number of edge crossings. FLCNP is NP-hard, and no previous polynomial-time approximation algorithms are known. We show that the problem can be generalized to k pages and transformed to the maximum k-cut problem which admits a randomized polynomial-time approximation. For the 2-page case, our approach leads to a randomized polynomial time 0.878+0.122ρ approximation algorithm for FLCNP, where ρ is the ratio of the number of conflicting pairs (pairs of edges that cross if drawn in the same page) to the crossing number. We further investigate this performance ratio on the random graph family G_n,1/2, where each edge of the complete graph K_n occurs with probability . We show that a longstanding conjecture for the crossing number of K_n implies that with probability at least 1-4e^-λ2, the expected performance bound of the algorithm on a random graph from G_n,1/2 is 1.366+O(λ/n). A series of experiments is performed to compare the algorithm against two other leading heuristics on a set of test graphs. The results indicate that the randomized algorithm yields near-optimal solutions and outperforms the other heuristics overall.     

Asymptotics in addition of pseudo-random sequences

The performance of individual pseudo-random sequence, generated by some mechanism, is often not ideal. The asymptotic performance of the addition (in the sense (mod ρ)) of a large number of such individual sequences is studied and the necessary and sufficient condition under which the resulting sequence may converge to genuine randomness is obtained. Project supported by the National Natural Science Foundation of China, the UPGC of Hong Kong, Hong Kong Baptist University and SRCU.     

On a nonlinear congruential pseudorandom number generator

A nonlinear congruential pseudorandom number generator with modulus is proposed, which may be viewed to comprise both linear as well as inversive congruential generators. The condition for it to generate sequences of maximal period length is obtained. It is akin to the inversive one and bears a remarkable resemblance to the latter.

     

On the number of iterations of Karmarkar's algorithm for linear programming

Karmarkar's algorithm for linear programming was published in 1984, and it is highly important to both theory and practice. On the practical side some of its variants have been found to be far more efficient than the simplex method on a wide range of very large calculations, while its polynomial time properties are fundamental to research on complexity. These properties depend on the fact that each iteration reduces a potential function by an amount that is bounded away from zero, the bound being independent of all the coefficients that occur. It follows that, under mild conditions on the initial vector of variables, the number of iterations that are needed to achieve a prescribed accuracy in the final value of the linear objective function is at most a multiple ofn, wheren is the number of inequality constraints. By considering a simple example that allowsn to be arbitrarily large, we deduce analytically that the magnitude of this complexity bound is correct. Specifically, we prove that the solution of the example by Karmarkar's original algorithm can require aboutn/20 iterations. Further, we find that the algorithm makes changes to the variables that are closely related to the steps of the simplex method.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.     

基于指数型核函数的线性规划原始对偶内点算法

给出线性规划原始对偶内点算法的一个单变量指数型核函数.首先研究了这个指数型核函数的性质以及其对应的障碍函数.其次,基于这个指数型核函数,设计了求解线性规划问题的原始对偶内点算法,得到了目前小步算法最好的理论迭代界.最后,通过数值算例比较了基于指数型核函数的原始对偶内点算法和基于对数型核函数的原始对偶内点算法的计算效果.     

Right triangles with algebraic sides and elliptic curves over number fields

Given any positive integer n, we prove the existence of infinitely many right triangles with area n and side lengths in certain number fields. This generalizes the famous congruent number problem. The proof allows the explicit construction of these triangles; for this purpose we find for any positive integer n an explicit cubic number field ℚ(λ) (depending on n) and an explicit point P _λ of infinite order in the Mordell-Weil group of the elliptic curve Y ² = X ³ − n ² X over ℚ(λ). Research of the rest of authors was supported in part by grant MTM 2006-01859 (Ministerio de Educación y Ciencia, Spain).