On-line randomness test through overlapping word counts
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. As random numbers are generated, overlapping blocks of k bits undergo an exponential count operation one at a time, in which the count operation is performed by dropping the leftmost bit from the previous k bit block and appending a new random bit to the right of it to form a new k bit block, thus maintaining the size of the block. The binary value of this k bit block is used for performing the accumulator selection during the overlapping count operation. All of the outputs of the exponential averaging are compared to a predetermined acceptance range to determine whether the bits generated by the random number generator is sufficiently random.
Claims25
A method for testing randomness when generating a random number, the method comprising the steps of:
- generating random sequences of binary bits;
- applying said generated random sequences to an exponential overlapping count operation A at a predefined block interval of k bits at a time to compute an average number of occurrences for each said predefined block;
- and,
- determining whether said generated random sequences are sufficiently random by comparing the output of said exponential overlapping count operation A to a predetermined acceptance range.
A method of testing an output of a random number generator, the method comprising the steps of:
- (a) generating a continuous stream of binary bits using said random number generator;
- (b) performing and tracking an overlapping exponential count operation on a predetermined block of k bits at a predefined time interval for each bit to obtain a corresponding frequency value;
- (c) comparing all said computed exponential averaging values A a predetermined acceptance range;
- and,
- (d) determining that said generated binary numbers are non-random when any one of said computed exponential averaging values falls outside of said predetermined acceptance range.
An apparatus for testing the randomness of a random number sequence, comprising:
- a random generator unit for generating substantially random sequences of binary bits;
- and,
- a detector unit, coupled to the output of said random generator unit, for detecting whether said generated random sequences are sufficiently random,
- wherein said generated random sequences are applied to an exponential overlapping count operation A at a predefined block interval of k bits to compute an average number of occurrences for each said predefined block, and wherein if the output of said exponential overlapping count operation A falls outside of 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:
- generate a stream of random numbers of binary bits;
- compute and track an exponential overlapping count operation on a predetermined block of k bits at a predefined time interval for each bit to obtain a corresponding binary value;
- and,
- compare all said computed exponential averaging A to a predetermined acceptance range to determine whether said generated random numbers are sufficiently random.
Dependencies are inferred from the claim text.