Расширенный алгоритм Евклида и обратные по модулю
Остатки уменьшаются, а каждая строка сохраняет r = x·a + y·n. Когда остаток равен 1, x и есть обратный элемент. Игрушечный RSA даёт d.
Подписи внутри интерактивного демо пока на английском.
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.
На что обратить внимание
- Каждая строка удовлетворяет rᵢ = xᵢ·a + yᵢ·n. Этот инвариант и есть всё доказательство соотношения Безу.
- Число строк растёт как log n, поэтому обратный элемент вычисляется быстро даже для 2048-битных чисел.
- Попробуйте a = 6, n = 3120: НОД равен 6, обратного нет. Поэтому RSA требует gcd(e, φ(n)) = 1.