大整数因子分解中的二次筛法优化

本文研究了大整数因子分解中的二次筛法，提出了算法选择，参数选择，硬件选取和过程控制上的优化途径，直接影响RSA密码系统，推动信息安全的发展。     

素因子分解与素数的快速判定法研究综述

素数的判定与整数的素因子分解是重要的有实际应用价值的计算理论问题.本文主要将近十年来素因子分解及素数的快速判定方法和结果作一简单介绍.     

保密通信的发展概况(续)

6　RSA公钥方案公元前三世纪 ,希腊数学家欧几里德在《几何原本》中叙述了以下定理并且给出了证明 :每个大于 1的整数都 (不计次序 )可唯一分解成有限个素数 (或叫质数 )的乘积 .这叫算术基本定理 ,是初等数论的基石 .这个定理在理论上是很漂亮的 ,但是在实际上人们会问 :给了一个很大的正整数n ,求n的分解式是否容易 ?一个最笨的算法是用 2 ,3,...,n- 1依次去除n ,如果均除不尽n ,则n为素数 ,分解完毕 .如果某个i( 2 ≤i≤n- 1 )除尽n ,则最小的这个i是n的一个素因子 .再对整数n i继续下去 .但是这个算法至少需要n个运算 ,而算式的复杂性…     

量子计算与公钥密码

首先介绍P.Shor的量子算法,然后运用该算法,对几种公钥密码体制(基于整数分解的困难性的RSA公钥体制;基于离散对数的困难性的公钥体制,如E lG am a l体制、椭圆曲线密码(ECC)体制等)进行了分析.     

唯一因子分解整环

1.引言我們知道,每个不等于±1及0的整数都可以表为有限个素数的乘积,并且若不計素因子的正負号,这种分解是唯一的。这就是通常所謂的整数唯一因子分解定理。对于一个域上的一元或多元多項式来說,相应的唯一因子分解定理也成立,即域F上每个次数≥1的多項式都可表成有限个在F上不可約的多項式之乘积,并且,在不可約因子差一个卢中的非零元素的意义下这种分解是唯一的。对于整数及域上一元多項式的唯一因子分解定理,通常是基于可以进行带余除法这一事实来証明的。万哲先同志在[1]中就几个重要的数域 (复数域、实数域和有理数域) 及整数环上一元多項式的因子分解問題給了詳細的論述,并且介紹了把带余除法抽象化而得到的一个較一般的概念,即欧氏环,进一步証明,在欧氏环里唯一因子分解定理亦成     

一个欧氏环的素因子分解方法

本文研究了整数环的一个代数扩环的性质.利用最优化理论证明了这个代数扩环是一个欧氏环,给出了它的单位和素元的刻画,得到了对这个代数扩环中任意素进行素因子分解的方法.     

(0, mf-k+1)-图中具有正交(0,f)-因子分解的子图

设G是一个简单图, f是定义在V(G)上的整数值函数,且m是大于等于2的整数. 讨论(0, mf-k+1)-图G的正交因子分解, 并且证明了对任意的1≤k≤m, (0, mf-k+1)-图G中存在着一个子图R, 使得R有一个(0,f)-因子分解正交于图G中的任意一个k-子图H.     

一个简单整数性质的应用

性质如果m、n为整数,那么m+n与m-n同奇同偶. 这一貌似简单的性质,在解有关整数、整除、方程的有理数解(包括整数解)以及整数的分解等问题时,常常能化繁为简、化难为易.     

弗洛伊登塔尔不可能之谜的机械化算法

1969年荷兰数学家汉斯·弗洛伊登塔尔提出的"和与积之谜",涉及到整数分拆和因子分解的基本性质,这个表述非常简单的问题表面上看是一个不可能解决的谜题.文章从自动推理智能体的视角,用浅显而严格的语言解释弗洛伊登塔尔问题的求解过程,可作为计算机搜索程序的设计参照.文章从弗洛伊登塔尔问题延伸定义了弗洛伊登塔尔数(Freudenthal numbers, F数)序列,通过计算机数学实验探讨了F数序列的性质,提出了几个有趣的未解决问题.     

