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 $\varphi$-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 $\varphi(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 $\varphi(m)$-hez.
5. Keresünk egy olyan $d$ egész számot, amelyre teljesül az $ed\equiv 1\pmod{\varphi(m)}$ kongruencia.