Score:4

Are there prime numbers that are easy to modulo within 40 bits to 60 bits?

cn flag
Bob

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

Score:10
ng flag

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.

gnasher729 avatar
kz flag
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.
Score:1
my flag

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)

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.