Алгоритм Полига-Хеллмана. Есть одна непонятка.

[Denmarino111]

Здравствуйте. Сечас реализую алгоритм Полига-Хеллмана. (Вычисление дискретного логарифма по модулю простого числа...) И наткнулся в учебнике на формулу. Не понимаю как она считается. Выложу пример. Объясните пожалуйста как такие вещи считаются вообще.$x=(7\cdot4^{-1})^{15} \pmod {61}$
тоесть там нельзя просто 7 поделить на 4. Должно получится целое число. Полный алгоритм есть на Вики http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9F%D0%BE%D0%BB%D0%B8%D0%B3%D0%B0_%E2%80%94_%D0%A5%D0%B5%D0%BB%D0%BB%D0%BC%D0%B0%D0%BD%D0%B0 . Там ниже середины страницы есть пример, и в нем похожий пример.

[Joker_vD]

$4\cdot4^{-1}\equiv1\pmod{61}$. Это значит, что есть такие целые числа $a$ и $b$, что $4a+61b=1$, причем $a$ как раз и прокатит за $4^{-1}$. Находятся $a,b$ с помощью алгоритма Евклида.

[Denmarino111]

Не понял немного.Не могли бы вы на моём примере показать как нужно считать. Или дать ссылку может на какую-нибудь статью

[Joker_vD]

$4=4\cdot1+61\cdot0,\;61=4\cdot0+61\cdot1$ — вычитаем из второго равенства первое, умноженное на $15$: $1=4\cdot(-15)+61\cdot1$. Хм, повезло.

Ну так вот, $4\cdot(-15)+61\cdot1=1$, т.е. $-15\equiv46\equiv4^{-1}\pmod{61}$. Можете проверить: $4\cdot46=184=3\cdot61+1$.

[Denmarino111]

Тоесть мы сначала ищем нужные коэффициенты при 4 и при 61, чтобы получились равенства $4=4\cdot1+61\cdot0,\;61=4\cdot0+61\cdot1$ . Хотя они вроде бы всегда равны 0 и 1. Зачем тогда писать еще $0\cdot 4$ и $0\cdot 61$? Затем вычитаем из второго первое, умноженное на степень. И искомое число получается равно коэффициенту при четверке?

Да и вообще. Оно всегда будет равно степени со знаком минус.

-- 28.03.2013, 17:00 --

ерунда какая-то. А что если, например надо рассчитать $7531\cdot 6^{-1} (\mod 8101)$ .

[Joker_vD]

$6^{-1}\equiv x\pmod{8101}$, найти $x$?

$6=6\cdot1+8101\cdot0,\;8101=6\cdot0+8101\cdot1$, делаем шаг: $8101=1350\cdot6+1$... слушайте, вы специально такие примеры подбираете, что алгоритм Евклида ровно один шаг делает?
$1=6\cdot(-1350)+8101\cdot1$, откуда $6^{-1}\equiv-1350\equiv6751\pmod{8101}$.

[Denmarino111]

А не подскажете где об этом подробно написано?

[Joker_vD]

Ну например: http://ru.wikipedia.org/wiki/Алгоритм_Евклида — в разделе "Расширенный алгоритм Евклида и соотношение Безу".