决定-LWE搜索-LWE

Question

Regev要求$q$是他为LWE撰写的论文引理4.2上的素数。

他为什么要求这样做，这对引理4.2的证明有什么影响？

Answer 1

他需要在第二坐标系中加入一些均匀随机的东西，才能得到一致随机的分布。(这个想法是，如果他猜到了正确的键，那么他的重命名就会将真实的实例转化为真实的实例。如果他猜错了键，他的重命名应该把实际的实例变成随机的实例。)

如果$p$是素数，那么任意非零值的乘积就是双射，所以均匀分布的$l$映射为一致分布的乘积$l(k-s_1)$。

如果$p$是复合的，那么用一个不是$p$相对素数的值相乘就不是双射，所以均匀分布的$l$可能不能映射到均匀分布的乘积$l(k-s_1)$。