从N!的质因数分解说起——“通解”2019美国数学竞赛AMC10～12

<正>2019美国数学竞赛AMC 10-2题、10-25题(AMC 12-24题)如下:(1)(20!-15!)的百位数是多少?(2)N为整数,1≤N≤50,使得((N~2-1)!/(N!)~N)为整数的N一共有多少个?值得注意的是,这一类含有N!形式的题型经常出现在各种数学竞赛当中.想要"通解"这一类问题,我们先得从质因数分解说起.质因数分解是研究整数规律的一个基本方法.在计算理论和密码学领域,如何快速地分     

A green policy to schedule tasks in a distributed cloud

In the last years, demand and availability of computational capabilities experienced radical changes. Desktops and laptops increased their processing resources, exceeding users’ demand for large part of the day. On the other hand, computational methods are more and more frequently adopted by scientific communities, which often experience difficulties in obtaining access to the required resources. Consequently, data centers for outsourcing use, relying on the cloud computing paradigm, are proliferating. Notwithstanding the effort to build energy-efficient data centers, their energy footprint is still considerable, since cooling a large number of machines situated in the same room or container requires a significant amount of power. The volunteer cloud, exploiting the users’ willingness to share a quote of their underused machine resources, can constitute an effective solution to have the required computational resources when needed. In this paper, we foster the adoption of the volunteer cloud computing as a green (i.e., energy efficient) solution even able to outperform existing data centers in specific tasks. To manage the complexity of such a large scale heterogeneous system, we propose a distributed optimization policy to task scheduling with the aim of reducing the overall energy consumption executing a given workload. To this end, we consider an integer programming problem relying on the Alternating Direction Method of Multipliers (ADMM) for its solution. Our approach is compared with a centralized one and other non-green targeting solutions. Results show that the distributed solution found by the ADMM constitutes a good suboptimal solution, worth to be applied in a real environment.     

A scenario decomposition algorithm for 0–1 stochastic programs

We propose a scenario decomposition algorithm for stochastic 0–1 programs. The algorithm recovers an optimal solution by iteratively exploring and cutting-off candidate solutions obtained from solving scenario subproblems. The scheme is applicable to quite general problem structures and can be implemented in a distributed framework. Illustrative computational results on standard two-stage stochastic integer programming and nonlinear stochastic integer programming test problems are presented.     

Computational assessment of distributed decomposition methods for stochastic linear programs

Incorporating uncertainty in optimization models gives rise to large, structured mathematical programs. Decomposition procedures are well-suited for parallelization, thus providing a promising venue for solving large stochastic programs arising in diverse practical applications. This paper presents an adaptation of decomposition methods for execution on distributed computing systems. A regularized decomposition, as well as the linear decomposition algorithm, are implemented for execution on distributed multiprocessors. Computational results on an IBM SP2 multiprocessor system are reported to demonstrate the comparative performance of the methods on a number of test cases.     

A heuristic decomposition approach to optimal control in a water supply model

The optimal pump control problem in a water supply system can be formulated as a mixed integer programming problem. In general, this problem is very difficult to solve by conventional integer programming algorithms, because the number of decision variables is as large as the total number of combinations of pump stations and control periods. However, it possesses a certain block triangular structure, which offers an attractive computational scheme. Taking advantage of this structure, this paper proposes a heuristic decomposition algorithm for finding a good feasible solution to this type of mixed integer programming problems. Numerical results for an actual pump control problem are also reported.     

Allocating modelling resources in distributed model management systems

Due to the growing popularity of distributed computing systems and the increased level of modelling activity in most organizations, significant benefits can be realized through the implementation of distributed model management systems (DMMS). These systems can be defined as a collection of logically related modelling resources distributed over a computer network. In several ways, functions of DMMS are isomorphic to those of distributed database systems. In general, this paper examines issues viewed as central to the development of distributed model bases (DMB). Several criteria relevant to the overall DMB design problem are discussed. Specifically, this paper focuses on the problem of distributing decision models and tools (solvers), henceforth referred to as theModel Allocation Problem (MAP), to individual computing sites in a geographically dispersed organization. In this research, a 0/1 integer programming model is formulated for the MAP, and an efficient dual ascent heuristic is proposed. Our extensive computational study shows in most instances heuristic-generated solutions which are guaranteed to be within 1.5–7% of optimality. Further, even problems with 420 integer and 160,000 continuous variables took no more than 60 seconds on an IBM 3090-600E computer.     

Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming

