Рейтинг:2

Экстрактор и доказательство минимальной энтропии

флаг ph

Я прохожу курс, посвященный криптографии. В этом курсе мы говорили о минимальной энтропии ($H_{\infty}$) и Экстрактор. Чтобы показать, что экстрактор $Ext:\{0,1\}^n \стрелка вправо \{0,1\}^l$ который выводит равномерно случайную строку, не существует, если $H_{\infty} < п$ мы берем частный случай $\ell=1$.

Но я плохо понимаю доказательство.

В этом доказательстве мы берем прообраз $b$ куда $b \in \{0,1\}$ выход, который максимизирует размер прообраза. Так что у нас будет $\|Расш^{-1}(б)\| \ge 2^{n-1}$. Если тогда мы возьмем $Х$ униформа над $Ext^{-1}(б)$ у нас есть константа, и я думаю, что это в отличие от минимальной энтропии, равной $n-1$.

Я не понимаю, почему мы должны брать прообраз и как мы берем форму $Х$.

kodlu avatar
флаг sa
Используйте \{ \} в mathjax, чтобы получить $\{ \}$.У вас также не может быть $n=n-1$, поэтому очистите свой вопрос. Выражение "у нас константа" бессмысленно, константа какая?
GhostMaggiore avatar
флаг ph
Почему я не могу иметь n = n-1? Вот как профессор объяснил доказательство. Значение «иметь константу» заключается в том, что если вы возьмете $Ext^{-1}(b), результат всегда будет одинаковым, поэтому минимальная энтропия равна 0. Однако именно так я «понял» его объяснение. Извините, но я не знаю, как объяснить доказательство по-другому, потому что я его не очень понимаю.
Paul Uszak avatar
флаг cn
Привет, Призрак и добро пожаловать :-) $n=n-1$ математически эквивалентно $1=2$. Вы имеете в виду извлечение из битовой последовательности $\{0,1\} ^m $ were $m
GhostMaggiore avatar
флаг ph
Я не думаю, что профессор плохой. Вина точно моя. Может быть, я смогу повторить урок и попытаться понять лучше. Спасибо, в любом случае.
Maarten Bodewes avatar
флаг in
**Спросите профессора**! Это кажется искренним вопросом. Любой достойный профессор должен попытаться научить желающих студентов.

Ответить или комментировать

Большинство людей не понимают, что склонность к познанию нового открывает путь к обучению и улучшает межличностные связи. В исследованиях Элисон, например, хотя люди могли точно вспомнить, сколько вопросов было задано в их разговорах, они не чувствовали интуитивно связи между вопросами и симпатиями. В четырех исследованиях, в которых участники сами участвовали в разговорах или читали стенограммы чужих разговоров, люди, как правило, не осознавали, что задаваемый вопрос повлияет — или повлиял — на уровень дружбы между собеседниками.