Fast exponentiation by folding the signed-digit exponent in half

For modern cryptographic systems, the public key cryptosystem such as RSA requires modular exponentiation (M ^E mod?N). The M, E and N are either as large as the 1024-bit integers or even larger, it is not a very good idea to directly compute M ^E mod?N. Recently, there are many techniques have been invented to solve the time-consuming computations of such time-consuming modular exponentiation. Among these useful algorithms, the “binary (square-and-multiply) algorithm” reduces the amount of modulo multiplications. As the “signed-digit representation algorithm” has the property of the nonzero digit occurrence probability equals to 1/3, taking this advantage, this method can more effectively decrease the amount of modular multiplications. Moreover, by using the technique of recording the common parts in the folded substrings, the “folding-exponent algorithm” can improve the efficiency of the binary algorithm, thus can further decrease the computational complexity of modular exponentiation. In this paper, a new modular exponentiation algorithm is proposed which based on the binary algorithm, signed-digit representation, and the folding-exponent technique. By using the parallel processing technique, in our proposed method, the modular multiplications and modular squaring can be executed in parallel, and thus lower down the computational complexity to k?+?3 multiplications. As modular squaring operation over GF(2 ⁿ ) is carried out by a simple cyclic right shift operation, the computational complexity of our proposed method can be further reduced to 29k/36?+?3 multiplications.     

Parallel exponentiation using common-multiplicand-multiplication and signed-digit-folding techniques

An efficient computation of the modular exponentiations C?=?M^E mod N is very useful for public-key cryptosystems. In this paper, an efficient parallel modular exponentiation algorithm is proposed based on both the common-multiplicand-multiplication (CMM) and signed-digit-folding (SDF) techniques. The ‘minimal-signed-digit (SD) recoding algorithm’ has less occurrence probability of the nonzero digit than the binary number representation. Taking this advantage, we can effectively decrease the amount of modular multiplications. By dividing the bit string of the minimal-SD recoding exponent E into three equal-length parts and by using the technique of recording the common parts in the folded substrings, the ‘folding-exponent algorithm’ can improve the efficiency of the binary algorithm, thus it can further decrease the computational complexity of modular exponentiation. As the modular squaring operation in GF(2 ⁿ ) over the normal basis can be done by a simple shift operation, the modular multiplications and the modular squaring operations in our proposed CMM–SDF algorithm can be executed in parallel. By using our proposed parallel CMM–SDF algorithm, we can obtain the optimal overall computational complexity as 0.689k?+?11 multiplications by folding the minimal-SD recoding exponent E exactly one-time in SD radix-2 recoding system, where k denotes the digit-length of the exponent and n denotes the folding time of the exponent.     

Compact Recognizers of Episode Sequences

Given two strings X=a₁…a_n and P=b₁…b_m over an alphabet Σ, the problem of testing whether P occurs as a subsequence of X is trivially solved in linear time. It is also known that a simple O(n log |Σ|) time preprocessing of X makes it easy to decide subsequently, for any P and in at most |P| log |Σ| character comparisons, whether P is a subsequence of X. These problems become more complicated if one asks instead whether P occurs as a subsequence of some substring Y of X of bounded length. This paper presents an automaton built on the textstring X and capable of identifying all distinct minimal substrings Y of X having P as a subsequence. By a substring Y being minimal with respect to P, it is meant that P is not a subsequence of any proper substring of Y. For every minimal substring Y, the automaton recognizes the occurrence of P having the lexicographically smallest sequence of symbol positions in Y. It is not difficult to realize such an automaton in time and space O(n²) for a text of n characters. One result of this paper consists of bringing those bounds down to linear or O(n log n), respectively, depending on whether the alphabet is bounded or of arbitrary size, thereby matching the corresponding complexities of automata constructions for offline exact string searching. Having built the automaton, the search for all lexicographically earliest occurrences of P in X is carried out in time O(∑_i=1^mrocc_i·i) or O(n+∑_i=1^mrocc_i·i· log n), depending on whether the alphabet is fixed or arbitrary, where rocc_i is the number of distinct minimal substrings of X having b₁…b_i as a subsequence (note that each such substring may occur many times in X but is counted only once in the bound). All log factors appearing in the above bounds can be further reduced to log log by resorting to known integer-handling data structures.     

