înregistrare Logare
Puncte:1
J. Linne avatar Crypto

Secvență pseudoaleatoare „infinită” (criptografică).

drapel us
J. Linne

Acest lucru este în principal în scopuri matematice, deși ar fi bine și în scopuri criptografice, există algoritmi cunoscuți pentru generarea unei secvențe (pseudo)aleatoare infinit de lungi (să zicem biți). Secvența nu se poate repeta sau are un model și ar trebui să se comporte ca a număr „normal”. (adică asemănătoare cifrelor lui Pi sau a unei alte constante).

84
0 + 0
kelalaka avatar
drapel in
kelalaka
Pentru un PRF $F$, $a_1 = F(1), a_2 = F(2||a_1), \ldots , a_i =F(i || a_i{-1})$, nu se poate dovedi, se poate dați un PRF care nu reușește acest lucru.
0
Răspunde
Puncte:2
avatar Crypto
drapel ph
bmm6o

Nu este posibil ca o mașină cu stări finite deterministă să scoată o secvență care nu se repetă niciodată. Odată ce revine la o stare în care a fost deja, ieșirea va repeta ieșirile anterioare din acel punct.

Totuși, aceasta este mai mult o preocupare teoretică decât una practică. Chiar și un simplu CSPRNG are mai multe stări posibile decât poate vizita în timpul vieții universului. Așa că îl puteți folosi „pentru totdeauna” înainte de a observa acest tip de repetare. Orice utilizare reală a unei secvențe pseudo-aleatoare este în mod necesar finită, așa că întrebări precum normalitatea care se aplică numai secvențelor infinite nu au cu adevărat sens. În schimb, există criterii precum „ne distinge de aleatoriu”, care pare a fi omologul finit la ceea ce întrebați.

0 + 0
J. Linne avatar
drapel us
J. Linne
@poncho Mă gândeam la asta... Poate că niște PRNG, dar folosește un modul diferit de fiecare dată când „expiră” un modul vechi (adică secvența este pe cale să se repete).
0
Răspunde
poncho avatar
drapel my
poncho
Rețineți că, dacă mergem la un model de calcul mai general, în care permitem mărimea stării să crească în timpul generării, într-adevăr putem avea o ieșire care nu se repetă niciodată (și cantitatea de creștere necesară este logaritmică în rezultatul generat - adică , crește destul de încet). Desigur, după cum observă bmm6o, de obicei nu ne pasă dacă secvența se repetă după $2^{1000}$ (sau chiar $2^{256}$) și așadar acest lucru nu apare în practică...
2
Răspunde
drapel ph
bmm6o
Corect, dacă ați implementa așa ceva, probabil că ați urma modelul descris de Poncho, unde algoritmul dvs. alocă mai multă memorie după cum este necesar (deoarece modulele dvs. vor trebui să crească fără limită). Ideea rămâne că, atunci când ați scos valori $n$, aveți nevoie de cel puțin $log(n)$ biți de stare pentru a evita revizuirea unei stări anterioare.
1
Răspunde
drapel romania
SEF 777
întrebarea această in alte limbi:

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.