Method and apparatus for extracting unbiased random bits from a potentially biased source of randomness
US6393447B1 · kind B1 · utility
Assignees
Inventors
Key dates
| Filing date | Oct 22, 1998 |
| Grant date | May 21, 2002 |
| Priority date | — |
| Expiry date | Oct 22, 2018 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/58
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The invention generates a random bit string from a sequence of readings taken from a potentially biased source of randomness, such as a random stationary source which can be represented as a biased die. A simulated unbiased source is generated from the potentially biased source, and a reading is taken from the simulated unbiased source. The reading is then converted to a bit string. Taking a reading from the simulated unbiased source may involve generating an integer pair (R,S), which depends on the sequence of readings from the random source, and represents a roll of value R on a simulated unbiased die U with S sides. The pair (R,S) is then converted into an output bit string bkbk−1 . . . b1 which is unbiased over sequences of readings from the random source.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.