RANDOM NUMBER GENERATION INCLUDING SKEWNESS CONTROL

• US 20070067692A1
• Filed: 09/05/2006
• Published: 03/22/2007
• Est. Priority Date: 09/05/2005
• Status: Active Grant

• Current Assignee: Infineon Technologies AG
• Original Assignee: Infineon Technologies AG
• Inventors: Dichtl, Markus
• Granted Patent: US 7,870,175 B2
• Time in Patent Office: Days
• US Class Current: 714/738
• CPC Class Codes: G06F 7/582 Pseudo-random number generators

Abstract

Random numbers can be generated in a statistically independent manner and with identical probability if the bits generated by a controlled bit generator are stored by a storage in a plurality of memory regions, wherein the bits are each stored in such memory regions associated with a difference of the bits of the values 1 and 0 generated up to the time of storage, and if all the bits stored within a memory region are subjected to algorithmic post-processing as soon as a predetermined number of bits within a memory region is exceeded. The fact that the bits are not stored and processed sequentially, i.e. in the order of generation, allows using a sequence of bits within which the individual bits are statistically independent of one another for the algorithmic post-processing. Thus, a way of performing algorithmic post-processing of the bits without reducing the entropy is provided.

Claims

1. A device for generating random numbers, comprising:

a bit generator for generating bits formed to generate a bit of a value 0 or 1 with a probability depending on a control quantity;

a counter for determining a difference in the number of bits of values 0 and 1 generated, and for determining a difference value for bits output by the bit generator;

a storage having a plurality of memory regions, wherein each memory region is associated with a difference value, wherein the storage is formed to store a bit output by the bit generator in the memory region associated with the difference value; and

a reader for reading out the bits from a memory region if a predetermined number of bits is stored in the one of the memory regions.

2. The device according to claim 1, wherein the counter is additionally formed to change the control quantity of the bit generator depending on the difference value.

3. The device according to claim 2, wherein the counter is formed to change the control quantity such that if a difference value indicates a more frequent occurrence of one of the values 0 or 1, a probability with which the more frequent value is generated by the bit generator will be reduced.

4. The device according to claim 3, wherein the reader is formed to deduce the random numbers by applying an association rule to the bits read out.

5. The device according to claim 4, wherein the association rule is applied such that the values 0 and 1 are evenly distributed in the random numbers provided.

6. The device according to claim 4, wherein the reader is formed such that applying the association rule includes combining at least two bits read out to form a random number.

7. The device according to claim 1, wherein the reader is additionally formed to check an even distribution of the values 0 and 1 in the bits read out from the memory region to deduce the random numbers depending on the check result.

8. The device according to claim 7, wherein the reader is formed to provide the bits read out as random numbers if the even distribution check indicates an even distribution of the values 0 and 1 in the bits read out.

9. The device according to claim 1, wherein the reader is formed to read out the bits from the memory region associated with a current difference value.

10. A method for generating random numbers, comprising:

generating bits of a value 0 or 1, wherein the probability of generating the value 0 or 1 depends on a control quantity;

determining the difference in the number of the bits of the values 0 and 1 generated;

storing a bit generated in a memory region of a plurality of memory regions of a storage in which each memory region is associated with a difference value, wherein the bit is stored in the memory region associated with the difference value; and

reading out the bits from the memory region if a predetermined number of bits is stored in the one of the memory regions.

11. A computer program having a program code for performing a method for generating random numbers, comprising:

generating bits of a value 0 or 1, wherein the probability of generating the value 0 or 1 depends on a control quantity;

determining the difference in the number of the bits of the values 0 and 1 generated;

storing a bit generated in a memory region of a plurality of memory regions of a storage in which each memory region is associated with a difference value, wherein the bit is stored in the memory region associated with the difference value; and

reading out the bits from the memory region if a predetermined number of bits is stored in the one of the memory regions, when the program runs on a computer.

12. A device for generating random numbers, comprising:

a bit generator for generating bits formed to generate a bit of a value 0 or 1 with a probability depending on a control quantity;

a counter for determining the difference in the number of bits of values 0 and 1 generated, and for determining a difference value for bits output by the bit generator; and

a storage having a plurality of memory regions, wherein each memory region is associated with a difference value, wherein the storage is formed to store a bit output by the bit generator in the memory region associated with the difference value.

13. A method for generating random numbers, comprising:

generating bits of a value 0 or 1, wherein the probability of generating the value 0 or 1 depends on a control quantity;

determining the difference in the number of the bits of the values 0 and 1 generated; and

storing a bit generated in a memory region of a plurality of memory regions of a storage in which each memory region is associated with a difference value, wherein the bit is stored in the memory region associated with the difference value.

14. A computer program having a program code for performing a method for generating random numbers, comprising:

generating bits of a value 0 or 1, wherein the probability of generating the value 0 or 1 depends on a control quantity;

determining the difference in the number of the bits of the values 0 and 1 generated; and

storing a bit generated in a memory region of a plurality of memory regions of a storage in which each memory region is associated with a difference value, wherein the bit is stored in the memory region associated with the difference value, when the program runs on a computer.