Device and method for generating a random number drawn according to a nonuniform distribution

Patent metadata

Field	Value
Publication number	US-11907682-B2
Application number	US-202117145787-A
Country	US
Kind code	B2
Filing date	Jan 11, 2021
Priority date	Jan 14, 2020
Publication date	Feb 20, 2024
Grant date	Feb 20, 2024

Abstract

This device comprises a fast sampler comprising:a truncated table associating with truncated random numbers rmsb coded on Nmsb bits, the only sample k for which, whatever the number rlsb belonging to the interval [0; 2Nr−Nmsb−1], the following condition is met: F(k−1)<(rmsb, rlsb)≤F(k), where:(rmsb, rlsb) is the binary number coded on Nr bits and the Nmsb most significant bits of which are equal to the truncated random number rmsb and the (Nr−Nmsb) least significant bits of which are equal to the number rlsb,Nmsb is an integer number lower than Nr,a module for searching for a received truncated random number rmsb in the truncated table, and able to transmit the sample k, associated, by the truncated table, with the received truncated random number rmsb, by way of random number drawn according to the probability distribution ρ.

First claim

The invention claimed is:

1. A device for generating a discrete random number, this random number being coded on N k bits and drawn according to a nonuniform, discrete and bounded probability distribution ρ, this device comprising:
a microprocessor configured to implement
a generator of random numbers that are coded on N r bits and drawn according to a uniform distribution, the number N r being a positive integer number higher than or equal to the number N k ,
a slow sampler comprising:
a complete table associating, with each possible probability F(k) of the cumulative probability density F of the distribution ρ, the corresponding sample k coded on N k bits, each probability F(k) being coded on N F bits, the number N F being higher than the number N k and lower than or equal to the number N r ,
a first searching module able:

to receive the N r bits of a random number r generated by the generator,
in response, to select, from the complete table, the only probability F(k) such that F(k−1)<r≤F(k), then
to transmit the sample k, associated by the complete table with the selected probability F(k), of as the discrete random number drawn according to the distribution ρ,
a fast sampler (ER i ) comprising:
a truncated table, which is smaller than the complete table, associating with truncated random numbers r msb coded only on N msb bits, the only sample k for which, whatever a number r lsb belonging to an interval [0; 2 Nr−Nmsb −1], the following condition is met: F(k−1)<(r msb , r lsb )≤F(k), where:

(r msb , r lsb ) is the binary number coded on N r bits and the N msb most significant bits of which are equal to the N msb bits of a truncated random number r msb and the (N r −N msb ) least significant bits of which are equal to the (N r −N msb ) bits of the number r lsb ,
N msb is a positive integer number lower than N r ,
a second searching module able:

to acquire the N msb most significant bits of the random number r generated by the generator, these N msb bits forming a received truncated random number r msb ,
in response, to search for the received truncated random number r msb in the truncated table, and
if the search is successful, to transmit the sample k, associated, by the truncated table, with the received truncated random number r msb , as the discrete random number drawn according to the distribution ρ, and, alternatively, if the search is unsuccessful, to send a failure signal, and
the slow sampler is able to:
receive the failure signal and the random number r generated by the generator and the N msb most significant bits of which are equal to the truncated random number r msb that led to this failure signal being sent, then
in response, to select, using the complete table, and to transmit the only sample k that meets the condition F(k−1)<r≤F(k) and that was unable to be transmitted by the fast sampler,

the generator is able to generate a new random number r at the start of each sampling interval, these sampling intervals being repeated periodically,
wherein the device comprises:
a plurality of fast samplers each able to work in parallel with the other fast samplers and in parallel with the slow sampler, and
an arbitrating module able to activate, on each new sampling interval, a new fast sampler different from the fast sampler activated in the preceding sampling interval, to process the N msb bits of the random number r generated at the start of this new sampling interval, with this new activated fast sampler.

2. The device as claimed in claim 1 , wherein the slow sampler is able, for each of the fast samplers, to receive:
the failure signal generated by this fast sampler, and
the random number r that led to the generation of this failure signal.

3. The device as claimed in claim 1 , wherein:
the device comprises a memory able:
to receive and to store each transmitted sample k, and
to deliver as output from the device, at the end of each sampling interval and provided that there are samples k stored in this memory, the oldest stored sample k.

4. The device as claimed in claim 3 , wherein:
the number of fast samplers is comprised between three and five,
the size of the memory allows at most T MF samples k to be stored, where the number T MF is comprised between eight and sixteen, and
the number N msb is comprised between four and six.

5. The device as claimed in claim 1 , wherein the number N msb is five times smaller than the number N r .

6. The device as claimed in claim 1 , wherein the number N r is a positive integer number at least two or four times higher than the number N k .

7. The device as claimed in claim 1 , wherein the generator is able to firstly generate the N msb bits of the random number r and, the fast sampler is able to inhibit the generation, by the generator, of the (N r −N msb ) bits following the random number r each time the search in the truncated table is successful.

8. The device as claimed in claim 1 , wherein:
the truncated table contains 2 Nmsb−s cells ordered in order of increasing index, where s is a positive or zero integer number lower than N msb , each sample k associated, by the truncated table, with a corresponding truncated random number r msb comprised between 0 and 2 Nmsb−s −1 being stored in the cell the index of which is equal to this corresponding truncated random number r msb , the other cells that contain no sample k containing a failure symbol different from all the samples k, and
the second searching module is able to directly read the content of the cell in the truncated table the index of which is equal to the received truncated random number r msb searched for in this truncated table and, when the read content is a sample k, to transmit this sample k, and when the read content is the failure symbol, to send the failure signal.

9. The device as claimed in claim 1 , wherein the distribution ρ is a discrete and bounded Gaussian probability distribution.

10. A method for generating a discrete random number, this random number being coded on N k bits and drawn according to a nonuniform, discrete and bounded probability distribution ρ, this method comprising:
a step of providing a complete table associating, with each possible probability F(k) of the cumulative probability density F of the distribution ρ, the corresponding sample k coded on N k bits, each probability F(k) being coded on N F bits, the number N F being higher than the number N k and lower than or equal to a number N r ,
a step of generating random numbers each coded on N r bits and drawn according to a uniform distribution, the number N r being a positive integer number higher than or equal to the number N k , this generating step comprising the generation of a new random number r at the start of each sampling interval, these sampling intervals being repeated periodically,
a slow-sampling step, this step comprising:
receiving the N r bits of a random number r generated by the generator,
in response, selecting, from the complete table, the only probability F(k) such that F(k−1)<r≤F(k), then
transmitting the sample k, associated by the complete table with the selected probability F(k), as the discrete random number drawn according to the distribution ρ,
providing a truncated table, which is smaller than the complete table, associating with truncated random numbers r msb coded only on N msb bits, the only sample k for which, whatever a number r lsb belonging to an interval [0; 2 Nr−Nmsb −1], the following condition is met: F(k−1)<(r msb , r lsb )≤F(k), where:
(r msb , r lsb ) is the binary number coded on N r bits and the N msb most significant bits of which are equal to the N msb bits of the truncated rando

Assignees

• Commissariat Energie Atomique

Inventors

• Hiscock Thomas

Classifications

• G06F7/58 Primary

  Random or pseudo-random number generators · CPC title

• H04L9/0869 Primary

  involving random numbers or seeds · CPC title

• H04L9/3093

  involving Lattices or polynomial equations, e.g. NTRU scheme · CPC title

• H04L2209/125

  Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations · CPC title