Pseudospille - Pseudorandomness

En pseudoslutt rekke av tall er en som ser ut til å være statistisk tilfeldig , til tross for at den er produsert av en helt deterministisk og repeterbar prosess.

Bakgrunn

Generasjonen av tilfeldige tall har mange bruksområder, for eksempel for tilfeldig prøvetaking , Monte Carlo -metoder , brettspill eller pengespill . I fysikken er imidlertid de fleste prosesser, for eksempel gravitasjonsakselerasjon, deterministiske, noe som betyr at de alltid gir det samme resultatet fra det samme utgangspunktet. Noen bemerkelsesverdige unntak er radioaktivt forfall og kvantemåling , som begge er modellert som virkelig tilfeldige prosesser i den underliggende fysikken. Siden disse prosessene ikke er praktiske kilder til tilfeldige tall, bruker folk pseudoslåtte tall, som ideelt sett har uforutsigbarheten til en virkelig tilfeldig sekvens, til tross for at de er generert av en deterministisk prosess.

I mange applikasjoner er den deterministiske prosessen en datamaskinalgoritme kalt en pseudotilfeldig tallgenerator , som først må forsynes med et tall som kalles et tilfeldig frø . Siden det samme frøet vil gi den samme sekvensen hver gang, er det viktig at frøet velges godt og holdes skjult, spesielt i sikkerhetsapplikasjoner , hvor mønsterets uforutsigbarhet er en kritisk funksjon.

I noen tilfeller der det er viktig at sekvensen er beviselig uforutsigbar, har folk brukt fysiske kilder til tilfeldige tall, for eksempel radioaktivt forfall, atmosfærisk elektromagnetisk støy høstet fra en radio som er innstilt mellom stasjoner, eller blandede tidspunkter for folks tastetrykk . Tidsinvesteringen som trengs for å skaffe disse tallene fører til et kompromiss: å bruke noen av disse fysikkavlesningene som et frø for en pseudoslått tallgenerator.

Historie

Før moderne databehandling ville forskere som krever tilfeldige tall, enten generere dem på forskjellige måter ( terninger , kort , roulettehjul , etc.) eller bruke eksisterende tabeller for tilfeldige tall.

Det første forsøket på å gi forskere en klar forsyning av tilfeldige sifre var i 1927, da Cambridge University Press publiserte en tabell med 41 600 sifre utviklet av LHC Tippett . I 1947 genererte RAND Corporation tall ved elektronisk simulering av et roulettehjul; resultatene ble til slutt publisert i 1955 som A Million Random Digits with 100,000 Normal Deviates .

I beregningskompleksitet

I teoretisk datateknologi , en fordeling er pseudotilfeldig mot en klasse av motstandere dersom ingen motstander fra klassen som skiller seg fra den jevne fordeling med betydelig fordel. Denne oppfatningen om pseudorandomness studeres i beregningskompleksitetsteori og har applikasjoner for kryptografi .

Formelt la S og T være endelige sett og la F = { f : S → T } være en klasse med funksjoner. En fordeling D over S er ε- pseudorandom mot F hvis for hver f i F , er den statistiske avstanden mellom fordelingene og , hvor og er samplet fra D , og , hvor og er samplet fra den uniforme fordelingen på S , høyst ε . ${\ displaystyle f (X)}$${\ displaystyle X}$${\ displaystyle f (Y)}$${\ displaystyle Y}$

For vanlige anvendelser vil den klasse F beskriver en modell for beregning med begrensede ressurser, og man er interessert i å utforme fordelinger D med visse egenskaper som er pseudotilfeldig mot F . Fordelingen D er ofte spesifisert som utgangen fra en pseudoslumpgenerator .

Se også

• Kryptografisk sikker pseudotilfeldig tallgenerator
• Liste over tilfeldige tallgeneratorer
• Pseudoslutt binær sekvens
• Pseudos tilfeldig ensemble
• Pseudoslått tallgenerator
• Kvasi-tilfeldig sekvens
• Tilfeldig tallgenerering
• Pseudoslått støy

Referanser

Videre lesning

• Donald E. Knuth (1997) The Art of Computer Programming , Volume 2: Seminumerical Algorithms (3. utgave) . Addison-Wesley Professional, ISBN  0-201-89684-2
• Oded Goldreich. (2008) Computational Complexity: a conceptual perspective . Cambridge University Press. ISBN  978-0-521-88473-0 . (Begrenset forhåndsvisning på Google Books)
• Vadhan, SP (2012). "Pseudospille". Grunnlag og trender innen teoretisk informatikk . 7 (1–3): 1–336. doi : 10.1561/0400000010 .

Eksterne linker

• HotBits: Ekte tilfeldige tall, generert av radioaktivt forfall
• Bruke og lage tilfeldige tall i kryptografisk kvalitet
• I RFC 1750 diskuteres bruken av pseudoslåtte tallsekvenser i kryptografi lenge.