Az RSA algoritmus helyes működése

Tegyük fel, hogy teljesülnek az alábbi feltételek:

1. Választunk két tetszőleges, egymástól különböző pozitív $p$ és $q$ prímszámot.
2. Képezzük ezekből az $m=pq$ modulust.
3. Képezzük az Euler-féle $\phi$-függvény értékét az $m$ modulusra, azaz a 21.3. és a 21.5. Tételek alapján kiszámítjuk a $\phi (m)=(p-1)(q-1)$ egész számot.
4. Választunk egy tetszőleges $e$ egész számot, amely relatív prím $\phi (m)$-hez.
5. Keresünk egy olyan $d$ egész számot, amelyre teljesül az $ed\equiv 1(\mathrm{mod}\phi (m))$ kongruencia.