Grupul RSA pentru modul $N$ a factorizării secrete este pur și simplu grup multiplicativ de numere întregi modulo $N$, des remarcat $\mathbb Z_N^*$. Acesta poate fi vizualizat sau definit ca un submult de numere întregi $m$ în interval $[0,N)$ cu $\gcd(N,m)=1$. Legea grupului este modul de multiplicare $N$, acesta este $a*b$ este restul Diviziune euclidiană de $a\ori b$, Unde $\ori$ este înmulțirea întregului.
Acest grup are ordinea¹ Euler totient $\varphi(N)$. Această cantitate este necunoscută, de la factorizarea lui $N$ este. Putem calcula cu ușurință $\varphi(N)$ dacă cunoaştem factorizarea $N$, și se dovedește că putem factor $N$ daca stim $N$ și $\varphi(N)$.
Notă: criptarea/decriptarea RSA funcționează adesea în totalitate monoid $[0,N)$ sub înmulțire modulo $N$, mai degrabă decât subsetul de grup $\mathbb Z_N^*$. Acest lucru necesită ca $N$ este fără pătrat pentru ca decriptarea să funcționeze în mod fiabil.
În a lui Benjamin Wesolowski Funcții eficiente de întârziere verificabile (în procedurile EuroCrypt 2019), $(\mathbf Z/N\mathbf Z)^Ã$ este $\mathbb Z_N^*$. Notația lor reflectă o construcție a acestui grup ca restricție la elemente inversabile ale mulțimii de coeficient de clase de echivalenţă în numere întregi (pe care le notează $\mathbf Z$ Decat $\mathbb Z$ de mai sus), pentru relația de echivalență modulo congruent² $N$, conform legii $Ã$ care este compatibil cu această relaţie de echivalenţă. Înțeleg că așa fac băieții de matematică; Nu sunt chiar unul.
Vedea cometariu pentru mai multe referințe despre VDF.
¹ adică, deoarece este o mulțime finită, este numărul de elemente.
² prin definiție, $a\equiv b\pmod N\iff\exists q,\,a=b+q\times N$, cu toate cantitățile în $\mathbb Z$.
