逻辑函数无冗余覆盖选择问题

逻辑函数的最小化算法可以分为两大步骤,产生本源蕴涵项和在这些蕴涵项中选择一个最小覆盖。提出一个适于大变量输入输出逻辑函数的实质项与相对冗余项的识别和选择近似最小覆盖的算法。Benchmark例题测试表明,算法具有理想的处理效果。     

关于实质本源蕴涵项的识别问题

本文揭示ＥＳＰＲＥＳＳＯ算法和Ｍｕｒｏｇａ等提出的求绝对最小算法中识别实质本源蕴涵项的方法具有近似的复杂度。文中还给出了一个在产生本源蕴涵项过程中识别实质本源项的算法。     

逻辑函数绝对最小覆盖的改进算法

逻辑函数的绝对最小化算法存在的主要问题是运行时间过长和需要的存储空间过大。本文提出了一个从给定本源蕴涵项集合中抽出一个绝对最小覆盖的算法，而时间、空间的需求被大缩小了。     

蕴涵项的扩展算法

本文提出了一个把逻辑函数的积项扩展为本源蕴涵项的算法。用此算法得到的本源蕴涵项集合通过去冗过程产生的最后结果最接近绝对最小化的解。     

一种求解多值逻辑函数接近最小覆盖的算法

1.引言 本文研究Allen-Givone多值逻辑代数系统中的“积之和”形式的函数的简化算法。首先,在讨论符合目前多值逻辑函数实现特点的合理代价标准基础上,提出了一种折衷的代价标准,按着这个标准不求所有质蕴涵项集合,直接求解无冗余覆盖。这个算法以减少文字门的个数为依据,在确定某些质蕴涵项和实现文字数较少之间进行权衡,它在一个位     

多输出逻辑函数最小化的一个算法

本文描述一个多输出逻辑函数的最小化算法。函数解中积项总数的多少被看作是衡量算法优劣的最重要指标。因此，我们努力使解中的积项被尽可能多的组成函数共享。本文求本源蕴涵项的方法与［１］是相似的。因此，本文也可看成是［１］向多输出函数的延伸。     

组合函数无冗余覆盖的优算法

本文提出了“相邻点分布密度”及质蕴涵项“生成元”的概念,从而使函数质蕴涵项的生成在选点及方向上,为形成无冗余覆盖有了依据,并进而提出了一个产生函数无冗余覆盖的较优算法,从理论和实践上验证了根据本算法编制的程序条数少、速度快、存储量少。     

接近最小化积之和式的简化方法

本文介绍一个将任意布尔函数最小化的算法。其方法与先前首先求得全部质蕴涵项然后确定最小覆盖的方法不同。这个算法为了获得接近最小的积之和的实现,运用一组条件来选择质蕴涵项。并把它推广到多输出和不完全规定函数的情况。所提出的算法的主要特点是求解同一问题所化费的机器时间比用其它的算法少。如果只要求结果是较少的乘积项时,MINI算法对于输入、输出数目多的布尔函数可以给出较好的结果。这个算法也适合于寻求内部按积之和实现的大的布尔函数的可编程序阵列(PLA)的解。     

改进的Q-M逻辑函数化简方法

为进一步提高逻辑函数的化简速度,提出一种改进的Q-M逻辑函数化简方法。在迭代比较过程中设置2个权值以缩减可合并蕴涵项集合的大小,只对满足条件的蕴涵项进行合并处理,得到全部质蕴涵项。构造质蕴涵项与最小项关联图,利用启发式规则得到能蕴涵全部最小项的最少质蕴涵项集合,从而得到逻辑函数的最小覆盖,完成逻辑函数化简。实验结果表明,该算法能降低迭代次数,减少逻辑函数的化简时间。     

大变量多输出逻辑函数实质项识别算法

在对Espresso算法进行分析改进的基础上，提出了一种基于全域识别的多输入多输出逻辑函数实质本源项、完全冗余项和相对冗余项生成算法，该算法通过对基于积项表示的多输入多输出逻辑函数的余因子计算来进行全域判断，根据全域判断结果来识别实质本源项、完全冗余项和相对冗余项，从而构成实质本源项集合、完全冗余项集合和相对冗余项集合。对基于二级SOP型的多输入多输出逻辑函数设计了多输入多输出逻辑函数优化识别软件系统，允许的最大输入变量数为128、最大输出变量数为256、最大输入输出变量总和为300、最大输入积项数为20 000。软件系统在Pentium 1.8GHz、512MB内存的计算机上通过了Benchmark例题的测试。     

用关键特征集对逻辑进行优化

提出了一个两级逻辑优化的新算法，与通过函数质蕴涵集求解覆盖的传统算法不同，文中将求解逻辑函数的质蕴涵项与推导覆盖问题相结合，直接得出覆盖问题的解。算法的主要问题可以简化为：对于立方描述的单元，求解最小覆盖，在这个过程中又提出了一种改进的覆盖吸收算法，基于关键特征集合的选拔吸收算法，此算法不用求所有的立方，通过标准的测试例子与原来的Espresso算法作比较，对于大电路，在计算时间上，新算法有明显的改进。     

Some Further Studies on Determination of all the Minimal Prime Implicant Covers of Switching Functions†

A method of determination of all the minimal prime implicant covers of switching functions by utilizing their connected cover term matrices is suggested in the paper. The method presented is an extension of the technique suggested by the authors in a previous paper (Choudhury and Das 1964). When majority of the prime implicants of a switching function will occur in more than two different columns of the cover table, it is shown that the determination of all the minimal prime implicant covers can often be greatly facilitated by initially dividing the cover table into more than two suitable sub-tables.     

