Miller-Rabin素数检测优化算法研究与实现

针对素数值越大,检测时间越长,效率越低等问题,在研究了Miller-Rabin算法基础之上,通过加入预处理过程,对原算法进行了细致地优化,减少了原算法中幂模运算的次数,从而大大提高了对于素数的检测速度.     

一种快速的强素数生成方法

针对传统的大素数生成方法需进行较复杂的模幂运算,从而导致运算速度较慢的缺陷,本文基于Miller-Rabin概率性素数检测法提出了一种大素数生成的优化方法,有效地提高了寻找大素数的速度。基于此优化方法,提出了一种新的强素数生成算法,该方法根据强素数的特征,用自顶向下的方法来生成强素数,算法简单、易实现,满足RSA算法安全性的需求。     

一种素数产生算法

素数判定是许多公钥密码算法中的一个重要环节,当前在密码算法中所使用的素性测试方法都是概率素数测试法。本文提出一种有效素数产生算法,该算法能在较快时间内产生任意比特长、从理论可以证明的素数。     

人工蜂群优化支持向量机算法在网络安全中的应用

针对支持向量机(SVM)性能的影响,探讨了人工蜂群算法(ABC)对SVM参数优化方法,建立了SVM参数优化模型,并将其用于网络安全中的网络入侵模型中.采用KDD 1999数据集进行仿真实验,验证了方法的有效性,结果表明,与遗传算法等传统优化算法相比,ABC优化的SVM有效地降低运行时间,可以获得更高的网络入侵检测率.     

多位高精度素数表及其计算机的实现技术

论述素数产生的理论价值与应用意义。着重介绍了十进制多位素数表的计算机实现技术,以及笔者所在的“大数分解与素性检测支撑工具集成软件的研究”课题组就多位素数表和π(10~9)之值进行研究而获得的精确计算结果,并对现有的某些中外密码学、数论专著中关于π(10~9)的引用值提出了修正数据及其印证数据。     

自适应相位旋转的量子菌群算法

量子菌群算法是将量子计算与菌群觅食优化算法相融合而得到的一种量子智能算法,但该算法存在鲁棒性比较差和寻优时间比较长的缺陷。为解决该问题,本文设计了一种旋转相位自适应调整的量子旋转门,并用其完成细菌的趋化操作,提出了一种自适应相位旋转的量子菌群算法。通过16个不同类型的标准测试函数对其优化性能进行研究,统计结果表明该算法在低维时,对于多种种类的测试函数,在收敛精度和稳定性上都要优于改进前的量子菌群算法,且优化结果要明显优于经典的菌群觅食优化算法和量子遗传算法。进一步研究表明,在达到指定收敛精度的情况下,该算法的平均收敛概率是最高的,平均运行时间和平均迭代步数是最短的。而在高维情况下,该算法则对碗状和碟状类型的测试函数比较适用。      

基于串并结合策略的SCMA多用户检测

稀疏码分多址接入（SCMA）是促进第五代移动通信系统发展的重要无线空口技术支撑,能够满足海量连接的需求。针对上行SCMA通信系统接收端使用的基于串行消息传递算法（MPA）的多用户检测迭代运行时间长,导致系统时延的问题,提出一种串并结合SCMA多用户检测算法,充分融合了串并行消息传递特点。仿真结果表明,相比串行MPA多用户检测算法,所提算法可降低系统的复杂度,且每轮迭代运行时间减少,从而减小了时延,实现了误比特率性能与系统时延、系统复杂度之间理想的平衡。     

基于Snort的模式匹配算法比较

字符串模式匹配算法是入侵检测的的关键,为了测试BM,BMG,AC,AC-BM四种算法性能,基于Snort的模式匹配算法在Snort入侵检测系统下测量了四种算法的运行时间和内存消耗。实验结果表明当模式数量较大时AC,AC—BM算法运行时间小于BM和BMG算法,但内存消耗相对较大;当模式数量较少时,BM和BMG算法优于AC,AC—BM算法。     

改进蚁群优化算法的图像边缘检测