Elements of small norm in Shanks’ cubic extensions of imaginary quadratic fields

Let be an imaginary quadratic number field with ring of integers Z_k and let k(α) be the cubic extension of k generated by the polynomial f_t(x)=x³−(t−1)x²−(t+2)x−1 with tZ_k. In the present paper we characterize all elements γZ_k[α] with norms satisfying |N_k(α)/k|≤|2t+1| for |t|≥14. This generalizes a corresponding result by Lemmermeyer and Pethő for Shanks’ cubic fields over the rationals.     

Empirical Bayes estimation of the scale parameter in a Pareto distribution

Let f(xθ) = αθ^αx^−(α+1)I(x>θ) be the pdf of a Pareto distribution with known shape parameter α>0, and unknown scale parameter θ. Let {(X_i, θ_i)} be a sequence of independent random pairs, where X_i's are independent with pdf f(xα_i), and θ_i are iid according to an unknown distribution G in a class of distributions whose supports are included in an interval (0, m), where m is a positive finite number. Under some assumption on the class and squared error loss, at (n + 1)th stage we construct a sequence of empirical Bayes estimators of θ_n+1 based on the past n independent observations X₁,…, X_n and the present observation X_n+1. This empirical Bayes estimator is shown to be asymptotically optimal with rate of convergence O(n^−1/2). It is also exhibited that this convergence rate cannot be improved beyond n^−1/2 for the priors in class .     

A Class of Composite Codes with Minimum Distance 8

We consider linear composite codes based on the |a+x|b+x|a+b+x| construction. For m 3 and r 4m + 3, we propose a class of linear composite [3 · 2 ^m , 3 · 2 ^m – r, 8] codes, which includes the [24,12,8] extended Golay code. We describe an algebraic decoding algorithm, which is valid for any odd m, and a simplified version of this algorithm, which can be applied for decoding the Golay code. We give an estimate for the combinational-circuit decoding complexity of the Golay code. We show that, along with correction of triple independent errors, composite codes with minimum distance 8 can also correct single cyclic error bursts and two-dimensional error bytes.     

Montgomery exponent architecture based on programmable cellular automata

This study presents an efficient exponent architecture for public-key cryptosystems using Montgomery multiplication based on programmable cellular automata (PCA). Multiplication is the key operation in implementing circuits for cryptosystem, as the process of encrypting and decrypting a message requires modular exponentiation which can be decomposed into multiplications. Efficient multiplication algorithm and simple architecture are the key for implementing exponentiation. Thus we employ Montgomery multiplication algorithm and construct simple architecture based on irreducible all one polynomial (AOP) in GF(2^m). The proposed architecture has the advantage of high regularity and a reduced hardware complexity based on combining the characteristics of the irreducible AOP and PCA. The proposed architecture can be efficiently used for public-key cryptosystem.     

Finding the Extrema of a Distributed Multiset

We consider the problem of finding the extrema of a distributed multiset in a ring, that is, of determining the minimum and the maximum values,x_minandx_max, of a multisetX= {x₀,x₂, ...,x_n−1} whose elements are drawn from a totally ordered universeUand stored at thenentities of a ring network. This problem is unsolvable if the ring size is not known to the entities, and it has complexity Θ(n²) in the case of asynchronous rings of known size. We show that, in synchronous rings of known size, this problem can always be solved inO((c+ logn) ·n) bits andO(n·c·x^1/c) time for any integerc> 0, wherex= Max{|x_min|, |x_max|}. The previous solutions requiredO(n²) bits and the same amount of time. Based on these results, we also present a bit-optimal solution to the problem of finding the multiplicity of the extrema.     

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     

Existence and efficient construction of fast Fourier transforms on supersolvable groups

