înregistrare Logare
Puncte:2
GhostMaggiore avatar Crypto

Dovada cu extractor și min-entropie

drapel ph
GhostMaggiore

Urmează un curs care vorbește despre criptografie. În acest curs am vorbit despre Min-Entropie ($H_{\infty}$) și Extractor. Pentru a arăta că un extractor $Ext:\{0,1\}^n \rightarrow \{0,1\}^l$ care scoate un șir uniform aleatoriu nu există dacă $H_{\infty} < n$ luăm cazul special $\ell=1$.

Dar nu înțeleg bine dovada.

În această dovadă luăm preimaginea a $b$ Unde $b \in \{0,1\}$ este rezultatul care maximizează dimensiunea preimaginei. Deci vom avea $\|Ext^{-1}(b)\| \ge 2^{n-1}$. Dacă atunci luăm un $X$ uniform peste $Ext^{-1}(b)$ avem o constantă și cred că aceasta este în contrast cu min-entropia egală cu $n-1$.

Nu înțeleg de ce ar trebui să luăm preimaginea și cum să luăm o uniformă $X$.

72
0 + 0
kodlu avatar
drapel sa
kodlu
Folosiți \{ \} în mathjax pentru a obține $\{ \}$.Nici nu puteți avea $n=n-1$, așa că curățați-vă întrebarea. Expresia „avem o constantă” este lipsită de sens, o constantă ce?
0
Răspunde
GhostMaggiore avatar
drapel ph
GhostMaggiore
De ce nu pot avea n = n-1? Așa a explicat profesorul dovada. Semnificația lui „au o constantă” este că, dacă luați un $Ext^{-1}(b), ieșirea este întotdeauna aceeași, deci min-entropia este 0. Cu toate acestea, așa am „înțeles” explicația lui. Îmi pare rău, dar nu știu cum să explic dovada într-un mod diferit, pentru că nu o înțeleg cu adevărat.
0
Răspunde
Paul Uszak avatar
drapel cn
Paul Uszak
Hiya Ghost & welcome :-) $n=n-1$ este echivalent cu $1=2$ matematic. Vrei să spui extragerea dintr-o secvență de biți $ \{0,1\} ^m $ erau $m
0
Răspunde
GhostMaggiore avatar
drapel ph
GhostMaggiore
Nu cred că profesorul nu este bun. Vina este a mea cu siguranță. Poate pot relua lecția și încerc să înțeleg mai bine. Multumesc oricum.
0
Răspunde
Maarten Bodewes avatar
drapel in
Maarten Bodewes
**Întreabă prof**! Aceasta pare a fi o întrebare autentică. Orice profesor care merită să-și îndeplinească ar trebui să încerce să învețe studenți bine dispusi.
3
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.