Random number generation including skewness control

• US 7,870,175 B2
• Filed: 09/05/2006
• Issued: 01/11/2011
• Est. Priority Date: 09/05/2005
• Status: Active Grant

• Current Assignee: Infineon Technologies AG
• Original Assignee: Infineon Technologies AG
• Inventors: Dichtl, Markus
• Primary Examiner(s): Do; Chat C
• Assistant Examiner(s): SANDIFER, MATTHEW D
• Application Number:
  US11/470,100
• Publication Number:
  US 20070067692A1
• Time in Patent Office: 1,589 Days
• Field of Search: 708250-256
• US Class Current: 708/250
• 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 formed to generate a sequence of bits having a value of 0 or 1 at a probability depending on a control quantity;

a counter formed to determine, for each currently generated bit output by the bit generator, a difference in the number of bits in the sequence having values 0 and 1 generated up to the currently generated bit;

a storage having a plurality of memory regions, wherein each memory region is addressed by a different difference value output by the counter, wherein the storage is formed to store each currently generated bit output by the bit generator in the memory region addressed by the difference value output by the counter, wherein the difference value indicates the difference determined up to the currently generated bit; and

a reader formed to read 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 a sequence of bits having a value 0 or 1 at a probability depending on a control quantity;

determining, for each currently generated bit output by the bit generator, a difference in the number of bits in the sequence having values 0 and 1 generated up to the currently generated bit;

storing each currently generated bit in a memory region of a plurality of memory regions of a storage in which each memory region is addressed by a different difference value, wherein the currently generated bit is stored in the memory region addressed by the difference value, wherein the difference value indicates the difference determined up to the currently generated bit; 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-readable non-transitory digital storage medium having stored thereon a program having a program code for performing a method for generating random numbers, comprising:

generating a sequence of bits having a value 0 or 1 at a probability depending on a control quantity;

determining, for each currently generated bit output by the bit generator, a difference in the number of the bits in the sequence having values 0 and 1 generated up to the currently generated bit;

storing each currently generated bit in a memory region of a plurality of memory regions of a storage in which each memory region is addressed by a different difference value, wherein the currently generated bit is stored in the memory region addressed by the difference value, wherein the difference value indicates the difference determined up to the currently generated bit; 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 formed to generate bits among which a sequential order is defined, and each of which has a value 0 or 1 at a probability depending on a control quantity;

a counter formed to determine, for each currently generated bit in the sequence output by the bit generator, the difference in the number of bits in the sequence having values 0 and 1 generated up to the currently generated bit, and to determine a difference value for the currently generated bit output by the bit generator; and

a storage having a plurality of memory regions, wherein each memory region is addressed by a different difference value output by the counter, wherein the storage is formed to store each currently generated bit output by the bit generator in the memory region addressed by the difference value output by the counter, wherein the difference value indicates the difference determined up to the currently generated bit.

13. A method for generating random numbers, comprising:

generating bits among which a sequential order is defined, and each of which has a value 0 or 1 at a probability depending on a control quantity;

determining, for each currently generated bit output by the bit generator, the difference in the number of the bits in the sequence having values 0 and 1 generated up to the currently generated bit; and

storing each currently generated bit in a memory region of a plurality of memory regions of a storage in which each memory region is addressed by a different difference value, wherein the currently generated bit is stored in the memory region addressed by the difference value, wherein the difference value indicates the difference determined up to the currently generated bit.

14. A computer-readable non-transitory digital storage medium having stored thereon a program having a program code for performing a method for generating random numbers, comprising:

generating bits among which a sequential order is defined, and each of which has a value 0 or 1 at a probability depending on a control quantity;

determining, for each currently generated bit output by the bit generator, the difference in the number of bits in the sequence having values 0 and 1 generated up to the currently generated bit; and

storing each currently generated bit in a memory region of a plurality of memory regions of a storage in which each memory region is addressed by a different difference value, wherein the currently generated bit is stored in the memory region addressed by the difference value, wherein the difference value indicates the difference determined up to the currently generated bit, when the program runs on a computer.