The linear complexityL _K(A) of a matrixA over a fieldK is defined as the minimal number of additions, subtractions and scalar multiplications sufficient to evaluateA at a generic input vector. IfG is a finite group andK a field containing a primitive exp(G)-th root of unity,L _K(G):= min{L _K(A)|A a Fourier transform forKG} is called theK-linear complexity ofG. We show that every supersolvable groupG has amonomial Fourier Transform adapted to a chief series ofG. The proof is constructive and gives rise to an efficient algorithm with running timeO(|G|²log|G|). Moreover, we prove that these Fourier transforms are efficient to evaluate:L _K(G)8.5|G|log|G| for any supersolvable groupG andL _K(G)1.5|G|log|G| for any 2-groupG.     

A variable-precision square root implementation for field programmable gate arrays

Applications requiring variable-precision arithmetic often rely on software implementations because custom hardware is either unavailable or too costly to build. By using the flexibility of the Xilinx XC4010 field programmable gate arrays, we present a hardware implementation of square root that is easily tailored to any desired precision. Our design consists of three types of modules: a control logic module, a data path module to extend the precision in 4-bit increments, and an interface module to span multiple chips. Our data path design avoids the common problem of large fan-out delay in the critical path. Cycle time is independent of precision, and operation latency can be independent of interchip communication delays.Notation S_j square root digit of weight 2^–j - S _j {–1, 0, 1} - S[j] computed square root value as of stepj - S _j ^s sign bit in the representation ofS _j in sign and magnitude form - S _j ^m magnitude bit in the representation ofS _j in sign and magnitude form - w[j] residual at stepj in two's complement carry-save representation - a sum vector in the carry-save representation of 2w[j] - b carry vector in the carry-save representation of 2w[j] - a _i bit of weight 2^–i in the sum vector,a - b_i bit of weight 2^–i in the carry vector,b - T[j]=–S[j – 1]s_j – s _j ² 2^–(j+1) T _i bit of weight 2^–i inT     

High-Performance Hardware of the Sliding-Window Method for Parallel Computation of Modular Exponentiations

Modular exponentiation is a basic operation in various applications, such as cryptography. Generally, the performance of this operation has a tremendous impact on the efficiency of the whole application. Therefore, many researchers have devoted special interest to providing smart methods and efficient implementations for modular exponentiation. One of these methods is the sliding-window method, which pre- processes the exponent into zero and non-zero partitions. Zero partitions allow for a reduction of the number of modular multiplications required in the exponentiation process. In this paper, we devise a novel hardware for computing modular exponentiation using the sliding-window method. The partitioning strategy used allows variable-length non-zero partitions, which increases the average number of zero partitions and so decreases that of non-zero partitions. It performs the partitioning process in parallel with the pre-computation step of the exponent so no overhead is introduced. The implementation is efficient when compared against related existing hardware implementations.     

Solving Systems of Difference Constraints Incrementally

Difference constraints systems consisting of inequalities of the form x _i - x _j b _i,j occur in many applications, most notably those involving temporal reasoning. Often, it is necessary to maintain a solution to such a system as constraints are added, modified, and deleted. Existing algorithms handle modifications by solving the resulting system anew each time, which is inefficient. The best known algorithm to determine if a system of difference constraints is feasible (i.e., if it has a solution) and to compute a solution runs in Θ (mn) time, where n is the number of variables and m is the number of constraints. This paper presents a new efficient incremental algorithm for maintaining a solution to a system of difference constraints. As constraints are added, modified, or deleted, the algorithm determines if the new system is feasible and updates its solution. When the system becomes infeasible, the algorithm continues to process changes until it becomes feasible again, at which point a feasible solution will be produced. The algorithm processes the addition of a constraint in time O(m + n log n) and the removal of a constraint in constant time when the original system is feasible. More precisely, additions are processed in time O( || Δ || + |Δ| log|Δ| ) , where |Δ| is the number of variables whose values are changed to compute the new feasible solution, and || Δ || is the number of constraints involving the variables whose values are changed. When the original system is infeasible, the algorithm processes any change in O(m + n log n) amortized time. The new algorithm can also be used to check for the existence of negative cycles in dynamic graphs. Received September 25, 1997; revised November 16, 1997.     

The query complexity of order-finding

