Существуют ли простые числа, которые легко вычислить по модулю в пределах от 40 до 60 бит?

Я хочу реализовать схему шифрования на основе LWE по модулю $q$ можно разложить как $q = q_0\cdot q_1\cdots q_k$ по данным КРТ. Я предполагаю, что модульная арифметика $q_i$ является ключевой операцией, поэтому я стараюсь выбрать простое число Мерсенна. Однако удовлетворяются только два простых числа: $2^{31}-1$ и $2^{61}-1$.

Существуют ли какие-либо другие простые числа, такие как $2^n-b$ которые легко по модулю (лучше быть между $2^{40}$ и $2^{60}$)?

Во-первых, это очевидно верно без каких-либо ограничений на $b$. Например, для $b = 2^n-2$ мы получаем это $2^n - b = 2^n - (2^n-2) = 2$ является простым. Это скучно и, вероятно, не то, что вы имеете в виду (и вместо этого, я думаю, вы хотите $b$ небольшой).

Насколько мало $b$ мы должны ожидать, что это будет продолжаться? Одна из интерпретаций теоремы о простых числах состоит в том, что простые числа имеют «плотность $1/\ln х$". Это к тому, что когда $х = 2^{40}$ к $2^{60}$, мы (примерно) ожидаем $\примерно 1/40$ к $1/60$ числа быть простыми. Существуют различные способы формализации этого (в зависимости от того, верите ли вы в гипотезу Римана), см. эта страница, особенно раздел "обобщения".

В любом случае, вывод должен быть таким.

1. простые числа относительно «многочисленны», поэтому
2. чтобы найти простые числа (желаемой формы), "просто посмотрите".

Это означает, что легко написать программу, которая ищет наименьшее положительное значение. $b$ такой, что $2^n-b$ является простым. Ниже приведена программа Sage, которая должна продемонстрировать, насколько все просто (при условии, что реализовано тестирование на простоту).

защита find_b(n):
    д = 2**п
    б = 0
    пока нет (q-b).is_prime():
        б += 1
    вернуть б

Поскольку вас интересуют случаи $2^{40}$ к $2^{60}$, я вычислил их для вас ниже

[(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)].

Формат данных такой $(а,б)$ обозначает число $2^а-б$, так что, например, первая запись - это число $2^{40}-87$. Все числа в приведенном выше списке являются простыми. Более того, выбор $b$ в приведенном выше (как упоминалось ранее) всегда минимальный выбор такой, что $(а,б)$ является простым. Выполнение этой программы чрезвычайно эффективно, на моем рабочем столе это заняло меньше секунды.

При этом точная структура $q_i$ которые допускают эффективную арифметику, немного сложнее, чем то, что вы описываете, по крайней мере, когда вы делаете вещи типа Ring-LWE (где вы используете полиномиальную арифметику). Здесь возможность использовать теоретико-числовые преобразования (даже если только «неполные») весьма полезна. Это накладывает довольно жесткие требования на точный вид выбранных модулей (для полных НТТ нужно $q\экв 1\bmod 2n$ при работе в $\mathbb{Z}_q[x]/(x^n+1)$ iirc). При этом эти оптимизации, возможно, немного сложнее с технической точки зрения, поэтому, возможно, их следует пропустить при изучении шифрования.

Я хочу реализовать схему шифрования на основе LWE по модулю $q$ можно разложить как $q = q_0\cdot q_1\cdots q_k$ по данным КРТ.

На самом деле, для того, чтобы CRT работала, необходимо, чтобы факторы были относительно простыми, они не обязательно должны быть простыми по отдельности. $2^x-1$ и $2^y-1$ будет относительно простым всякий раз, когда $х$ и $у$ находятся; следовательно, все, что вам нужно, это набор показателей из диапазона $[40, 60]$ которые являются относительно простыми.

Одним из очевидных вариантов было бы использование факторов $2^{р}-1$ за $p \in \{41, 43, 47, 49, 53, 55, 57, 58, 59\}$ (что, как я полагаю, является набором взаимно простых значений из этого диапазона с максимальной суммой); этого может быть достаточно для удовлетворения ваших потребностей (если $q \приблизительно 2^{462}$ достаточно большой)