Có số nguyên tố nào dễ điều chỉnh trong phạm vi 40 bit đến 60 bit không?

Tôi muốn triển khai lược đồ mã hóa dựa trên LWE, modulo $q$ có thể được phân hủy như $q = q_0\cdot q_1\cdots q_k$ theo CRT. Tôi đoán số học mô-đun bằng $q_i$ là thao tác chính, vì vậy tôi cố gắng chọn số nguyên tố Mersenne. Tuy nhiên, chỉ có hai số nguyên tố thỏa mãn: $2^{31}-1$ và $2^{61}-1$.

Có bất kỳ số nguyên tố nào khác như $2^n-b$ dễ modulo (Tốt hơn là ở giữa $2^{40}$ và $2^{60}$)?

Đầu tiên, điều này rõ ràng là đúng mà không có hạn chế nào về $b$. Ví dụ, đối với $b = 2^n-2$ chúng tôi hiểu điều đó $2^n - b = 2^n - (2^n-2) = 2$ là nguyên tố. Điều này thật nhàm chán và có thể không phải ý của bạn (và thay vào đó, tôi tưởng tượng bạn muốn $b$ bé nhỏ).

Làm thế nào nhỏ của $b$ chúng ta nên mong đợi điều này để giữ cho? Một cách giải thích Định lý số nguyên tố là các số nguyên tố có "mật độ $1/\ln x$“. Điều này muốn nói rằng, khi $x = 2^{40}$ đến $2^{60}$, chúng tôi (khoảng) mong đợi $\xấp xỉ 1/40$ đến $1/60$ các số phải là số nguyên tố. Có nhiều cách khác nhau để chính thức hóa điều này (tùy thuộc vào việc bạn có tin vào Giả thuyết Riemann hay không), xem trang này, đặc biệt là phần "tổng quát hóa".

Dù sao đi nữa, điều nên làm là

1. số nguyên tố tương đối "dồi dào", vì vậy
2. để tìm các số nguyên tố (ở dạng bạn muốn), "chỉ cần nhìn".

Điều này có nghĩa là thật đơn giản để viết một chương trình tìm kiếm số dương nhỏ nhất $b$ như vậy mà $2^n-b$ là nguyên tố. Sau đây là chương trình Sage và sẽ chứng minh mọi thứ đơn giản như thế nào (miễn là thử nghiệm tính nguyên thủy được triển khai).

xác định find_b(n):
    q = 2**n
    b = 0
    trong khi không (q-b).is_prime():
        b += 1
    trả lại b

Như bạn đang quan tâm đến các trường hợp của $2^{40}$ đến $2^{60}$, tôi đã tính toán cho bạn dưới đây

[(40, 87), (41, 21), (42, 11), (43, 57), (44, 17), (45, 55), (46, 21), (47, 115), (48, 59), (49, 81), (50, 27), (51, 129), (52, 47), (53, 111), (54, 33), (55, 55), (56, 5), (57, 13), (58, 27), (59, 55), (60, 93)].

Định dạng dữ liệu là $(a,b)$ biểu thị số $2^a-b$, vì vậy, ví dụ, mục nhập đầu tiên là số $2^{40}-87$. Tất cả các số trong danh sách trên là số nguyên tố. Hơn nữa, sự lựa chọn của $b$ ở trên là (như đã đề cập trước đây) luôn là sự lựa chọn tối thiểu sao cho $(a,b)$ là nguyên tố. Việc thực thi chương trình này cực kỳ hiệu quả, chỉ mất chưa đầy một giây trên máy tính để bàn của tôi.

Như đã nói, cấu trúc chính xác của $q_i$ thừa nhận số học hiệu quả phức tạp hơn một chút so với những gì bạn mô tả, ít nhất là khi thực hiện các loại Ring-LWE (nơi bạn đang sử dụng số học đa thức). Ở đây, việc có thể sử dụng các Biến đổi Lý thuyết Số (ngay cả khi chỉ những biến đổi "không hoàn chỉnh") là khá hữu ích. Điều này áp đặt các yêu cầu khá chặt chẽ đối với dạng chính xác của các mô đun đã chọn (đối với các NTT hoàn chỉnh, bạn cần $q\tương đương 1\bmod 2n$ khi làm việc trong $\mathbb{Z}_q[x]/(x^n+1)$ iirc). Điều đó đang được nói, những tối ưu hóa này có lẽ liên quan nhiều hơn đến kỹ thuật, vì vậy có lẽ nên bỏ qua bước đầu khi tìm hiểu về mã hóa.

Tôi muốn triển khai lược đồ mã hóa dựa trên LWE, modulo $q$ có thể được phân hủy như $q = q_0\cdot q_1\cdots q_k$ theo CRT.

Trên thực tế, để CRT hoạt động, tất cả những gì cần thiết là các thừa số phải nguyên tố tương đối, chúng không cần phải nguyên tố riêng lẻ. $2^x-1$ và $2^y-1$ sẽ tương đối nguyên tố bất cứ khi nào $x$ và $y$ là; do đó tất cả những gì bạn cần là một tập hợp các số mũ từ phạm vi $[40, 60]$ tương đối nguyên tố.

Một sự lựa chọn rõ ràng là sử dụng các yếu tố $2^{p}-1$ vì $p \in \{41, 43, 47, 49, 53, 55, 57, 58, 59\}$ (tôi tin rằng đó là tập hợp các giá trị nguyên tố lẫn nhau từ phạm vi đó với tổng tối đa); có thể đủ để đáp ứng nhu cầu của bạn (nếu $q \khoảng 2^{462}$ đủ lớn)