The RSA Group is Pseudo-Free

We prove, under the strong RSA assumption, that the group of invertible integers modulo the product of two safe primes is pseudo-free. More specifically, no polynomial-time algorithm can output (with non negligible probability) an unsatisfiable system of equations over the free Abelian group generated by the symbols g ₁,…,g _n , together with a solution modulo the product of two randomly chosen safe primes when g ₁,…,g _n are instantiated to randomly chosen quadratic residues. Ours is the first provably secure construction of pseudo-free Abelian groups under a standard cryptographic assumption and resolves a conjecture of Rivest (Theory of Cryptography Conference—Proceedings of TCC 2004, LNCS, vol. 2951, pp. 505–521, 2004).     

Finite multidimensional behaviors

We study finitely generated and finite systems defined by linear partial difference equations with constant coefficients in a Noetherian ring. The two notions coincide for finite rings, and we show that all finite systems exhibit certain periodicity properties. For the particular case of systems over the ring of integers modulo m?>?1, which is important in coding theory, a method is given for determining the number of trajectories, using Gr?bner basis techniques.     

Efficient architectures for modulo 2n − 2 arithmetic units

Moduli of the 2ⁿ and 2ⁿ ± 1 forms are usually employed in designs that adopt the residue number system. However, in several cases such as in finite impulse response filters and communication components, a modulo value equal to 2ⁿ ? 2 can be used. So far, modulo 2ⁿ ? 2 arithmetic units have been based either on look-up tables or on generic modulo arithmetic units. In this work, by taking advantage of the properties of modulo 2ⁿ ? 2 arithmetic, we propose efficient modulo 2ⁿ ? 2 multi-operand adder, multiplier as well as squarer architectures. The proposed circuits are based on the corresponding ones for modulo 2^n?1 ? 1 arithmetic and some simple logic. Experimental results validate that the proposed circuits achieve significant area and delay savings compared to those previously presented.     

On the Analysis of Cryptographic Assumptions in the Generic Ring Model

The generic ring model considers algorithms that operate on elements of an algebraic ring by performing only the ring operations and without exploiting properties of a given representation of ring elements. It is used to analyze the hardness of computational problems defined over rings. For instance, it is known that breaking RSA is equivalent to factoring in the generic ring model (Aggarwal and Maurer, Eurocrypt 2009). Do hardness results in the generic ring model support the conjecture that solving the considered problem is also hard in the standard model, where elements of ? _n are represented by integers modulo n? We prove in the generic ring model that computing the Jacobi symbol of an integer modulo n is equivalent to factoring. Since there are simple and efficient non-generic algorithms which compute the Jacobi symbol, this provides an example of a natural computational problem which is hard in the generic ring model, but easy to solve if elements of ? _n are given in their standard representation as integers. Thus, a proof in the generic ring model is unfortunately not a very strong indicator for the hardness of a computational problem in the standard model. Despite this negative result, generic hardness results still provide a lower complexity bound for a large class of algorithms, namely all algorithms solving a computational problem independent of a given representation of ring elements. From this point of view, results in the generic ring model are still interesting. Motivated by this fact, we also show that solving the quadratic residuosity problem generically is equivalent to factoring.     

On the Deployment of Antenna Elements in Generalized Multi-User Distributed Antenna Systems

In this paper, we focus on a generalized multi-user distributed antenna system (DAS), where the antenna elements (AEs) are divided into antenna clusters and the antenna clusters are randomly deployed in the coverage area. The mobile terminals equipped with M AEs each are supposed to be uniformly distributed in the coverage area. We are motivated to study the impact of the deployment of antenna elements on the system performance. In the model of consideration, the deployment of antenna elements is characterized by the antenna cluster size V, i.e., the number of AEs within each antenna cluster, and the distribution of the antenna clusters. With the assumption that the antenna clusters are uniformly deployed in the coverage area, the impact of the antenna cluster size V on the uplink sum rate capacity is particularly investigated. The mean square access distance (MSAD), a function of V, is proposed as a reasonable metric instead of the uplink sum rate capacity. From the analysis of the asymptotic behavior of MSAD, we derive an approximate closed-form expression for the expectation of MSAD over system topologies. Then, it is concluded that the ergodic uplink sum rate capacity can be improved due to access distance reduction by scattering AEs further only when V > M. An approximate closed-form expression for the relative variance of MSAD is also derived. And we conclude that the outage uplink sum rate capacity can be improved due to macro-diversity by scattering AEs further only when V ≤ M. In other words, when V ≤ M, the ergodic uplink sum rate capacity can not be improved by scattering AEs further, when V > M, the outage uplink sum rate capacity can not be improved by scattering AEs further. Finally, our analysis is well verified by Monte Carlo simulations.     

Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities

We show how to find sufficiently small integer solutions to a polynomial in a single variable modulo N, and to a polynomial in two variables over the integers. The methods sometimes extend to more variables. As applications: RSA encryption with exponent 3 is vulnerable if the opponent knows two-thirds of the message, or if two messages agree over eight-ninths of their length; and we can find the factors of N=PQ if we are given the high order bits of P. Received 21 December 1995 and revised 11 August 1996     

