Модульное возведение в степень

[bondik]

Подскажите пожалуйста,есть такое сравнение,знаю X K P нужно найти A.Мне бы алгоритм или кусок кода.

[Sazary]

Если я правильно понял, то вы не знаете как выразить?

Ну, первый вариант - перебором a. Не лучшее решение.
Преобразуем:
a / p =b * p + x^k (из определения остатка от деления).
Умножим на p:
a = b *p*p + p*x^k
Остается только перебирать целочисленное b от 1.

ps На всякий случай, напомните, что значит этот знак "тройное равно"?

[bondik]

Сравнение по модулю,то есть 5=5 mod 1 пять сравнимо с пятью по модулю 1

[Sasha_Smirnov]

Ну какой тут кусок кода... Вот кусок мысли.

(Считаю знак тождественного равенства — обычным равенством (=). А зря**!!!)

p должно быть > чем x^k. Например, когда x^k=10, то остатки (a mod p) тоже равны 10 при p, равном*:
p: 11; 12; 13; ... для a, соответственно равных:
a: 21; 22; 23; ... (a mod p = 10 при их целочисленном частном a \ p = 1)
a: 32; 34; 36; ... (a mod p = 10 при их целочисленном частном a \ p = 2)
a: 43; 46; 49; ... (a mod p = 10 при их целочисленном частном a \ p = 3)

Вот и прикиньте, какой отсюда можно вывести алгоритм. Смотря что дано!

___________________________________ ____
* при этом p, конечно, всегда должно быть больше, чем x^k
** ну да, погорячился... после того, как увидел (вчера), что модуль студентка назвала моделем... прицел сбит!

[Sazary]

Почитал я немного об этом модульном сравнении.
http://ru.wikipedia.org/wiki/Сравнение_по_модулю
В общем, тройное равенство != двойному )

Насколько понял, условие можно переписать как-то так:
x^k mod p = a mod p

Вот нашел в нете pdf-ку о модульном возведении в степень. Прикрепляю.

И еще, как я понял, оно применяется в криптографии. Так что там не все так просто..