Coded data generation or conversion – Analog to or from digital conversion – Increasing converter resolution
Reexamination Certificate
1999-12-17
2002-04-09
JeanPierre, Peguy (Department: 2819)
Coded data generation or conversion
Analog to or from digital conversion
Increasing converter resolution
36
Reexamination Certificate
active
06369727
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to random number generators (RNG) and more particularly to a method and means that uses an analog-to-digital (A/D) conversion process on random noise to produce an output from an analog-to-digital converter and then applies a reductive mapping process to the A/D converter output to transform it into a uniformly distributed random variable.
2. Description of the Prior Art
With the proliferation of digital computers, and the increasing rates at which they operate, an unprecedented demand for random numbers has arisen and accordingly RNGs. The myriad applications which benefit from RNGs are as diverse and ubiquitous as national security and home entertainment, e.g., cryptography and computer games. Earlier, random numbers were needed in order to solve problems by experimental probability procedures run on the first digital computers. The early experimental procedures have since been developed into the sophisticated probabilistic algorithms that are now run on contemporary computing platforms resulting in a corresponding increase in demand. Over the same history, the scope of digital computer applications has expanded manifold, and the advantages provided to these applications by methods which require random numbers continue to be recognized. Of greatest importance in such applications are random sequences which have the uniform probability distribution, the ideal output of computer languages' “random number functions.” Accordingly, a measure of RNG quality in this regard is that it have a small bias, i.e., a small difference between the distribution of the RNG output and the uniform distribution. The random physical phenomena employed in implementing RNGs pose unique problems in terms of harnessing the phenomena to provide, as digital signals, the needed uniformly distributed random numbers.
It is, of course, desirable that the numbers provided to a random number application be generated by means which produce actual randomness, since any correlation among them is detrimental. However, the physical phenomena useful for providing rapid, automatic random means present a problem in that they do not exhibit the uniform distribution required of the RNG output. One widely practiced solution is to circumvent this problem by substituting uniformly distributed non-random sequences in lieu of random sequences, whenever practicable. Such pseudo-random sequences are generated by deterministic algorithmic processes, e.g., modular multiplication, which, by careful selection of parameters, yield sequences that are devoid of obvious patterns. Because no random phenomenon is involved, all elements of pseudo-random sequences are, necessarily, causally related and the sequences may be accurately predicted and replicated. This replication property is fundamental for pseudo-random applications, e.g., the RSA cryptosystem (see U.S. Pat. No. 4,405,829), in which the sender uses a modular exponentiation to obscure meaning in transit and the recipient uses an inverse modular exponentiation to regenerate the sender's plaintext. However, for random number applications, this replication property is a liability, since, e.g., in order to maximize security, RSA keys (i.e., exponents and modulus) are generated exclusively by random means.
Several other prior art solutions to the problem generate random time periods as means to randomly select numbers produced by deterministic means. Examples include the so-called “electronic roulette wheel” used to produce Rand's well-known table (see Rand Corporation. (1966)
A Million Random Digits with
100,000 Normal Deviates, The Free Press. Glencoe Ill.), and the method involving radiology by which, “Random-numbers modulo-M are produced by stopping the rapidly advancing [modulo-M] counter at the random time, determined by an electron arrival of the G-M [Geiger-Mueller] tube [from a sample of
90
Sr]” (see SCHMIDT, H. (1970) “Quantum-mechanical random-number generator”,
Journal of Applied Physics,
41, 462-468). Another recent method in this regard employs user actions, e.g., keystrokes, as means to randomly select numbers from software counters in order to generate cryptographic keys for secure interchange via the Internet. The generation rates provided by the second method are obviously much higher than those provided by the latter method, but the rates are limited to 80,000 bit/sec by an estimated G-M tube limit of 10,000 counts per second. Although random frequency pulses may be produced at high rates by entirely electronic means, to significantly exceed a rate of 80,000 bit/sec would require digital counters that may be clocked at SHF or EHF frequencies, or a cumbersome plurality of slower apparatus.
Further prior art solutions use deterministic means to distort random electronic noise, which is normally distributed, in order to provide a 1-bit random variable. One example subjects the noise to successive stages of clipping, amplifying, and sampling, whereby the normal distribution is thus directly divided in two, with the probability of each fraction mapped to one of the two possible digits (see NELSON, R. D., BRADISH, G. J., and DOBYNS, Y. H. (1989) “Random event generator qualification, calibration and analysis.” Princeton University School of Engineering/Applied Sciences; and U.S. Pat. No. 5,830,064). Another example uses a comparator to severely amplify the difference between the instantaneous output of two sources. In practice, maintaining the approximate coincidence of division and median in the former example, and of the two medians in the latter example, within a tolerance that provides a bias as small as the quantum-mechanical RNG, e.g., <3×10
−6
, necessitates extreme precision and periodic calibration.
It is believed that the limitations of the prior art methods and means have resulted in speed and cost constraints on execution of random number applications which cannot tolerate non-random characteristics. These random number applications include, e.g., cryptographic key generation. The limitations have also resulted in the use of pseudo-random numbers in other applications for which high speed is essential and non-random characteristics may be tolerated, for instance, computer simulations for which unwanted correlation is not catastrophic. Still other applications for which no compromise is feasible have had to be abandoned. Lastly, in the case of probabilistic, “Monte Carlo” methods that may be practiced with pseudo-random numbers, computer resources consumed by pseudo-random generator algorithms represent a reduction of resources to the application itself
Consequently, there is a need in the art for a method and means that provide uniformly distributed random number sequences.
Objects:
It is accordingly an object of the present invention to provide an improved method and means of generating random number sequences having uniform distribution.
It is another object of the invention to provide an improved random number generator for use in any situation which benefits from random number sequences.
It is a further object of the invention to provide a high-speed RNG of particularly small bias.
It is a still further object of the invention to provide an electronic RNG which has no periodic calibration requirements.
It is an additional object of the invention to provide an improved RNG for use in applications benefiting from random number sequences, particularly applications wherein it is most preferred that an RNG be fabricated as an integrated circuit (RNG-IC).
It is also an object of the present invention to provide an improved method and means of generating random number sequences that is automatic and free of radiological considerations.
SUMMARY OF THE INVENTION
The present invention is directed to providing an improved method and means for generating random number sequences and particularly as embodied in a random number generator (RNG). The RNG embodiment provides uniformly distributed random number sequences
Jean-Pierre Peguy
Lauture Joseph J
Perman and Green, LLP
RNG Research
LandOfFree
Analog-to-digital conversion method of random number generation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Analog-to-digital conversion method of random number generation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analog-to-digital conversion method of random number generation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2910939