Рейтинг:1

Почему $q$ в LWE должен быть полиномиальным по $n$

флаг in

Мне интересно, почему модуль $q$ в задаче LWE должен быть полиномиальным по $n$.

Другой вопрос заключается в том, можно ли считать его произвольным целым числом вместо простого числа.

Ievgeni avatar
флаг cn
Вы спрашиваете, почему $q\in O(poly(n))$ или почему $q\in \Omega(poly(n))$?
C.S. avatar
флаг in
@Ievgeni Это $O(\text{poly}(n)$
Ievgeni avatar
флаг cn
Не могли бы вы уточнить, где, по вашему мнению, должно быть q в $O(poly(n))$?
C.S. avatar
флаг in
@Ивгений это здесь https://cims.nyu.edu/~regev/papers/lwesurvey.pdf Раздел "Параметры" в конце страницы 2. Большое спасибо!
Рейтинг:0
флаг cn

Я думаю, что ответ находится в документе, который вы нашли рекомендацию: «Выбор экспоненциального модуля $q$ имеет недостаток значительного увеличения размера входных данных».

C.S. avatar
флаг in
Да, но что вход здесь? Ввод чего?
Ievgeni avatar
флаг cn
$(\vec a, ã\vec a, sã+ e)$

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

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