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.