Như Hilder đã đề cập, thông qua kỹ thuật "chuyển đổi mô đun", sự lựa chọn cụ thể của $q$ không quan trọng lắm đối với tính bảo mật của LWE.
Vì vậy, hình thức cụ thể của $q$ chủ yếu là để cho phép cải thiện hiệu quả.
Tôi đã nhầm người khi liệt kê đầy đủ tất cả chúng, nhưng người ta có thể dễ dàng chỉ ra một số bằng cách đọc các đề xuất của NIST PQC KEM.
Ví dụ:
Lựa chọn $q = 2^k$ cho một số $k$ cho phép một người thay thế việc giảm mô-đun bằng $q$ với sự thay đổi bit, một hoạt động rẻ hơn. Đây là một phần lý do mà Saber chọn $q = 2^{13}$.
Lựa chọn $q$ trở thành "NTT thân thiện". NTT là một dạng tương tự nhất định của FFT "mod $q$" (thay vì kết thúc $\mathbb{C}$) có thể cho phép tăng tốc lớn trong phép nhân đa thức (khoảng từ $O(n^2)$ sự phức tạp ngây thơ đến $O(n\log n)$). Kích thước của việc tăng tốc được liên kết trực tiếp với việc có một chất tương tự phù hợp của $i\in\mathbb{C}$. Trường hợp tốt nhất (nói khi làm việc trên $\mathbb{Z}_q[x]/(x^n+1)$ vì $n = 2^k$) xảy ra khi bạn có một "nguyên thủy $2n$gốc của sự thống nhất", điều này xảy ra khi $q\tương đương 1\bmod 2n$ (Tôi nghĩ). Lưu ý rằng điều này không tương thích với tối ưu hóa trước đó. KEM Kyber đưa ra lựa chọn này (gần như, có những khác biệt nhỏ về kỹ thuật).
Lựa chọn $q$ là sản phẩm của các đồng nguyên tố nhỏ (cỡ từ), vì vậy người ta có thể sử dụng định lý Phần dư Trung Quốc và giữ tất cả kích thước từ số học. Tôi không biết KEM nào làm được điều này, nhưng điều này phổ biến trong tài liệu của FHE (và thường có tên là "Hệ thống số dư" hoặc số học RNS).
Vì vậy, có những lý lẽ để lựa chọn $q \equiv 0 \bmod 2^k$, $q\equiv 1\bmod 2\times 2^k$, và $q$ tích của các đồng nguyên tố nhỏ. Tất cả những điều này dường như là tối ưu hóa loại trừ lẫn nhau, nhưng một người có thể hơi thông minh và sử dụng nhiều tối ưu hóa cùng một lúc.
Ví dụ, có công việc này về nhúng mod số học $2^k$ (tức là "giảm mô-đun thân thiện") thành một vòng thân thiện với NTT, cho phép một người sử dụng cả tối ưu hóa 1 và 2.
