Randomness test utilizing auto-correlation
AssigneeKoninklijke Philips Electronics N.V.
InventorLaszlo Hars
Life of this patent
Estimating the term…
Abstract
The present invention is a method and apparatus for testing the random numbers generated by a random number generator in real time. As a series of random numbers are generated, a plurality of the last numbers are stored, then the stored random numbers are shifted by predetermined amounts to obtain a special kind of dot product of bit sequences between the stored random numbers and the shifted random numbers. The average autocorrelation values are computed each time a new random bit is generated. Thereafter, it is determined whether the generated random numbers are not sufficiently random by comparing the average autocorrelation values to predetermined acceptance ranges.
Claims21
A method for evaluating random numbers generated by a random number generator, the method comprising the steps of:
- generating a continuous stream of random bits;
- storing said generated random bits in a memory medium;
- shifting said stored random sequences by a predetermined amount;
- computing modified products of bit sequences between said stored random sequences and said shifted random sequences to determine an average correlation value;
- and,
- determining whether said generated random numbers are sufficiently random by comparing said determined average correlation value to a predetermined acceptance range.
A method for evaluating the random numbers generated by a random number generator, the method comprising the steps of:
- (a) generating and storing a stream of random bits using said random number generator;
- (b) shifting said stored random sequences by a predetermined amount;
- (c) computing modified products of bit sequences between said stored random numbers and said shifted random numbers;
- (d) performing exponential averaging operations (A) on said modified products to obtain average autocorrelation values;
- (e) comparing the average autocorrelation values to a predetermined acceptance range;
- and,
- (f) determining that said generated random numbers are not sufficiently random when any of the average autocorrelation values falls outside said predetermined acceptance range.
An apparatus for evaluating the random numbers generated by a random number generator, comprising:
- a random generator unit for generating random sequences comprising of binary bits;
- a detector unit, coupled to the output of said random generator unit, for detecting whether said generated random sequences are sufficiently random;
- and,
- a switching unit, coupled to the outputs said random generator and said detector unit, for disabling the flow of said generated random sequences for a subsequent application when said generated random sequences are determined to be insufficiently random,
- wherein said generated random bits are stored and shifted by a predetermined amount to obtain modified products of bit sequences between said stored random sequences and said shifted random sequences, said modified products applied to exponential averaging operations (A) to determine an average autocorrelation value and wherein, if the output of any of said exponential averaging operations (A) falls outside a predetermined acceptance range, determining that said generated random sequences are insufficiently random.
A machine-readable medium having stored thereon data representing sequences of instructions, and the sequences of instructions which, when executed by a processor, cause the processor to:
- store a plurality of bits of externally generated random sequences of binary bits;
- shift said stored random sequences by predetermined amounts;
- compute a modified dot product of bit sequences between said stored random sequences and said shifted random sequences to determine an average autocorrelation value;
- and,
- determine whether said generated random numbers are sufficiently random by comparing all said determined average autocorrelation values to a predetermined acceptance range.
The memory medium of claim 21, wherein said exponential averaging operation (A) is computed according to the following equation:
- Anew=α·Aold1,
- wherein α=1−1/n, and α falls between 0 and 1 (0<α<1).
Dependencies are inferred from the claim text.