4
$\begingroup$

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}$)?

$\endgroup$
0

2 Answers 2

10
$\begingroup$

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

  1. prime numbers are relatively "plentiful", so
  2. to find prime numbers (of your desired form), "just look".

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.

$\endgroup$
1
  • $\begingroup$ True story: In the mid eighties, I cracked an RSA key with pencil and paper. The geniuses had used a table from "The art of computer programming" to use the tenth prime below 2^60 and the tenth prime above 2^63 as the private key, so the product was very easy to factor. $\endgroup$
    – gnasher729
    May 4, 2022 at 0:05
1
$\begingroup$

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.