Регистрация Войти
Рейтинг:4
Max1z avatar Crypto

Различные оценки леммы о переключении PRP/PRF

флаг kr
Max1z

Лемма о переключении PRP/PRF обычно обозначается как следует: введите описание изображения здесь

Я понимаю доказательство этой версии связанного $\frac{q(q-1)}{2^{n+1}}$ и игровая техника, стоящая за этим.

Однако недавно мне попалась другая версия этой леммы, которая чаще используется в статьях. Он обозначается как следует: введите описание изображения здесь

Эта версия границы оказывается $\frac{q^{2}}{2^{n+1}}$ (или что-то в этом роде).Соответствующее доказательство (стр. 150) не объясняет, почему количество пар столкновений $\frac{q^{2}}{2}$ вместо $\frac{q(q-1)}{2}$ когда есть $q$ запросы.

Итак, мой вопрос:

Почему граница $\frac{q^{2}}{2^{n+1}}$ вместо $\frac{q(q-1)}{2^{n+1}}$ в последней версии этой леммы о переключении? Как это доказать? Спасибо!

161
0 + 0
флаг cn
Maeher
Поскольку $q^2 \geq q(q-1)$ для $q\in\mathbb{N}$, из первого варианта следует второй.
3
Ответить
Max1z avatar
флаг kr
Max1z
Спасибо, kelalaka и Maehar. У меня когда-то была такая же мысль с тобой. То есть «Последняя граница получена из первой только для удобства вычислений?». Однако поддержки этой идеи я не нахожу. Ни в одной статье или книге никогда не обсуждается взаимосвязь между этими двумя границами, они просто выбирают одну из них, но никогда не упоминают другую. Поэтому я хочу знать, есть ли между ними более глубокая связь, кроме масштабирования неравенства.
0
Ответить
флаг cn
Maeher
Глубоких отношений нет. $q(q-1)$ — более строгая граница, из которой тривиально следует более слабая граница $q^2$. Если вы заботитесь о жесткости своих границ, используйте более тесную. Если вы этого не сделаете, удобнее просто использовать $q^2$.
2
Ответить
Max1z avatar
флаг kr
Max1z
Спасибо @Maeher! Если нет более глубокой связи, то мой вопрос решен. Было бы лучше, если бы были какие-либо ссылки, которые упоминают об этом.
0
Ответить
Рейтинг:4
avatar Crypto
флаг cn
Maeher

Простой ответ: обе леммы верны, и первая тривиально влечет за собой вторую. Это следует просто потому, что для любого $q\in\mathbb{N}$, $q(q-1) = q^2-q \leq q^2$.

Почему тогда существуют обе версии? Первый дает более точную верхнюю границу, если вас очень заботит точность конкретных границ в любом доказательстве, которое вы используете, используйте его. Если плотность бетона не так важна, вы можете также использовать более слабый, потому что он быстрее пишется и легче читается.

Соответствующее доказательство (стр. 150) не объясняет, почему количество пар столкновений равно $\фракция{q^2}{2}$ вместо $\frac{q(q-1)}{2}$ когда есть $q$ запросы.

Не указано, что есть $q^2/2$ такие пары вообще. Это говорит о том, что

Есть меньше, чем $Q^2/2$ такие пары

что верно, учитывая наличие $Q(Q-1)/2 \leqQ^2/2$ много пар.

Как это доказать?

Что ж, доказательство есть в книге, но если вам легче следовать доказательству Беллара и Рогауэя, вы можете просто использовать это доказательство, учитывая, что оно доказывает строго более сильную верхнюю границу.

0 + 0
kelalaka avatar
флаг in
kelalaka
Спасибо за конвертацию,
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

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

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