Metraipolis › archive › dc_bbf393c22581
Randomness extractor — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Randomness_extractor
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-15T17:03:59.076Z
- SHA-256 of the archived text
774360aba48c086a6d739d17c9127801c2525bca76a0f59a9c11468b3d2d23b2- Stable URL of this page
https://metraipolis.com/documento/dc_bbf393c22581
How to cite
Randomness extractor — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Randomness_extractor (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_bbf393c22581 (Metraipolis archive dc_bbf393c22581, sha256 774360aba48c086a6d739d17c9127801c2525bca76a0f59a9c11468b3d2d23b2)
BibTeX
@misc{dcbbf393c22581,
title = {Randomness extractor — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Randomness_extractor},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_bbf393c22581; sha256 774360aba48c086a6d739d17c9127801c2525bca76a0f59a9c11468b3d2d23b2},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Randomness_extractor. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weak entropy source, together with a short, uniformly random seed, generates a highly random output that appears independent from the source and uniformly distributed. Examples of weakly random sources include radioactive decay or thermal noise; the only restriction on possible sources is that there is no way they can be fully controlled, calculated or predicted, and that a lower bound on their entropy rate can be established. For a given source, a randomness extractor can even be considered to be a true random number generator (TRNG); but there is no single extractor that has been proven to produce truly random output from any type of weakly random source. Sometimes the term "bias" is used to denote a weakly random source's departure from uniformity, and in older literature, some extractors are called unbiasing algorithms, as they take the randomness from a so-called "biased" source and output a distribution that appears unbiased. The weakly random source will always be longer than the extractor's output, but an efficient extractor is one that lowers this ratio of lengths as much as possible, while simultaneously keeping the seed length low. Intuitively, this means that as much randomness as possible has been "extracted" from the source. An extractor has some conceptual similarities with a pseudorandom generator (PRG), but the two concepts are not identical. Both are functions that take as input a small, uniformly random seed and produce a longer output that "looks" uniformly random. Some pseudorandom generators are, in fact, also extractors. (When a PRG is based on the existence of hard-core predicates, one can think of the weakly random source as a set of truth tables of such predicates and prove that the output is statistically close to uniform.) However, the general PRG definition does not specify that a weakly random source must be used, and while in the case of an extractor, the output should be statistically close to uniform, in a PRG it is only required to be computationally indistinguishable from uniform, a somewhat weaker concept. Tema degli esploratori: fiducia digitale e crittografia (deposito sistematico; ricerca «cryptographic hash function»). Fonte: Wikipedia in inglese, voce «Randomness extractor» — https://en.wikipedia.org/wiki/Randomness_extractor Wikidata Q7292012 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q7292012 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Randomness_extractor?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1378835663, consultata il 2026-10-15T16:15:05.703Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: c8b20fece6d442a04e2ac62f944dc8a2a882c23c87dfe9ee742edc92b617da2c