Genişləndirilmiş Evklid alqoritmi və modul tərslər
Qalıqlar kiçilir, hər sətir isə r = x·a + y·n bərabərliyini saxlayır. Qalıq 1 olanda x tərs elementdir. Oyuncaq RSA d-ni verir.
İnteraktiv demonun içindəki yazılar hələlik ingilis dilindədir.
Each row keeps the invariant rᵢ = xᵢ·a + yᵢ·n. When the remainder hits 0, the row above holds gcd(a, n), and if it equals 1, xᵢ mod n is a⁻¹. The defaults are textbook toy RSA: p = 61, q = 53, φ(n) = 3120, e = 17. The inverse is the private exponent d.
| i | qᵢ | rᵢ | xᵢ | yᵢ |
|---|---|---|---|---|
| 0 | 3120 | 0 | 1 | |
| 1 | 17 | 1 | 0 | |
| 2 | 183 | 9 | -183 | 1 |
| 3 | 1 | 8 | 184 | -1 |
| 4 | 1 | 1 | -367 | 2 |
| 5 | 8 | 0 | 3120 | -17 |
gcd(17, 3120) = 1, so a⁻¹ ≡ 2753 (mod 3120). Check: 17 · 2753 mod 3120 = 1.
Nəyə diqqət etməli
- Hər sətir rᵢ = xᵢ·a + yᵢ·n bərabərliyini ödəyir. Bu invariant Bezu eyniliyinin bütün isbatıdır.
- Sətirlərin sayı log n kimi artır, buna görə tərs element hətta 2048 bitlik ədədlər üçün də ucuz hesablanır.
- a = 6, n = 3120 yoxlayın: ƏBOB 6-dır, tərs element yoxdur. RSA-nın gcd(e, φ(n)) = 1 tələb etməsinin səbəbi budur.