Există numere prime care sunt ușor de modulat între 40 de biți și 60 de biți?

Vreau să implementez schema de criptare bazată pe LWE, modulo $q$ ar putea fi descompus ca $q = q_0\cdot q_1\cdots q_k$ conform CRT. Presupun că aritmetica modulară de $q_i$ este operația cheie, așa că încerc să aleg Mersenne prime. Cu toate acestea, există doar două numere prime satisfăcute: $2^{31}-1$ și $2^{61}-1$.

Există și alte numere prime, cum ar fi $2^n-b$ care sunt ușor de modulo (Ar fi mai bine să fie între $2^{40}$ și $2^{60}$)?

În primul rând, acest lucru este în mod evident adevărat, fără restricții $b$. De exemplu, pentru $b = 2^n-2$ înţelegem asta $2^n - b = 2^n - (2^n-2) = 2$ este prim. Este plictisitor și probabil nu ceea ce vrei să spui (și în schimb, îmi imaginez că vrei $b$ mic).

Cât de mic de $b$ ar trebui să ne așteptăm ca asta să țină? O interpretare a teoremei numerelor prim este că numerele prime au „densitate $1/\ln x$". Asta înseamnă că, când $x = 2^{40}$ la $2^{60}$, ne așteptăm (aproximativ). $\aproximativ 1/40$ la $1/60$ numerele să fie prime. Există diferite moduri de a formaliza acest lucru (în funcție de credința sau nu în Ipoteza Riemann), vezi această pagină, în special secțiunea „generalizări”..

Oricum, takeaway-ul ar trebui să fie asta

1. numerele prime sunt relativ „abundente”, deci
2. pentru a găsi numere prime (de forma dorită), „doar uita-te”.

Asta înseamnă că este simplu să scrii un program care caută cel mai mic pozitiv $b$ astfel încât $2^n-b$ este prim. Următorul este un program Sage și ar trebui să demonstreze cât de simple sunt lucrurile (cu condiția ca testarea primarității să fie implementată).

def find_b(n):
    q = 2**n
    b = 0
    în timp ce nu (q-b).is_prim():
        b += 1
    întoarcere b

Deoarece vă interesează cazurile de $2^{40}$ la $2^{60}$, le-am calculat pentru tine mai jos

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

Formatul datelor este acela $(a,b)$ denotă numărul $2^a-b$, deci, de exemplu, prima intrare este numărul $2^{40}-87$. Toate numerele din lista de mai sus sunt prime. Mai mult, alegerea de $b$ în cele de mai sus este (după cum am menționat mai sus) întotdeauna alegerea minimă astfel încât $(a,b)$ este prim. Executarea acestui program este extrem de eficientă, a durat mai puțin de o secundă pe desktopul meu.

Toate acestea fiind spuse, structura precisă a $q_i$ care admit că aritmetica eficientă este puțin mai complexă decât ceea ce descrieți, cel puțin atunci când faceți lucruri de tip Ring-LWE (unde utilizați aritmetica polinomială). Aici, posibilitatea de a utiliza Transformările teoretice ale numerelor (chiar dacă sunt doar „incomplete”) este destul de utilă. Acest lucru impune cerințe destul de puternice asupra formei precise a modulelor aleși (pentru NTT-uri complete, aveți nevoie de $q\equiv 1\bmod 2n$ când lucrezi în $\mathbb{Z}_q[x]/(x^n+1)$ iirc). Acestea fiind spuse, aceste optimizări sunt poate puțin mai implicate din punct de vedere tehnic, așa că poate că ar trebui să fie ignorate inițial atunci când învățați despre criptare.

Vreau să implementez schema de criptare bazată pe LWE, modulo $q$ ar putea fi descompuse ca $q = q_0\cdot q_1\cdots q_k$ conform CRT.

De fapt, pentru ca CRT să funcționeze, tot ceea ce este neapărat este ca factorii să fie relativ primi, nu trebuie să fie primii individual. $2^x-1$ și $2^y-1$ va fi relativ prim oricând $x$ și $y$ sunt; prin urmare, tot ce aveți nevoie este un set de exponenți din gamă $[40, 60]$ care sunt relativ prime.

O alegere evidentă ar fi folosirea factorilor 2$^{p}-1$ pentru $p \în \{41, 43, 47, 49, 53, 55, 57, 58, 59\}$ (care este, cred, setul de valori reciproc prime din acel interval cu suma maximă); care poate fi suficient pentru a vă satisface nevoile (dacă $q \aproximativ 2^{462}$ este suficient de mare)