The best known algorithm for modular exponentiation Memod t for arbitrary M, e and t is of O(n3) where n is the number of bits in the largest of M, e and t. This paper presents an O(n2) algorithm for the problem where Memod t is required for many values of M and e with constant t some preprocessing is done on t, and the results are applied repeatedly to different values of M and e. The main algorithm involves on-line arithmetic in a redundant. number system. An immediate application is in encoding/decoding of messages in an RSA-based public-key cryptosystem.

Application of associative processors to the solution of the maximal flow problem is investigated. To take maximum advantage of the capability of associative processors, a new algorithm based on matrix representation is developed. The new algorithm is then compared with the associative version of the Ford and Fulkerson labeling method. The comparison is made on the total associative memory access time required for problem solution by each algorithm running on an associate processor. Results show that the ratio of the labeling algorithm to the new algorithm is about 3 for a dense network with 5 nodes. This ratio increases as the number of nodes increases, and decreases as the density of the network decreases.

Previous proposals for fast multipliers are discussed, along with a summary of the known theoretical limitations of such designs. Then, a new parallel multiplier with a very simple configuration is suggested. This multiplier operates in time 0(n), where n is the maximum of the lengths of the multiplier and multiplicand, both of which are fixed point, expressed in binary notation. It is a logical circuit consisting of 2n modules, each being only slightly more complex than a full adder; instead of three inputs and two outputs, each module has five inputs and three outputs. A logical circuit realization is given for the modules. But perhaps the most significant aspect of this design is the property that the input is required only bit-sequentially and the output is generated bit-sequentially, both at the rate of one bit per time step, least significant bit first. The advantages of such bit-sequential input and output arithmetic units are described.

Cellular arrays composed of identical cells with uniform interconnections are presented. The basic cell is a switching device with two inputs, two outputs, and two control variables x and T. The cell structure is either purely combinational or with unit delay depending upon the control variable T. The control variable x sets up either a ``crossing mode'' or a ``bending mode'' in the cell. Thus a two-dimensional cellular array without time delays has the connection capabilities of a crossbar switch. Any combinational switching function can be realized by appropriate choice of control variables while the inputs to the edges of the plane are fixed. Alternatively, the control variables can be fixed while the inputs to the edges of the cellular plane are varied from function to function. A cubic array is constructed from a set of identical cellular planes packed one upon the other such that the control variables applied to the first plane will penetrate to all other planes without time delay. It is shown that any k functions of the same variables can be synthesized on such a cubic array. By allowing the control variable T to delay some signals in the array, such a cubic array can be used to realize any synchronous sequential machine with single or multiple inputs and/or feedback functions. Any defective cell in the array can be tested and isolated. The array can be stripped, divided, or interconnected.