Reducere Barret pentru a obține restul de 64 de biți dintr-un număr de 128 de biți

Codul întrebării calculează pe 64 de biți obține<2>(I)=$h:=f\,g\bmod n$ din intrări:

• pe 64 de biți valoarea_modulului=$n$ cu $n\în[2,\,2^{63}]$
• pe 64 de biți obține<0>(I)=$f$ cu $f\in[0,\,2^{64}-1]$
• pe 64 de biți obține<1>(I)=$g$ cu $g\in[0,\,2^{64}-1]$ și $f\,g<2^{64}\,n$, o condiție care este îndeplinită dacă $f,g\in[0,\,n-1]$ (ceea ce cred că este întotdeauna cazul în aplicație).

Rezultatul $h$ este restul diviziunii euclidiene a $f\,g$ de $n$. Este definit matematic de $0\le h<m$ și $\există q\in\mathbb Z,\ f\,g=q\cdot n+h$.

Codul calculează mai întâi 128 de biți z$=z:=f\,g$, apoi rezultatul obține<2>(I)$=h:=z\bmod n$ de Reducere Barrett:

• A fost precalculat (extern la codul întrebării) const_ratio$=r=\left\lfloor2^{128}/n\right\rfloor$
• $\hat q:=\left\lfloor z\,r/2^{128}\right\rfloor$, care este corect $q$ în cadrul unuia în mod implicit (notă: $\hat q$ este valoarea finală a variabilei tmp1).
• $\hat h:=z-q\cdot n$, care este corect $h$ în limita posibil unui exces de exact $n$ (Notă: $\hat h$ este valoarea finală a variabilei tmp3).
• $h:=\hat h-n$ când $\hat h\ge n$, sau $h:=\hat h$ in caz contrar.

Codul folosește algoritmi de școală primară pentru a efectua aritmetica cu mai multe cifre, transpusă de la bază $10$ la baza $2^{64}$ (cu optimizări și o variantă detaliată în secțiunea următoare). Echivalentul cifrelor sunt așa-numitele membrelor, aici pe 64 de biți.

Produsul z$=z$ este exprimată ca două membre z[0]$=z_0$ (de ordin scăzut), z[1]$=z_1$ (de ordin înalt), deci cu $z=z_0+2^{64}\,z_1$, și $z_0, z_1\in[0,\,2^{64}-1]$.

Multiplicatorul Barrett const_ratio$=r=\left\lfloor2^{128}/n\right\rfloor$ este exprimat în mod similar ca două membre const_ratio_0$=r_0$ și const_ratio_1$=r_1$, datorită capătului inferior al intervalului în precondiție $n\în[2,\,2^{63}]$.

Produsul intermediar $z\,r$ se potrivește întotdeauna trei membre (chiar dacă în general produsul a două cantități exprimate ca două membre ar necesita patru membre).

În mod implicit, coeficientul tentativ $\hat q$ se potrivește unui singur membru, deoarece $\hat q\le q$ și $q<2^{64}$, cu cel mai recent asigurat prin precondiția de intrare $f\,g<2^{64}\,n$.

Restul tentativ $\hat h$ se potrivește unui singur membru, deoarece $\hat h<2n$ și $2n\le2^{64}$, cu mulțumirea ulterioară la capătul înalt al intervalului în precondiție $n\în[2,\,2^{63}]$.

Detalierea algoritmului codului (așa cum se cere în cometariu și recompensă):

Voi folosi o ilustrație în zecimală. În acea bază, din moment ce $2\le n\le10/2$, const_ratio$=r$ poate fi doar $\left\lfloor100/2\right\rfloor=50$, $\left\lfloor100/3\right\rfloor=33$, $\left\lfloor100/4\right\rfloor=25$, $\left\lfloor100/5\right\rfloor=20$, dar mă voi preface const_ratio$=r=29$ pentru că asta face un exemplu mai interesant. Din același motiv voi folosi z$=z=34$, chiar dacă aceasta nu poate fi obținută ca produs de două cifre.

Produsul z se obtine in cod prin multiplica_uint64(get<0>(I), get<1>(I), z) ca două membre z[0] și z[1].

