论Miller-Rabin算法预处理的局限性

信息安全领域中极为重要的公钥密码体制的关键在于生成两个大素数,目前虽已有多项式运行时间的确定性素性检测算法AKS算法,可惜运行时间还达不到实用要求,故还是快速实用的概率性素性检测算法Miller-Rabin算法为主流,但其有一点一直被忽略——Miller-Rabin算法直接控制的其实是误判率而不是出错率,而后者才是真正需要降低的。对此做了详细分析,同时考察一些利用素数分布特性的预处理措施在降低出错率方面的效果,并分析了这一类优化的效果极限,否定了其必要性,相比之下,针对算法底层的优化更为直接有效。     

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].     

A comparison of known codes, random codes, and the best codes

This paper calculates new bounds on the size of the performance gap between random codes and the best possible codes. The first result shows that, for large block sizes, the ratio of the error probability of a random code to the sphere-packing lower bound on the error probability of every code on the binary symmetric channel (BSC) is small for a wide range of useful crossover probabilities. Thus even far from capacity, random codes have nearly the same error performance as the best possible long codes. The paper also demonstrates that a small reduction k-k˜ in the number of information bits conveyed by a codeword will make the error performance of an (n,k˜) random code better than the sphere-packing lower bound for an (n,k) code as long as the channel crossover probability is somewhat greater than a critical probability. For example, the sphere-packing lower bound for a long (n,k), rate 1/2, code will exceed the error probability of an (n,k˜) random code if k-k˜>10 and the crossover probability is between 0.035 and 0.11=H^-1(1/2). Analogous results are presented for the binary erasure channel (BEC) and the additive white Gaussian noise (AWGN) channel. The paper also presents substantial numerical evaluation of the performance of random codes and existing standard lower bounds for the BEC, BSC, and the AWGN channel. These last results provide a useful standard against which to measure many popular codes including turbo codes, e.g., there exist turbo codes that perform within 0.6 dB of the bounds over a wide range of block lengths     

New bounds and constructions for authentication/secrecy codes with splitting

We investigate authentication codes with splitting, using the mathematical model introduced by Simmons. Besides an overview of the existing bounds, we obtain some new bounds for the probability of deception of the transmitter/ receiver in case of an impersonation or substitution game. We also prove some new bounds for a spoofing attack of order L. Further, we give several new constructions for authentication/secrecy codes with splitting, derived from finite incidence structures such as partial geometries and affine resolvable designs. In some of these codes the bounds are attained with equality.     

Distributed In-Network Channel Decoding

Average log-likelihood ratios (LLRs) constitute sufficient statistics for centralized maximum-likelihood block decoding as well as for a posteriori probability evaluation which enables bit-wise (possibly iterative) decoding. By acquiring such average LLRs per sensor it becomes possible to perform these decoding tasks in a low-complexity distributed fashion using wireless sensor networks. At affordable communication overhead, the resultant distributed decoders rely on local message exchanges among single-hop neighboring sensors to achieve iteratively consensus on the average LLRs per sensor. Furthermore, the decoders exhibit robustness to non-ideal inter-sensor links affected by additive noise and random link failures. Pairwise error probability bounds benchmark the decoding performance as a function of the number of consensus iterations. Interestingly, simulated tests corroborating the analytical findings demonstrate that only a few consensus iterations suffice for the novel distributed decoders to approach the performance of their centralized counterparts.     

Computation of random coding exponent functions

Gallager's exponent functionE_{circ}, (rho,p)plays a crucial role in the derivation of bounds for coding error probabilities. An iterative algorithm for computing the maximum ofE_{circ} (rho,p)over the set of input probability distributions is presented. The algorithm is similar to that of Arimoto and Blahut for computing channel capacity. It is shown that the approximation error is at most inversely proportional to the number of iterations. A similar iterative algorithm for computing the source code reliability-rate function also is presented.     

Generalized minimum distance decoding

We introduce a new distance measure which permits likelihood information to be used in algebraic minimum distance decoding techniques. We give an efficient decoding algorithm, and develop exponential bounds on the probability of not decoding correctly. In one application, this technique yields the same probability of error as maximum likelihood decoding.     

On the performance of peaky capacity-achieving signaling on multipath fading channels

We analyze the error probability of peaky signaling on bandlimited multipath fading channels, the signaling strategy that achieves the capacity of such channels in the limit of infinite bandwidth under an average power constraint. We first derive an upper bound for general fading, then specialize to the case of Rayleigh fading, where we obtain upper and lower bounds that are exponentially tight and, therefore, yield the reliability function. These bounds constitute a strong coding theorem for the channel, as they not only delimit the range of achievable rates, but also give us a relationship among the error probability, data rate, bandwidth, peakiness, and fading parameters, such as the coherence time. They can be used to compare peaky signaling systems to other large bandwidth systems over fading channels, such as ultra-wideband radio and wideband code-division multiple access. We find that the error probability decreases slowly with the bandwidth W; under Rayleigh fading, the error probability varies roughly as W/sup -/spl alpha//, where /spl alpha/>0. With parameters typical of indoor wireless situations, we study the behavior of the upper and lower bounds on the error probability and the reliability function numerically.     

