Вычисление mod

[ult1m]

Источник формулы http://ru.wikipedia.org/wiki/RSA, таблица "Пример"

e = 3; φ(n) = 9167368.

отсюда получается d = 6111579.

Как происходит вычисление d? У меня получается:
е^{-1} mod φ(n) = е^{-1}
т.к. е < φ(n).

[gris]

А здесь же степень понимается как степень в кольце вычетов. То есть, например,

$2^{3} \mod 5 =3$, но и

$2^{-1} \mod 5 =3$, так как $2\cdot 3 \mod 5 =1$

Символ $-1$ находится в связке с $\mod 2$, а не понимается как обратное в кольце рациональных чисел, где $2^{-1}=1/2$.

[ult1m]

Поясните значение символа "степени" во втором примере - не понимаю как получается "3". В первом примере:

$8 \mod 5 = 3$

?

Тогда почему во втором примере по-другому? В примерах, которые нашел - решение не расписывается, просто

$X^{n} \mod Y = Z$,

без объяснений.

[gris]

В кольце вычетов $\mathrm {Z}_n$ есть операция умножения, единица и обратные элементы (при простом $n$ ) . Степень $k^{-1}$ есть просто обратный элемент для $k$.
Как найти $3^{-1}$ в $\mathrm {Z}_7$, например?
Надо найти такое натуральное $k$, чтобы произведение $3\cdot k$ имело остаток 1 при делении на 7.
То есть $3^{-1}=k\in \mathrm {Z}_7: 3k \mod 7 =1$
В данном случае легко найти ответ: $3\cdot 5=15$.
$15=2\cdot 7 +1 \equiv 1 \mod 7$

[Cash]

В общем случае, для того, чтобы найти $a^{-1}$ в кольце вычетов по модулю $n$, вам нужно решить диофантово уравнение $ax+ny=1$. $x$ и будет обратным элементом.

Как его решить? Гуглите фразу Алгоритм Евклида.