Generating of random numbers
A device for generating a random number is suggested, the device comprising at least two shift registers, a transformation function that generates the random number based on at least one cell of each of the at least two shift registers.
1. A device for generating a random number, the device comprising:
at least three shift registers, wherein each of the shift registers per shift register clock pulse is configured to generate, based on a plurality of cells of the respective shift register, an output vector comprising a plurality of bits; and
a transformation function configured to generate, based on the output vectors, the random number, wherein the random number comprises a plurality of bits, and the transformation function comprises:
a first transformation stage comprising first transformations corresponding to the respective shift registers, wherein each of the first transformations has a single input and is configured to map the respective output vector to a further output vector; and
a second transformation stage configured to map the further output vectors to the random number,
wherein each of the first transformation stage and the second transformation stage is a linear function.
2. The device according to claim 1 , wherein the transformation function comprises:
a concatenator configured to combine the further output vectors for the second transformation stage to map to the random number,
wherein the random number is generated in a single clock cycle.
3. The device according to claim 2 , wherein the second transformation stage is configured to compress the combined further output vectors to result in a reduced number of bits of the random number.
4. The device according to claim 2 , wherein each of the first transformations is configured to map the respective output vector with the respective further output vector.
5. The device according to claim 1 , wherein the device is configured to generate a plurality of random numbers that are substantially evenly distributed and substantially statistically independent.
6. The device according to claim 1 , wherein the random number is generated with each clock cycle applied to the shift register and the transformation function.
7. The device according to claim 1 , wherein each of the shift registers has a period amounting to 2 N −j, wherein N is the length of the shift register and j is greater than or equal to 1 and less than 2 N .
8. The device according to claim 1 , wherein each of the shift registers is a non-linear feedback shift register.
9. The device according to claim 1 , wherein the shift registers and the transformation function are implemented on a die or chip.
10. The device according to claim 1 , wherein at least two of the shift registers are of different lengths.
11. The device according to claim 1 , wherein the transformation function is configured to generate the random number based on a portion of cells of the shift registers, wherein for at least two of the shift registers a different number of cells is used to generate the respective output vectors.
12. A device for generating a random number, the device comprising:
at least three shift registers, wherein each of the shift registers per shift register clock pulse is configured to generate, based on a plurality of cells of the respective shift register, an output vector comprising a plurality of bits; and
a transformation function configured to generate, based on the output vectors, the random number, wherein the random number comprises a plurality of bits, and the transformation function comprises:
a first transformation stage comprising first transformations corresponding to the respective shift registers, wherein each of the first transformations has a single input and is configured to map the respective output vector to a further output vector, and each of the first transformations is configured to compress the respective output vector to result in a reduced number of bits in the further output vector;
a second transformation stage configured to map the further output vectors to the random number; and
a concatenator configured to combine the further output vectors for the second transformation stage to map to the random number,
wherein the random number is generated in a single clock cycle.
13. A method for generating a random number, the method comprising:
generating, by respective at least three shift registers per shift register clock pulse based on a plurality of cells of the respective shift registers, an output vector comprising a plurality of bits;
generating, by a transformation function based on the output vectors, the random number,
wherein the random number comprises a plurality of bits, and the generating by the transformation function comprises:
mapping, for each of the shift registers by a respective first transformation having a single input, the respective output vector to a further output vector; and
mapping, by a second transformation, the further output vectors to the random number,
wherein each of the first transformation and the second transformation is a linear function.
14. The method according to claim 13 , wherein the generating by the transformation function comprises:
combining, by a concatenator, the further output vectors to be mapped by the second transformation to the random number,
wherein the random number is generated in a single clock cycle.
15. A non-transitory computer program product directly loadable into a memory of a digital processing device, comprising software code portions for performing the steps of the method according to claim 13 .
16. The method according to claim 13 , wherein each of the shift registers is a non-linear feedback shift register.