RLWE Объяснение

В RLWE, мы часто выбираем следующее кольцо многочленов, где q простое число, и n представляет собой степень числа 2, например. $2^к$ $$\mathbb Z_q[X]/(X^n + 1)$$

Мы знаем это ${Х^{2^к}} + 1$ является неприводимым многочленом относительно $Z$, потому что Циклотомический полином, но в это вопрос, Учитывая $$\mathbb Z_{17}[X]/(X^4 + 1)$$ $(Х^4 + 1)$ можно разложить на $$\mathbb (X^2 + 4)(X^2 - 4) = X^4 - 16 = X^4 + 1$$ потому что $Z_{17}$, более того, его можно даже разложить на $(х + 15)(х + 9)(х + 8)(х + 2)$ под $Z_{17}$

Тогда зачем нам выбирать неприводимый многочлен, например ${Х^{2^к}} + 1$ в первую очередь, когда оно приводимо под $Z_q$, кроме того, каковы преимущества выбора ${Х^{2^к}} + 1$ как наш идеальный, и предотвращает ли описанный выше сценарий выбор достаточно большого простого числа q (намного больше 17)?

Спасибо!

Круговые полиномы используются в доказательствах того, что проблемы решетки в наихудшем случае сводятся к RLWE. Если вы попытаетесь реализовать RLWE с другими полиномами, то у вас не будет таких формальных гарантий сложности задачи. Ты можешь проверить этот набор слайдов от Peikert для введения, а затем прочитайте ссылки, если вы хотите получить более подробную информацию.

И выбирая $q$ такое, что круговой многочлен не расщепляется полностью, бесполезен, потому что сложность задачи RLWE зависит только от разрядности $q$, а не в его формате.

Кстати, когда мы реализуем БГВ, ФВ, СККС или другие схемы на базе RLWE, мы часто ограничиваем себя в выборе $q$ заставить $X^n + 1$ полностью разделить, чтобы мы могли использовать Представление RNS (также известное как double-CRT).