Gap average on-line randomness test
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 random numbers generated by a random number generator in real time. A stream of random bits is generated using said random number generator, then the generated random bits undergo a gap length calculation operation in which all sub-sequences having identical bit patterns are identified and the resulting gap lengths are applied to exponential averaging to obtain average gap lengths between identical bit patterns. The average gap lengths are compared to at least one predetermined acceptance range, so that if at least one of the average gap lengths falls repeatedly outside the predetermined acceptance range more than a predetermined number of times, it is determined that the generated random bits are insufficiently random.
Claims19
A method for testing randomness of a stream of random numbers, the method comprising the steps of:
- generating a continuous stream of random binary bits;
- applying said generated random bits to an exponential average gap calculation to compute an average gap length between at least two identical bit patterns;
- and,
- determining whether said generated random bits are sufficiently random by comparing the output of said exponential gap operation 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 a stream of random bits using said random-number generator;
- (b) applying said generated random bits to a gap length calculation;
- (c) applying the output of said gap length calculation to an exponential averaging to obtain average gap lengths between at least two identical bit patterns;
- (d) comparing the average gap lengths to a predetermined acceptance range;
- and,
- (e) determining whether at least one of the average gap lengths falls outside said predetermined acceptance range more than a predefined number of times.
An apparatus for evaluating the random numbers generated by a random number generator, comprising:
- means for generating random sequences comprising binary bits;
- means for detecting whether said generated random sequences are insufficiently random based on an exponential average gap operation;
- and,
- means for controlling the flow of said generated random sequences for a subsequent application when said generated random sequences are determined to be insufficiently random,
- wherein said exponential average gap operation is performed to compute average gap lengths between at least two identical bit patterns and wherein, if at least one of the average gap lengths repeatedly falls outside a predetermined acceptance range more than a predefined number of times, 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:
- process a continuous stream of random binary bits;
- apply said generated random bits to an exponential gap length operation to compute average gap lengths between at least two identical bit patterns;
- and,
- determine whether said generated random bits are insufficiently random by comparing the output of said exponential gap count to a predetermined acceptance range.
Dependencies are inferred from the claim text.