US 4,667,301 AGranted

Generator for pseudo-random numbers

AssigneeControl Data Corporation

InventorsSou-Hsiung J. Chiu, Yulu Qi

Life of this patent

Estimating the term…

Loading patent…

Abstract

Pseudo-random numbers (PRNs) have great importance in data processing and encryption. The standard technique for generating PRNs on computers at the present time involves software implementation of recursively computing PRN.sub.n+1 =(PRN.sub.n)(b) mod M, in real number field which means that a relatively slow and involved multiplication must occur for each PRN, and each PRN calculation is strictly subsequent to previous PRM calculations. This disclosure shows a systolic multiplier implemented by a series of exclusive OR operations which generates simultaneously a new set of the PRN's from the current set of PRN's in parallel. The operation of multiplication mod M is performed over a finite field instead of a real number field. To facilitate the multiplication, the input operands are first transformed into a different representation that consists of more bits than that of the original ones. The operation of multiplication is then carried out in this transformed representation. The number of bits of the intermediate product is then reduced to that specified for each PRN through an inverse transform network, thereby forming a new PRN. The cheapness, speed, and simplicity of the required logic allows at least one PRN to be generated per computer cycle. If desired, several logic networks can be paralleled for simultaneous generation of multiple PRNs. This technique allows PRN.sub.n+k, . . . to be generated directly from PRN.sub.n, . . . where k is some proper integer.

Claims1

Dependent claims

A non-recursive pseudo-random number generator comprised of:

input means for generating a first finite field binary operand from an input binary operand,
a register connected to said input means for storing said first finite field binary operand,
means for providing a second finite field binary operand to be multiplied with said first finite field binary operand stored in said register,
a plurality of AND gates connected to receive individual first finite field binary operand bits from said register and said second finite field binary operand bits from said means for providing a second finite field binary operand to produce output partial product bits representative of the bit-by-bit multiplication of said first and second input finite field binary operands,
exclusive OR means connected with the outputs of said AND gates for computing an exclusive OR function for all bits of said first and second finite field binary operands and for producing a single output bit which represents a particular bit of the output finite field binary operand forming the product of the input binary operands, where each bit of said output product binary finite field operand is generated in the same manner,
a product storage register,
a multiplexer having an output connection to each bit position of said product storage register, and a single input connection connected to the output of said exclusive OR means,
a systolic counter connected to said multiplexer for controlling said multiplexer to shift its input-output connection by one bit position as each product bit is produced, and
a number counter to produce an output count as each new random number is formed.

6 more elements

Dependencies are inferred from the claim text.

Facts

Application: 06/504,091Filed 13 Jun 1983
Granted: 19 May 1987
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

G06F 7/724
Using residue arithmetic: finite field arithmetic
G06F 7/584
Pseudo-random number generators: using finite field arithmetic, e.g. using a linear feedback shift register
G06F 7/586
Pseudo-random number generators: using an integer algorithm, e.g. using linear congruential method
G06F 2207/581
Indexing scheme relating to groups G06F7/58 - G06F7/588: generating an LFSR sequence, e.g. an m-sequence; sequence may be generated without LFSR,…