Carnea calculului este $\hat q:=\left\lfloor z\,r/2^{128}\right\rfloor$. Acesta este analogul de bază $2^{64}$ de $9:=\stânga\lfloor29\cdot34/100\right\rfloor$ în baza 10. Ambele argumente $29$ și $34$ la înmulțire sunt de două cifre, dar suficient de mici încât produsul lor $986$ este format din trei cifre (mai degrabă decât patru) și ne interesează doar a treia cifră din dreapta. Algoritmul școlii primare de calculat $986:=29\cdot34$ ar fi prezentat ca

      2 9 const_ratio
   x 3 4 z
    -----
    1 1 6
+ 8 7
  -------
    9 8 6

În algoritmul școlii primare există patru înmulțiri cu o singură cifră (pe care codul le efectuează) și câteva operații suplimentare (pe care codul le reorganizează ușor):

• 4 ori 9, 36; scrie 6, a pastra 3;
• 4 ori 2, 8; plus 3 (ținut), 11; scrie asta.
• 3 ori 9, 27; scrie 7, a pastra 2;
• 3 ori 2, 6; plus 2 (ținut), 8; scrie asta.

Prima dintre aceste patru înmulțiri are loc în fragmentul de cod multiply_uint64_hw64(z[0], const_ratio_0, &carry), care multiplica limbul de ordin inferior al $r$ cu membrul de ordin inferior al $z$, cum am înmulți cifra de ordin inferioară 4 de 34 cu cifra de ordin inferior 9 de 29. Observați că „scrie 6" este inutilă în această circumstanță, deoarece orice cifră pe care o scrie va rămâne separată în coloana din dreapta a calculului, fără nicio oportunitate de a influența o cifră din stânga, și ignorată atunci când împărțim la 100 și rotunjim în jos (în mod echivalent, păstrăm doar a treia cifră din dreapta). De aceea, 64 de biți de ordin scăzut al produsului pe 128 de biți nici măcar nu este calculat, așa cum se menționează în întrebare. Echivalentul 3 în 36 este păstrat în transporta.

A doua înmulțire are loc în multiply_uint64(z[0], const_ratio_1, tmp2), care multiplică limbul de ordin înalt al $r$ cu membrul de ordin inferior al $z$, cu rezultat în cele două membre ale tmp2; pe 64 de biți tmp[0] primește echivalentul a 8 în 8, și tmp[1] primește echivalentul a 0 pentru (observați o conducere 0 este suprimată în scrierea convențională a numerelor întregi zecimale). Echivalentul lui 8 plus 3 se întâmplă în add_uint64(tmp2[0], carry, &tmp1), cu cifra de ordin inferioară 1 a rezultatului 11 în tmp1, și noul carry 1 în ieșirea acelei funcții. Acesta este folosit ca operand drept în tmp3 = tmp2[1] + â¦ (care se întâmplă să fie omis în algoritmul școlii primare cu exemplul particular pe care l-am luat de la 0 a fost suprimat), dând echivalentul stângi 1 în 116. [Notă despre ieșirea de add_uint64: este generat de static_cast<unsigned char>(*rezultat < operand1), care compară *rezultat și operand, apoi se întoarce Adevărat la 1, fals la 0. Făcut după *rezultat = operand1 + operand2, care spune dacă această adăugare a generat un carry. Unii compilatori recunosc acest idiom, folosesc bitul C al cuvântului de stare și refolosesc C în adiția viitoare].

A treia înmulțire are loc în multiply_uint64(z[1], const_ratio_0, tmp2), care multiplica limbul de ordin inferior al $r$ cu membrul de ordin înalt al $z$, cu rezultat asupra membrelor în tmp2, așa cum facem noi 3 x 9 = 27. De data aceasta avem nevoie de ambele membre/cifre: echivalentul lui 7 se duce la tmp2[0] iar echivalentul lui 2 se duce la tmp2[1]. Aici este făcută o variantă a algoritmului de școală primară: se adaugă imediat tmp1 (echivalentul mijlocului 1 în 116) la membrul de ordin inferior cu add_uint64(tmp1, tmp2[0], &tmp1), efectuând echivalentul a 1 + 7 = 8, fără transport. Rezultatul 8 este stocat în tmp1 deoarece semantica lui add_uint64 are nevoie de o destinație, dar este cu adevărat ignorată, pentru că nu ne pasă de cifra din mijloc 986. Ieșirea de transport de către add_uint64 este folosit ca operand drept în purtare = tmp2[1] + â¦, efectuând echivalentul a 1 + 0 = 1 în exemplul nostru. În ciuda numelui transporta, care deține un membru/cifră complet de 64 de biți.