We consider the problem where π is an unknown permutation on {0,1,…,2ⁿ−1}, y₀{0,1,…,2ⁿ−1}, and the goal is to determine the minimum r>0 such that π^r(y₀)=1. Information about π is available only via queries that yield π^x(y) from any x{0,1,…,2^m−1} and y{0,1,…,2ⁿ−1} (where m is polynomial in n). The main resource under consideration is the number of these queries. We show that the number of queries necessary to solve the problem in the classical probabilistic bounded-error model is exponential in n. This contrasts sharply with the quantum bounded-error model, where a constant number of queries suffices.     

An efficient common-multiplicand-multiplication method to the Montgomery algorithm for speeding up exponentiation

The modular exponentiation is a common operation for scrambling secret data and is used by several public-key cryptosystems, such as the RSA scheme and DSS digital signature scheme. However, the calculations involved in modular exponentiation are time-consuming especially when performed in software. In this paper, we propose an efficient CMM-MSD Montgomery algorithm by utilizing the Montgomery modular reduction method, common-multiplicand-multiplication (CMM) method, and minimal-signed-digit (MSD) recoding technique for fast modular exponentiation. By using the technique of recording the common signed-digit representations in the grouped substrings of exponent, our algorithm can improve the efficiency of both the original CMM exponentiation algorithm and the Montgomery multiplication algorithm. The fast modular exponentiation algorithm developed in this paper can be easily implemented in general signed-digit computing machine, and is therefore well suited for parallel implementation to fast evaluating modular exponentiation. Moreover, by using the proposed CMM-MSD Montgomery algorithm, on average the total number of single-precision multiplications can be reduced by about 38.9% and 26.68% as compared with Dusse-Kaliski’s Montgomery algorithm and Ha-Moon’s Montgomery algorithm, respectively.     

Fast hardware for modular exponentiation with efficient exponent pre-processing

Modular exponentiation is an important operation in several public-key cryptosystems. It is performed using successive modular multiplications. For the sake of efficiency, one needs to reduce the total number of required modular multiplications. In this paper, we propose two efficient hardware implementations for computing modular exponentiations, which are based on the m-ary method. The m-ary method includes a power pre-computation step. The first design ignores the exponent and pre-computes all possible powers while the second takes advantage of the formation of the exponent to compute only those powers that are really necessary for the rest of the computation. As it can be expected, the implementation of the first architecture, compared with that of the second one, requires more time to complete an exponentiation. In compensation, however, the first should require less hardware area than the second. We provide a comparison of these two implementations using the performance factor, which takes into account both space and time requirements.     

One-way functions and circuit complexity

A finite function f is a mapping of {0, 1}ⁿ into {0, 1}^m{#}, where “#” is a symbol to be thought of as “undefined.” A family of finite functions is said to be one-way (in a circuit complexity sense) if it can be computed with polynomial-size circuits, but every family of inverses of these functions cannot. In this paper we show that, provided functions that are not one-to-one are allowed, one-way functions exist if and only if the satisfiability problem SAT does not have polynomial-size circuits. A family of functions f_i(x) can be checked if some family of polynomial-size circuits with inputs x and y can determine if f_i(x) = y. A family of functions f_i(x) can be evaluated if some family of polynomial-size circuits with input x can compute f_i(x). Can all families of total functions that can be checked also be evaluated? We show that this is true if and only if the nonuniform versions of the complexity classes P and UP co-UP are equal. A family of functions f_i is one-way for constant depth circuits if f_i can be computed with unbounded famin circuits of polynomial size and constant depth, but every family of inverses f_i⁻¹ cannot. We give two provably one-way functions (in fact permutaions) for constant-depth circuits. The second example has the stronger property that no bit of its inverse can be computed in polynomial size and constant depth.     

Stochastic stabilization and destabilization

It is shown in this paper that any nonlinear systems in ^d can be stabilized by Brownian motion provided |ƒ(x,t)| ≤ K|x| for some K > 0. On the other hand, this system can also be destabilized by Brownian motion if the dimension d ≥ 2. Similar results are also obtained for any given stochastic differential equation dx(t) = ƒ(x(t), t) + g(x(t), t) dW(t).