为了解决图像边缘检测中的噪声问题,并提升检测效率与检测效果,提出改进蚁群优化算法的图像边缘检测方法。所提方法改进了传统蚁群优化算法直接在像素域进行迭代的边缘检测过程,其将蚂蚁分为探测蚁和寻路蚁,寻路蚁采用数据结构控制思想在原图像上随机选择迭代路线,根据蚂蚁移动角度设置像素点结构搜索路线,在所经过的每个像素点上进行附近像素点结构搜索,快速获取整体图像边缘检测信息,再利用探测蚁将寻路蚁给出的结果进行蚂蚁外激素检测,完成对检测效率与检测效果的改进。实验结果证明,相比传统蚁群优化算法,改进蚁群优化算法在图像边缘检测的效率与效果上均有很大提高。     

一种不需要计算量化失真的快速码书训练算法

该文利用LBG算法迭代过程中质心序列收敛特性,提出了一种快速算法。它的基本思想是,直接去掉LBG算法中量化失真计算,用质心序列收敛作停止条件。我们用典型的测试图像Lena做实验,实验结果表明,该算法与著名的LBG算法的PSNR相差小于0.1dB,但它的运行时间至少比LBG的运行时间少一半。     

Fast generation of prime numbers and secure public-key cryptographic parameters

A very efficient recursive algorithm for generating nearly random provable primes is presented. The expected time for generating a prime is only slightly greater than the expected time required for generating a pseudoprime of the same size that passes the Miller-Rabin test for only one base. Therefore our algorithm is even faster than algorithms presently used for generating only pseudoprimes because several Miller-Rabin tests with independent bases must be applied for achieving a sufficient confidence level. Heuristic arguments suggest that the generated primes are close to uniformly distributed over the set of primes in the specified interval.Security constraints on the prime parameters of certain cryptographic systems are discussed, and in particular a detailed analysis of the iterated encryption attack on the RSA public-key cryptosystem is presented. The prime-generation algorithm can easily be modified to generate nearly random primes or RSA-moduli that satisfy these security constraints. Further results described in this paper include an analysis of the optimal upper bound for trial division in the Miller-Rabin test as well as an analysis of the distribution of the number of bits of the smaller prime factor of a random k-bit RSA-modulus, given a security bound on the size of the two primes.Some results of this paper were presented at EUROCRYPT '89, Houthalen, Belgium, April 10–13, 1989 [55].     

An Extended Quadratic Frobenius Primality Test with Average- and Worst-Case Error Estimate

We present an Extended Quadratic Frobenius Primality Test (EQFT), which is related to the Miller-Rabin test and to several other known probabilistic tests. EQFT takes time equivalent to about two or three Miller-Rabin tests, but has a much smaller error probability, namely 256/331776^t for t iterations of the test in the worst case. We also give bounds on the average-case behaviour of the test: consider the algorithm that repeatedly chooses random odd k bit numbers, subjects them to t iterations of our test and outputs the first one found that passes all tests. We obtain numeric upper bounds for the error probability of this algorithm as well as a general closed expression bounding the error. For instance, it is at most 2^-155 for k = 500, t = 2. Compared with earlier similar results for the Miller-Rabin test, the results indicate that our test in the average case has the effect of nine Miller-Rabin tests. We also give bounds for the error in case a prime is sought by incremental search from a random starting point.     

The generation of random numbers that are probably prime

In this paper we make two observations on Rabin's probabilistic primality test. The first is a provocative reason why Rabin's test is so good. It turned out that a single iteration has a nonnegligible probability of failing only on composite numbers that can actually be split in expected polynomial time. Therefore, factoring would be easy if Rabin's test systematically failed with a 25% probability on each composite integer (which, of course, it does not). The second observation is more fundamental because it is not restricted to primality testing: it has consequences for the entire field of probabilistic algorithms. The failure probability when using a probabilistic algorithm for the purpose of testing some property is compared with that when using it for the purpose of obtaining a random element hopefully having this property. More specifically, we investigate the question of how reliable Rabin's test is when used to generate a random integer that is probably prime, rather than to test a specific integer for primality.Supported in part by NSERC grant A4107. Part of the research was performed while this author was at the CWI, Amsterdam.Supported in part by an NSERC Posgraduate Scholarship. Part of the research was performed while this author was at the Université de Montréal.Supported in part by an NSF grant.     

序贯概率比检验法在导航精度试飞中的应用

以往导航精度试飞采用基于参数估计理论的误差统计法,须完成规定的试飞架次才能得出试飞结论。这里根据假设检验理论总结出序贯概率比检验法,在给定置信度和误差概率时,求出导航精度的拒绝域、接收域和观察域;当试验曲线收敛于接收域时即可提前结束试飞,达到节省架次的目的。通过应用表明该方法不但适用于导航系统,对其他系统也具参考价值。     