Decomposition has proved to be one of the more effective tools for the solution of large-scale problems, especially those arising in stochastic programming. A decomposition method with wide applicability is Benders' decomposition, which has been applied to both stochastic programming as well as integer programming problems. However, this method of decomposition relies on convexity of the value function of linear programming subproblems. This paper is devoted to a class of problems in which the second-stage subproblem(s) may impose integer restrictions on some variables. The value function of such integer subproblem(s) is not convex, and new approaches must be designed. In this paper, we discuss alternative decomposition methods in which the second-stage integer subproblems are solved using branch-and-cut methods. One of the main advantages of our decomposition scheme is that Stochastic Mixed-Integer Programming (SMIP) problems can be solved by dividing a large problem into smaller MIP subproblems that can be solved in parallel. This paper lays the foundation for such decomposition methods for two-stage stochastic mixed-integer programs.     

Using matrix approximation for high-dimensional discrete optimization problems: Server consolidation based on cyclic time-series data

We consider the assignment of enterprise applications in virtual machines to physical servers, also known as server consolidation problem. Data center operators try to minimize the number of servers, but at the same time provide sufficient computing resources at each point in time. While historical workload data would allow for accurate workload forecasting and optimal allocation of enterprise applications to servers, the volume of data and the large number of resulting capacity constraints in a mathematical problem formulation renders this task impossible for any but small instances. We use singular value decomposition (SVD) to extract significant features from a large constraint matrix and provide a new geometric interpretation of these features, which allows for allocating large sets of applications efficiently to physical servers with this new formulation. While SVD is typically applied for purposes such as time series decomposition, noise filtering, or clustering, in this paper features are used to transform the original allocation problem into a low-dimensional integer program with only the extracted features in a much smaller constraint matrix. We evaluate the approach using workload data from a large data center and show that it leads to high solution quality, but at the same time allows for solving considerably larger problem instances than what would be possible without data reduction and model transform. The overall approach could also be applied to similar packing problems in service operations management.     

Admit or preserve? Addressing server failures in cloud computing task management

Cloud computing task management has a critical role in the efficient operation of the cloud resources, i.e., the servers. The task management handles critical and complicated decisions, overcoming the inherent dynamic nature of cloud computing systems and the additional complexity due to the large magnitude of resources in such systems (tens of thousands of servers). Due to the fact that servers may fail, task management is required to conduct both task admissions and task preservation decisions. Moreover, both these decisions require considering future system trajectories and the interplay between preservation and admission. In this paper we study the combined problem of task admission and preservation in a dynamic environment of cloud computing systems through analysis of a queueing system based on a Markov decision process (MDP). We show that the optimal operational policy is of a double switching curve type. On face value, the extraction of the optimal policy is rather complicated, yet our analysis reveals that the optimal policy can be reduced to a single rule, since the rules can effectively be decoupled. Based on this result, we propose two heuristic approaches that approximate the optimal rule for the most relevant system settings in cloud computing systems. Our results provide a simple policy scheme for the combined admission and preservation problem that can be applied in a complex cloud computing environments, and eliminate the need for sophisticated real-time control mechanisms.

     

柔性制造系统的载荷模型和对偶分解算法

本文研究柔性制造系统最优排序问题的载荷模型，通过优化系统的最优利用率并考虑系统各机器的工作平衡，本文给出了载荷问题三个新的优化模型，这些模型形成具有０－１变量和一般整型变量的大规模整数规划问题，根据分解理论，考虑到问题的变量特性，这些大规模问题可被分解成若干维数较低的子问题求解，文章还给出了一个对偶分解算法。