# US 11,907,682 B2 · Device and method for generating a random number drawn according to a nonuniform distribution

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,907,682 B2
- Document ID: US11907682B2
- Status: Granted
- Kind: B2
- Application number: 17/145,787
- Filed: 2021-01-11
- Published: 2021-07-15
- Granted: 2024-02-20
- Earliest claimed: 2020-01-14
- Assignees: Commissariat A L'energie Atomique Et Aux Energies Alternatives
- Applicants: Commissariat A L'Energie Atomique et aux Energies Alternatives
- Inventors: Thomas Hiscock
- Web page: https://patentgrep.com/patent/US11907682B2

## CPC

- G06F 7/58: Random or pseudo-random number generators
- H04L 9/0869: {involving random numbers or seeds}
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- H04L 2209/125: Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## 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 ρ.

## Claims

### Claim 1

A device for generating a discrete random number, this random number being coded on Nk 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 Nr bits and drawn according to a uniform distribution, the number Nr being a positive integer number higher than or equal to the number Nk,
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 Nk bits, each probability F(k) being coded on NF bits, the number NF being higher than the number Nk and lower than or equal to the number Nr,
a first searching module able:
to receive the Nr 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 (ERi) comprising:
a truncated table, which is smaller than the complete table, associating with truncated random numbers rmsb coded only on Nmsb bits, the only sample k for which, whatever a number rlsb belonging to an 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 Nmsb bits of a truncated random number rmsb and the (Nr−Nmsb) least significant bits of which are equal to the (Nr−Nmsb) bits of the number rlsb,
Nmsb is a positive integer number lower than Nr,
a second searching module able:
to acquire the Nmsb most significant bits of the random number r generated by the generator, these Nmsb bits forming a received truncated random number rmsb,
in response, to search for the received truncated random number rmsb 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 rmsb, 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 Nmsb most significant bits of which are equal to the truncated random number rmsb 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 Nmsb bits of the random number r generated at the start of this new sampling interval, with this new activated fast sampler.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 3)

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 TMF samples k to be stored, where the number TMF is comprised between eight and sixteen, and
the number Nmsb is comprised between four and six.

### Claim 5 (depends on 1)

The device as claimed in claim 1, wherein the number Nmsb is five times smaller than the number Nr.

### Claim 6 (depends on 1)

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

### Claim 7 (depends on 1)

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

### Claim 8 (depends on 1)

The device as claimed in claim 1, wherein:
the truncated table contains 2Nmsb−s cells ordered in order of increasing index, where s is a positive or zero integer number lower than Nmsb, each sample k associated, by the truncated table, with a corresponding truncated random number rmsb comprised between 0 and 2Nmsb−s−1 being stored in the cell the index of which is equal to this corresponding truncated random number rmsb, 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 rmsb 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.

### Claim 9 (depends on 1)

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

### Claim 10

A method for generating a discrete random number, this random number being coded on Nk 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 Nk bits, each probability F(k) being coded on NF bits, the number NF being higher than the number Nk and lower than or equal to a number Nr,
a step of generating random numbers each coded on Nr bits and drawn according to a uniform distribution, the number Nr being a positive integer number higher than or equal to the number Nk, 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 Nr 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 rmsb coded only on Nmsb bits, the only sample k for which, whatever a number rlsb belonging to an 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 Nmsb bits of the truncated random number rmsb and the (Nr−Nmsb) least significant bits of which are equal to the (Nr−Nmsb) bits of the number rlsb,
Nmsb is a positive integer number lower than Nr,
a fast-sampling step, this step comprising:
receiving the Nmsb most significant bits of the random number r generated by the generator, these Nmsb bits forming a received truncated random number rmsb,
in response, searching for this received truncated random number rmsb in the truncated table, and
if the search is successful, transmitting the sample k, associated, by the truncated table, with the received truncated random number rmsb, as the discrete random number drawn according to the distribution ρ, and, alternatively, if the search is unsuccessful, sending a failure signal, then
in response to the reception of the failure signal and of the random number r generated by the generator and the Nmsb most significant bits of which are equal to the truncated random number rmsb that led to this failure signal being sent, triggering the execution of the slow-sampling step with a view to selecting, using the complete table, and transmitting the only sample k that meets the condition F(k−1)<r≤F(k) and that was unable to be transmitted at the end of the fast-sampling phase,
wherein the method comprises:
providing a plurality of fast samplers each able to work in parallel with the other fast samplers and in parallel with the slow sampler, and
activating, on each new sampling interval, a new fast sampler different from the fast sampler activated in the preceding sampling interval, to process the Nmsb bits of the random number r generated at the start of this new sampling interval, with this new activated fast sampler.

### Claim 11 (depends on 10)

A non-transitory data-storage medium that is readable by a microprocessor, wherein this medium comprises instructions for executing a method as claimed in claim 10, when these instructions are executed by the microprocessor.