Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I want to implement LWE-based encryption scheme, the modulo $q$ could be decomposed as $q = q_0\cdot q_1\cdots q_k$ according to CRT. I guess the modular arithmetic by $q_i$ is key operation, so I try to choose the Mersenne prime. However, there are only two primes satisfied: $2^{31}-1$ and $2^{61}-1$.
Are there any other primes such as $2^n-b$ that are easy to modulo(It better be between $2^{40}$ and $2^{60}$)?
First, this is obviously true with no restrictions on $b$. For example, for $b = 2^n-2$ we get that $2^n - b = 2^n - (2^n-2) = 2$ is prime. This is boring, and likely not what you mean (and instead, I imagine you want $b$ small).
How small of $b$ should we expect for this to hold for? One interpretation of the Prime Number Theorem is that the primes have "density $1/\ln x$". This is to say that, when $x = 2^{40}$ to $2^{60}$, we (roughly) expect $\approx 1/40$ to $1/60$ numbers to be prime. There are various ways of formalizing this (depending on whether you believe in the Riemann Hypothesis), see this page, especially the "generalizations" section.
Anyway, the takeaway should be that
This is to say that it is simple to write a program that searches for the smallest positive $b$ such that $2^n-b$ is prime. The following is a Sage program, and should demonstrate how simple things are (provided primality testing is implemented).
def find_b(n):
q = 2**n
b = 0
while not (q-b).is_prime():
b += 1
return b
As you are interested in the cases of $2^{40}$ to $2^{60}$, I've computed those for you below
[(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)].
The data format is that $(a,b)$ denotes the number $2^a-b$, so for example the first entry is the number $2^{40}-87$. All numbers in the above list are prime. Moreover, the choice of $b$ in the above is (as mentioned before) always the minimal choice such that $(a,b)$ is prime. Executing this program is extremely efficient, it took well under a second on my desktop.
That all being said, the precise structure of $q_i$ that admit efficient arithmetic is a little more complex than what you describe, at least when doing Ring-LWE type things (where you are using polynomial arithmetic). Here, being able to utilize Number Theoretic Transforms (even if only "incomplete" ones) is quite useful. This imposes fairly strong requirements on the precise form of the moduli chosen (for complete NTTs, you need $q\equiv 1\bmod 2n$ when working in $\mathbb{Z}_q[x]/(x^n+1)$ iirc). That being said, these optimizations are perhaps a little more technically involved, so perhaps should be skipped initially when learning about encryption.
I want to implement LWE-based encryption scheme, the modulo $q$ could be decomposed as $q = q_0\cdot q_1\cdots q_k$ according to CRT.
Actually, for CRT to work, all that is necessarily is that the factors be relatively prime, they don't need to be individually prime. $2^x-1$ and $2^y-1$ will be relatively prime whenever $x$ and $y$ are; hence all you need is a set of exponents from the range $[40, 60]$ that are relatively prime.
One obvious choice would be to use the factors $2^{p}-1$ for $p \in \{41, 43, 47, 49, 53, 55, 57, 58, 59\}$ (which is, I believe, the set of mutually prime values from that range with the maximum sum); that may be sufficient to meet your needs (if $q \approx 2^{462}$ is sufficiently large)