SECURITY OF NUMBER THEORETIC PUBLIC KEY CRYPTOSYSTEMS AGAINST RANDOM ATTACK,III

This paper concludes the discussion we began in the last two issues of CRYPTOLOGIA. A typical message receiver using an RSA public key cryptosystem believes that the secret nontrivial factors p and q of his public coding modulus m are primes. But he need not know that p or q are prime, or even square free. We give a few examples below. In some of them the “RSA public key cryptosystem” based on integers P and Q erroneously thought both to be prime works perfectly, but is more vulnerable to a cryptanalytic attack of the type G. J. Simmons and J. N. Norris [7] have suggested. In other cases these cryptosystems malfunction in an obvious fashion likely to be apprehended quickly by the message receiver. After the examples we prove all the results in I and II except a few which, like Theorems 1.1, 1.2 and 1.3, are obvious corollaries of other results in those papers.     

A lower bound on the mod 6 degree of the OR function

We examine the computational power of modular counting, where the modulus m is not a prime power, in the setting of polynomials in Boolean variables over Z _m . In particular, we say that a polynomial P weakly represents a Boolean function f (both have n variables) if for any inputs x and y in {0,1}ⁿ, we have whenever . Barrington et al. (1994) investigated the minimal degree of a polynomial representing the OR function in this way, proving an upper bound of O(n ^{1/ r} ) (where r is the number of distinct primes dividing m) and a lower bound of . Here, we show a lower bound of when m is a product of two primes and in general. While many lower bounds are known for a much stronger form of representation of a function by a polynomial (Barrington et al. 1994, Tsai 1996), very little is known using this liberal (and, we argue, more natural) definition. While the degree is known to be for the generalized inner product because of its high communication complexity (Grolmusz 1995), our bound is the best known for any function of low communication complexity and any modulus not a prime power. received 29 September 1994     

Two-Level Multiple-Output Logic Minimization Using A Single Function

A new method for obtaining a two-level collective minimal cover for a set of incompletely-specified switching functions $S=\{f_1,f_2,\ldots,f_n\}$ is presented. The method relies on the introduction of a single auxiliary function F whose subfunctions (restrictions) with respect to some additional auxiliary variables $y_1,y_2,\ldots,y_{n-1}$ are certain members of S . The complete sum of F has full information on the multiple-output prime implicants (MOPIs) of the set of functions S . A particularly constrained minimal cover for F contains only labeled versions of some paramount prime implicants (PPIs) of S and can be used to construct a multiple-output minimal cover for S . The present method can proceed by map, algebraic or tabular techniques, though only the map version is presented herein. This version employs a single map whose construction avoids the ANDing operations needed in the classical method, and whose size is almost one half the total size of the maps used by the classical method, and whose entries can be variable as well as constant. The minimization process is a direct two-step technique that avoids constructing the set of all PPIs as it produces only these PPIs needed in the minimal cover. Details of the method are carefully explained and illustrated via a typical example.     

适用于建立密码体制的椭圆曲线的构造方法及实现

本文提出了一种素域Ｚｐ（ｐ〉３）上椭圆曲线的构造方法，以获得椭圆曲线Ｅ／Ｚｐ，使得Ｅ（Ｚｐ）无平滑阶子群且其阶＃Ｅ（Ｚｐ）中含有多个大素因子。这类椭圆曲线可用于密码技术中各种需要合数阶群的情形。在这类椭圆曲线上建立密码体制，消除了离散对数型保密或数字签名方案信息泄露的隐患，为建立可抗击各种攻击的椭圆曲线密码体制提供了基础。同时，本文还我存的用于密码体制的椭圆曲线构造方法（这些方法用于构造＃Ｅ（Ｚｐ     

Prime number generation using memetic programming

For centuries, the study of prime numbers has been regarded as a subject of pure mathematics in number theory. Recently, this vision has changed and the importance of prime numbers has increased rapidly, especially in information technology, e.g., public key cryptography algorithms, hash tables, and pseudo-random number generators. One of the most popular topics to attract attention is to find a formula that maps the set of natural numbers into the set of prime numbers. However, to date there is no known formula that produces all primes. In this article, we use a hybrid evolutionary algorithm, called the memetic programming (MP) algorithm, to generate mathematical formulas that produce distinct primes. Using the MP algorithm, we succeeded in discovering an interesting set of formulas that produce sets of distinct primes.     

快速结构化图像修补

图像修补的目的是对图像中缺失的区域进行修复,或是将图像中的物体抠去并进行背景填充,以取得融合到难以用肉眼分辨的效果。在图像修补的过程中,较大的结构信息是修补的难点。为此提出了一种快速结构化的图像修补算法,该方法将图像修补分为结构修补与纹理填充两个部分,即在用户指定待修补区域与结构曲线之后,首先定义全局最优化能量函数,并用动态规划与置信度传播的算法将其最小化来完成结构修补;然后对剩余的待修补区域通过按行扫描来进行纹理填充,其中对于边界处的点是使用基于样本的修补算法,而对于待修补区域内部的点,则使用快速的加权Ashikhmin-WL算法,扫描完成后输出修补后的图像;最后实现了一个快速结构化图像修补系统,并给出一些实验结果,从实验结果中可以看到,该方法的修补流程与算法是有实际应用价值的。     

Optimal strong primes

We clarify the notion of a strong prime by supplying a precise definition and a characterization for an optimal strong prime. We present a conjecture regarding the distribution and density of optimal strong primes, allowing one to predict in advance the time needed to compute one optimal strong prime of a given bit length. Based on these results, we develop an algorithm to compute optimal strong primes. Some experimental results are also included.