CONDITIONAL FACTORIZATION BASED ON LATTICE THEORY FOR 〈K,1〉-INTEGERS

In this paper, the integer N = p^kq is called a 〈k, 1〉-integer, if p and q are odd primes with almost the same size and k is a positive integer. Such integers were previously proposed for various cryptographic applications. The conditional factorization based on lattice theory for n-bit 〈k, 1〉-integers is considered, and there is an algorithm in time polynomial in n to factor these integers if the least significant ｜（2k - 1）n/（3k-1）（k＋1）｜ bits of p are given.     

On Polynomial Approximation of the Discrete Logarithm and the Diffie—Hellman Mapping

We obtain several lower bounds, exponential in terms of lg p , on the degrees of polynomials and algebraic functions coinciding with values of the discrete logarithm modulo a prime p at sufficiently many points; the number of points can be as little as p ^1/2 + ɛ . We also obtain improved lower bounds on the degree and sensitivity of Boolean functions on bits of x deciding whether x is a quadratic residue. Similar bounds are also proved for the Diffie—Hellman mapping g ^x → g ^x2 , where g is a primitive root of a finite field of q elements F _q . These results can be used to obtain lower bounds on the parallel arithmetic and Boolean complexity of computing the discrete logarithm and breaking the Diffie—Hellman cryptosystem. The method is based on bounds of character sums and numbers of solutions of some polynomial equations. Received 26 August 1997 and revised 29 June 1998     

Fast algorithms for erasures and error correction in redundant residue number systems

In this work, we extend the coding theory approach to error control in redundant residue number systems (RRNS). The concept of erasure correction capability in RRNS is introduced. We derive the relationship between the minimum distance and the error detection and error/erasure correction capability. New computationally efficient algorithms are derived for simultaneously correcting single errors and multiple erasures and detecting multiple errors. These algorithms reduce the computational complexity of the previously known algorithms by at least an order of magnitude. Another attractive feature of the algorithms is that all the arithmetic operations are modulo operations. Consequently, the need to process large valued integers is avoided.     

Transform decoding of BCH codes over Zm

For BCH codes with symbols from rings of residue class integers modulo m, denoted by Z_m , we introduce the analogue of Blahut's frequency domain approach for codes over finite fields and show that the problem of decoding these codes is equivalent to the minimal shift register synthesis problem over Galois rings. A minimal shift register synthesis algorithm over Galois rings is obtained by straightforward extention of the Reeds-Sloane algorithm which is for shift register synthesis over Z_m .     

Switched capacitor analog modulo integrator for application in open loop Sigma-Delta modulators

We introduce the switched capacitor analog modulo integrator, which to our knowledge is a new circuit. We introduce the amplitude modulated open loop ΣΔ modulator (OLSDM), which is an analog modulo integrator followed by a quantizer and a modulo differentiator. The mathematical equivalence between low pass ΣΔ modulators and OLSDM is explained. Behavioral simulations confirm the equivalence. The necessary circuit, a switched capacitor analog modulo integrator, is explained in detail. Behavioral level simulations in SPICE of the analog modulo integrator verify the function, and prove the concept of amplitude modulated OLSDM.     

ROM based methods for computing the squaring operation in modular rings

Signal Processing algorithms generally rely heavily on the convolution operation which in turn is multiplication intensive. However, more recently convolution algorithms based on the squaring operation as opposed to the multiplication operation have been developed. In this article we present two ROM based methods for performing the squaring operation modulo 2 ⁿ , modulo 2 ⁿ −1, or modulo 2 ⁿ +1. The performance, cost, and implementation issues of the two methods are analyzed in detail and compared against each other as well as with a traditional ROM based implementation. It is shown that both methods obtain ROM bit savings of 99.99%, for 32-bit word lengths, when compared with traditional techniques. However, one of the methods outperforms the other in all other respects such as overhead costs, of up to 99.48% savings, performance, up to about 20 times faster, and regularity and simplicity of hardware design.     

A Probable Prime Test with Very High Confidence for n ≡ 3 mod 4

Abstract. The workhorse of most compositeness tests is Miller—Rabin, which works very fast in practice, but may fail for one-quarter of all bases. We present an alternative method to decide quickly whether a large number n is composite or probably prime. Our algorithm is both based on the ideas of Pomerance, Baillie, Selfridge, and Wagstaff, and on a suitable combination of square, third, and fourth root testing conditions. A composite number n ≡ 3 mod 4 will pass our test with probability less than 1/331,000, in the worst case. For most numbers, the failure rate is even smaller. Depending on the the respective residue classes n modulo 3 and 8 , we prove a worst-case failure rate of less than 1/5,300,000, 1/480,000, and 1/331,000, respectively, for any iteration of our test. Along with some fixed precomputation, our test has running time about three times the time as for the Miller—Rabin test. Implementation can be achieved very efficiently by naive arithmetic only.     

Communication capabilities of product networks