Classification of quadrature amplitude modulated (QAM) signals via sequential probability ratio test (SPRT)

A novel approach to automatic classification of quadrature amplitude modulated (QAM) signals is presented in this research. Modulation classification has been traditionally treated as a hypothesis test problem with input signals of a fixed sample size. By formulating it as a variable sample size test problem, we propose a new classification algorithm based on the sequential probability ratio test (SPRT). It is demonstrated that the new approach has several important merits, including ease of error rate control, lower computational complexity and lower decision delay.     

Note on the generation of p/sub 0/ for RSA keysets

A note has been published by Clayden (1988) regarding the value p/sub 0/=s/sup r-1/(mod rs)-r/sup s-1/(mod rs) (where r and s are distinct primes). This value of p/sub 0/ can be used in the generation of strong primes for the RSA public key cryptosystem. In another paper, Gordon (1984) requires whichever of p/sub 0/ or p/sub 0/+rs is odd to generate the strong prime. Clayden's note gives a proof of the fact that it is always the value of p/sub 0/+rs that is odd. He also commented that, as this is not necessarily the case if either r or s is not prime, then the oddness of p/sub 0/+rs could be used as an extra test for the primality of both r and s.<>     

An Analog Checker with Input-Relative Tolerance for Duplicate Signals

We discuss the design of a novel analog checker that monitors two duplicate signals and provides a digital error indication when their absolute difference is unacceptably large. The key feature of the proposed checker is that it establishes a test criterion that is dynamically adapted to the magnitude of its input signals, thus enhancing the accuracy of assessing their relative discrepancy. Consequently, when this checker is utilized in concurrent error detection, it diminishes the probability of both false negatives and false positives. Likewise, when employed for off-line test purposes, the checker supports both high yield and high fault coverage. In contrast, checkers implementing a static test criterion may only be tuned to achieve efficiently one of the aforementioned objectives.     

关于椭圆曲线素性证明

文章给出了由Atkin提出的一种非常有效的素性测试方法即椭圆曲线素性证明算法,详细讨论了具体实施该算法的所有细节,而且通过在计算机上编程获得了其软件实现,并用该软件来测试一般的大整数的素性,取得了很好的效果。为了清晰地展示该算法的过程,文章在最后给出了一个详细的算例。     

Aliasing properties of circular MISRs

In built-in self-test for logic circuits, test data reduction can be achieved using a linear feedback shift register. The probability of this data reduction allowing a faulty circuit to be declared good is the probability of aliasing. This article examines aliasing in circular multiple-input shift-registers (MISRs), under the independent bit error model. We present an exact closed form expression for aliasing probability without assuming equiprobable bit error probabilities. We show that the aliasing probability can be much larger than its asymptotic value. Irrespective of the register length we prove that for a circular MISR, when two inputs are used for testing out ofm possible inputs, high minimum spatial separations between inputs result in low aliasing probabilities. We also show that for equiprobable errors an m-bit circular MISR can be replaced with a set ofm single-bit MISRs without affecting aliasing probability or adding any additional logic, to reduce the propagation delay due to feedback path. The above features can be used as criteria for the MISR design.     

Primality Proving via One Round in ECPP and One Iteration in AKS

In August 2002, Agrawal, Kayal and Saxena announced the first deterministic and polynomial-time primality-testing algorithm. For an input n, the Agarwal-Kayal-Saxena (AKS) algorithm runs in time (heuristic time ). Verification takes roughly the same amount of time. On the other hand, the Elliptic Curve Primality Proving algorithm (ECPP) runs in random heuristic time (some variant has heuristic time complexity ) and generates certificates which can be easily verified. However, it is hard to analyze the provable time complexity of ECPP even for a small portion of primes. More recently, Berrizbeitia gave a variant of the AKS algorithm, in which some primes (of density ) cost much less time to prove than a general prime does. Building on these celebrated results, this paper explores the possibility of designing a randomized primality-proving algorithm based on the AKS algorithm. We first generalize Berrizbeitia's algorithm to one which has higher density ( ) of primes whose primality can be proved in time complexity . For a general prime, one round of ECPP is deployed to reduce its primality proof to the proof of a random easily proved prime, thus we achieve heuristic time complexity for all primes.