A patra înmulțire are loc în z[1] * const_ratio_1, care multiplică limbul de ordin înalt al $r$ cu membrul de ordin înalt al $z$, așa cum facem noi 3 x 2 = 6. Aici contextul asigură că rezultatul se potrivește unui singur membru, astfel încât operatorul C nativ pentru multiplicare poate fi utilizat. Rezultatul este apoi folosit ca operator stânga al ⦠+ tmp3 + carry, efectuând echivalentul a 6 + 1 + 1 = 8. Din nou contextul asigură aceste valori $\hat q$, stocat in tmp1, se potrivește unui singur membru/cifră.

Atunci tmp3 = z[0] - tmp1 * valoare_modul execută $\hat h:=z-q\cdot n$. Contextul asigură că rezultatul exact din punct de vedere matematic se potrivește unui singur membru/cifră (stocat în tmp3) chiar dacă $q\cdot n$ nu. Acest lucru permite utilizarea operatorilor nativi C, care omit complet calculul membrului de ordin înalt.

Atunci SEAL_COND_SELECT(tmp3 >= modulus_value, tmp3 - modulus_value, tmp3) calculează $h$ din $\hat h$ prin scăderea condiționată $n$ când $\hat h\ge n$. Operatorul de selecție este ascuns într-o macrocomandă.

Două exemple pentru bază $2^{64}$ (valori în hexazecimal big-endian cu spațiu inserat între membre):

valoarea_modulului 000076513ae0b1cd
const_ratio 00000000000229e6 7f4ca82ba3a115f1
obține<0>(I) 00005f0fd669f2c7
obține<1>(I) 000041a1f91ef16f
z 00000000185f2ae8 a455846cb7cf9b49
tmp1 000034bb854f9a8d
tmp3 00000fcebfd55b60
obţine<2>(I) 00000fcebfd55b60

valoarea_modulului 686f4b7702a9c775
const_ratio 0000000000000002 7387d66ffd685b82
obține<0>(I) 536094611fa2b19b
obține<1>(I) 675ef5187093ff63
z 21aac8fcf31d6421 62e675ba16d513f1
tmp1 5287278703394bb1
tmp3 72b1d3d2b9f5e50c
obţine<2>(I) 0a42885bb74c1d97

Notă: pentru $n\în[2^{63}+1,\,2^{64}-1]$, cantitatea $\hat h$ poate deborda un membru și codul așa cum este eșuează. De exemplu. pentru intrare $f=g=2^{32}$, primim $z=2^{64}$ prin urmare $\hat q=0$ (pentru orice $n>2^{63}$), prin urmare $\hat h=z=2^{64}$ și o ieșire de $0$ mai degrabă decât adevăratul $h=2^{64}-n$. Sursa completă are un comentariu „clasa Modulus reprezintă un modul întreg nenegativ de până la 61 de biți”, astfel încât astfel de probleme pentru mari $n$ apare numai atunci când codul de apel este greșit. În plus, dacă am înțeles bine, $n=2^{60}-2^{14}+1$ este ținta principală.

Alternativă: pentru ceva care îndeplinește aceeași funcție ca codul întrebării, în 4 linii scurte de cod în loc de 11, pentru toate $n\în[1,\,2^{64}-1]$, care nu necesită precalcul, posibil mai rapid, dar compatibil doar cu compilatoarele x64 recente + CPU-uri, vezi primul dintre aceste fragmente de cod (a doua este o variantă mică fără restricție $f\,g<2^{64}\,n$ ). Nu fac nicio declarație despre caracterul constant al vreunui cod.