Instead of providing separate solutions for each individual network, a unified theory is desirable to cover the study of a class of networks. Cartesian product graphs provide a common framework to investigate the performance of several individual networks. This paper addresses communication capabilities of product networks. Communication cost is generally characterized by the diameter, the average distance, the total number of paths, the traffic intensity, the saturation level, the queue length in each node, the communication delay and the network throughput. The diameter and average distance of product networks have been studied. However, no work has addressed the remaining measures for product networks. This paper presents a unified theory to evaluate the traffic intensity and the saturation level of product networks. We have theoretically computed the traffic intensity and the saturation level. Intensive simulations have been conducted to validate the analytical results and to compute the other measures for different workloads, different networks, and different network sizes. Examples of product networks that have been investigated are multidimensional meshes, multidimensional toruses, and r‐ary n‐cube networks. We have also shown that the structure (geometry) of a network is a primary factor for network high performance. For meshes and toruses, square networks present an optimal structure. While in case of an r‐ary n‐cubes, networks with higher radix outperform those with smaller radix. In particular, cross‐cubes (4‐ary n‐cube) are shown to perform better than binary cubes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Feedback decoding of fixed-point arithmetic convolutional codes

Convolutional codes defined over the integers modulo a power of two, an arithmetic structure used for fixed-point arithmetic computations, employ well-known binary convolutional codes as their underlying generators. A recursive decoding technique that exploits binary expansion components of the code symbols uses any binary decoding algorithm valid for the underlying code.     

The magnetic parameter connected with design of high quality ferrite microstrip phase shifter

It is shown that the state of magnetization of the substrate is one of the main factors affecting the properties of nonreciprocal latching ferrite microstrip phase shifter. Raising the residual magnetization of the substrate, increasing the ratioR(=4πM/4πM _s ) (4πM—the magnetization of the “latching state” of the device, 4πM _s —the saturation magnetization) are effective in reducing the insertion loss of the device, raising the effectiveness of phase shift, extending the band width, and reducing the drive power, etc. Different methods of magnetization are analysed and compared. Photographs indicating the structure and the external form of the device are given and the main performances of single-digit and multi-digit devices are also presented.     

Effect of electron and neutron bombardment on the orange luminescence spectra of not specially doped and copper-doped cadmium sulfide single crystals

CdS single crystals which were not specially doped and which were doped with copper (N _Cu=10¹⁸ cm⁻³) have been investigated. It is concluded on the basis of an analysis of the dose dependences of the orange luminescence intensity (λ _M=605 nm) of “pure” and doped samples upon bombardment by electrons with E=1.2 MeV and by fast reactor neutrons that the centers responsible for this luminescence are complex in nature. They consist of interstitial cadmium atoms and oxygen atoms. Electron bombardment of CdS:Cu single crystals results in the formation of new centers which are responsible for luminescence with λ _M=570 and 545 nm. Fiz. Tekh. Poluprovodn. 31, 390–392 (April 1997)     

A design of a fast pipelined modular multiplier based on a diminished-radix algorithm

We present a new serial-parallel concurrent modular-multiplication algorithm and architecture suitable for standard RSA encryption. In the new scheme, multiplication is performed modulo a multiple of the RSA modulus n, which has a diminished-radix form 2 ^k -v, where k and v are positive integers and v < n. This design is the first concurrent modular multiplier to use a diminished-radix algorithm and to pipeline concurrent modular-reduction to optimize the clock rate. For a modular multiplier of order ranging from 1 to 10 (number of multiplier bits per clock cycle), a faster clock rate and throughput is possible than with other known designs including those of Brickell, Morita, Sedlak and Golze, and Miyaguchi. Throughput estimates for 512-bit RSA decryption range from 100 kbit/s in a serial mode to 650 kbit/s with a modular multiplier of order 10, at a clock rate of 20 MHz on 1.5 m CMOS.     

A Magnetoresistance Induced by a Nonzero Berry Phase in GeTe/Sb2Te3 Chalcogenide Superlattices

The chalcogenide alloy Ge–Sb–Te (GST) has not only been used in rewritable digital versatile discs, but also in nonvolatile electrical phase change memory as a key recording material. Although GST has been believed for a long time not to show magnetic properties unless doped with magnetic impurities, it has recently been reported that superlattices (SLs) with the structure [(GeTe)_L(Sb₂Te₃)_M]_N (where L, M, and N are usually integers) have a large magnetoresistance at room temperature for particular combinations of L and M. Here it is reported that when [(GeTe)_L(Sb₂Te₃)_M]_N chalcogenide SL films are thermally annealed at 470 K and cooled down to room temperature under an external magnetic field accompanied by current pulse injections, a large magnetoresistance change (>2500 Ω) is induced. This study shows that the phenomenon has a strong correlation with the GeTe thickness and the periodic structure of the SL films, and that it is induced by the structural phase transition between electrically nonpolar and polar phases in the GeTe layers in the SLs. This study proposes that the relationship between the polar (ferroelectric) phase and the Berry curvature in the SLs is responsible for the magnetoresistance change.