随机周期序列k错线性复杂度的方差估计

周期序列的k错线性复杂度是衡量流密码系统的安全性能的一个重要指标.本文首次给出了随机周期序列k错线性复杂度方差的一个表达公式,同时给出了一些情形下的随机周期序列k错线性复杂度方差的上下界的估计和特定情形下的精确结果.     

A View of Gaussian Elimination Applied to Early-Stopped Berlekamp–Massey Algorithm

In this paper, we adopt a restricted Gaussian elimination on the Hankel structured augmented syndrome matrix to reinterpret an early-stopped version of the Berlekamp-Massey algorithm in which only (t + e) iterations are needed to be performed for the decoding of BCH codes up to t errors, where e is the number of errors actually occurred with e les t, instead of the It iterations required in the conventional Berlekamp-Massey algorithm. The minimality of (t + e) iterations in this early-stopped Berlekamp-Massey (ESBM) algorithm is justified and related to the subject of simultaneous error correction and detection in this paper. We show that the multiplicative complexity of the ESBM algorithm is upper bounded by (te + e² - 1)foralle les t and except for a trivial case, the ESBM algorithm is the most efficient algorithm for finding the error-locator polynomial.     

LDPC Decoding by Failed Check Nodes for Serial Concatenated Code

The use of serial concatenated codes is an effective technique for alleviating the error floor phenomenon of low‐density parity‐check (LDPC) codes. An enhanced sum–product algorithm (SPA) for LDPC codes, which is suitable for serial concatenated codes, is proposed in this paper. The proposed algorithm minimizes the number of errors by using the failed check nodes (FCNs) in LDPC decoding. Hence, the error‐correcting capability of the serial concatenated code can be improved. The number of FCNs is simply obtained by the syndrome test, which is performed during the SPA. Hence, the decoding procedure of the proposed algorithm is similar to that of the conventional algorithm. The error performance of the proposed algorithm is analyzed and compared with that of the conventional algorithm. As a result, a gain of 1.4 dB can be obtained by the proposed algorithm at a bit error rate of 10^?8. In addition, the error performance of the proposed algorithm with just 30 iterations is shown to be superior to that of the conventional algorithm with 100 iterations.     

Optimal simultaneous detection and estimation under a false alarmconstraint

This paper addresses the problem of finite sample simultaneous detection and estimation which arises when estimation of signal parameters is desired but signal presence is uncertain. In general, a joint detection and estimation algorithm cannot simultaneously achieve optimal detection and optimal estimation performance. We develop a multihypothesis testing framework for studying the tradeoffs between detection and parameter estimation (classification) for a finite discrete parameter set. Our multihypothesis testing problem is based on the worst case detection and worst case classification error probabilities of the class of joint detection and classification algorithms which are subject to a false alarm constraint. This framework leads to the evaluation of greatest lower bounds on the worst case decision error probabilities and a construction of decision rules which achieve these lower bounds. For illustration, we apply these methods to signal detection, order selection, and signal classification for a multicomponent signal in noise model. For two or fewer signals, an SNR of 3 dB and signal space dimension of N=10 numerical results are obtained which establish the existence of fundamental tradeoffs between three performance criteria: probability of signal detection, probability of correct order selection, and probability of correct classification. Furthermore, based on numerical performance comparisons between our optimal decision rule and other suboptimal penalty function methods, we observe that Rissanen's (1978) order selection penalty method is nearly min-max optimal in some nonasymptotic regimes     

Error Probability of Asynchronous Spread Spectrum Multiple Access Communication Systems

Several approaches for the evaluation of upper and lower bounds on error probability of asynchronous spread spectrum multiple access communication systems are presented. These bounds are obtained by utilizing an isomorphism theorem in the theory of moment spaces. From this theorem, we generate closed, compact, and convex bodies, where one of the coordinates represents error probability, while the other coordinate represents a generalized moment of the multiple access interference random variable. Derivations for the second moment, fourth moment, single exponential moment, and multiple exponential moment are given in terms of the partial cross correlations of the codes used in the system. Error bounds based on the use of these moments are obtained. By using a sufficient number of terms in the multiple exponential moment, upper and lower error bounds can be made arbitrarily tight. In that case, the error probability equals the multiple exponential moment of the multiple access interference random variable. An example using partial cross correlations based on codes generated from Gold's method is presented.     

Intersymbol Interference Performance of Systems with Correlated Digital Signals

For a digital system with correlated digital symbols, we derive upper and lower bounds on the probability of error when the system is subject to intersymbol interference and additive Gaussian noise. The bounds are expressed in terms of the error probability obtained with a finite number of intersymbol interference terms and some parameters associated with the remainder terms. We also show that the difference between the upper and lower bounds can be made arbitrarily small and that the error probability can be computed to any desired degree of accuracy. We give some examples to illustrate the method.     

Improving the multicommodity flow rates with network codes for two sources

In this work we introduce a construction and analysis of network codes for two sources. The region of achievable rates for this problem is still unknown. The scheme we suggest is based on modifying the multicommodity flow solution and thus improving the achievable rate region, w.r.t the uncoded case. The similarity to the flow problem allows our method to be implemented distributively. We show how the construction algorithm can be combined with distributed backpressure routing algorithms for wireless ad-hoc networks. For both the nondistributed case and the distributed case, the computational complexity of our algorithm for network coding is comparable to that of the parallel multicommodity flow problem. We provide non trivial upper and lower bounds on the performance of our scheme, using random coding techniques.     

Maximum error modeling for fault-tolerant computation using maximum a posteriori (MAP) hypothesis

The application of current generation computing machines in safety-centric applications like implantable biomedical chips and automobile safety has immensely increased the need for reviewing the worst-case error behavior of computing devices for fault-tolerant computation. In this work, we propose an exact probabilistic error model that can compute the maximum error over all possible input space in a circuit-specific manner and can handle various types of structural dependencies in the circuit. We also provide the worst-case input vector, which has the highest probability to generate an erroneous output, for any given logic circuit. We also present a study of circuit-specific error bounds for fault-tolerant computation in heterogeneous circuits using the maximum error computed for each circuit. We model the error estimation problem as a maximum a posteriori (MAP) estimate [28] and [29], over the joint error probability function of the entire circuit, calculated efficiently through an intelligent search of the entire input space using probabilistic traversal of a binary Join tree using Shenoy-Shafer algorithm [20] and [21]. We demonstrate this model using MCNC and ISCAS benchmark circuits and validate it using an equivalent HSpice model. Both results yield the same worst-case input vectors and the highest percentage difference of our error model over HSpice is just 1.23%. We observe that the maximum error probabilities are significantly larger than the average error probabilities, and provides a much tighter error bounds for fault-tolerant computation. We also find that the error estimates depend on the specific circuit structure and the maximum error probabilities are sensitive to the individual gate failure probabilities.     

Maximum likelihood estimation of constellation vectors for blindseparation of co-channel BPSK signals and its performance analysis

In this paper, we present a method for blind separation of co-channel BPSK signals arriving at an antenna array. This method consists of two parts: the maximum likelihood constellation estimation and assignment. We show that at high SNR, the maximum likelihood constellation estimation is well approximated by the smallest distance clustering algorithm, which we proposed earlier on heuristic grounds. We observe that both these methods for estimating the constellation vectors perform very well at high SNR and nearly attain Cramer-Rao bounds. Using this fact and noting that the assignment algorithm causes negligible error at high SNR, we derive upper bounds on the probability of bit error for the above method at high SNR. These upper bounds fall very rapidly with increasing SNR, showing that our constellation estimation-assignment approach is very efficient. Simulation results are given to demonstrate the usefulness of the bounds     

Bounds on the maximum-likelihood decoding error probability oflow-density parity-check codes

We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent     

Improved bounds on the word error probability of RA(2) codes with linear-programming-based decoding

This paper deals with the linear-programming-based decoding algorithm of Feldman and Karger for repeat-accumulate "turbo-like" codes. We present a new structural characterization that captures the event that decoding fails. Based on this structural characterization, we develop polynomial algorithms that, given an RA(2) code, compute upper and lower bounds on the word error probability P/sub w/ for the binary-symmetric and the additive white Gaussian noise (AWGN) channels. Our experiments with an implementation of these algorithms for bounding P/sub w/ demonstrate in many interesting cases an improvement in the upper bound on the word error probability by a factor of over 1000 compared to the bounds by Feldman et al.. The experiments also indicate that the improvement in upper bound increases as the codeword length increases and the channel noise decreases. The computed lower bounds on the word error probability in our experiments are roughly ten times smaller than the upper bound.     

Design and analysis of codes with distance 4 and 6 minimizing the probability of decoder error

The problem of minimization of the decoder error probability is considered for shortened codes of dimension 2 ^m with distance 4 and 6. We prove that shortened Panchenko codes with distance 4 achieve the minimal probability of decoder error under special form of shortening. This shows that Hamming codes are not the best. In the paper, the rules for shortening Panchenko codes are defined and a combinatorial method to minimize the number of words of weight 4 and 5 is developed. There are obtained exact lower bounds on the probability of decoder error and the full solution of the problem of minimization of the decoder error probability for [39,32,4] and [72,64,4] codes. For shortened BCH codes with distance 6, upper and lower bounds on the number of minimal weight codewords are derived. There are constructed [45,32,6] and [79,64,6] BCH codes with the number of weight 6 codewords close to the lower bound and the decoder error probabilities are calculated for these codes. The results are intended for use in memory devices.