сравнение по модулю больших чисел

[bikineev]

Помогите, пожалуйста, студент 2-го курса. Вообщем, задача такая. Известно, что
123^137 mod m = n
Требуется найти Х такое, что
X^137 mod m = p
Числа n, m, p ,очень здоровые, даны. n>p. m -составное.
Преподаватель сказал, что задачу можно решить не обязательно через факторизацию числа m.
Попробовал свести задачу к тому, что
X^137=Q (mod m),
где Q=123^137-(n-p),
но тоже не имею понятия, как это решить.

[Sonic86]

Это Вам прочесть: topic3829.html
- формулы надо в ТеХе набирать.

В зависимости от $m,n,p$ число $X$ может и не существовать, а может быть их и несколько...

bikineev писал(а):

Преподаватель сказал, что задачу можно решить не обязательно через факторизацию числа m.

Серьезно?! не верится что-то...
Можно, конечно $n$ возводить в степени (или умножать на $g^{137}$), пока $p$ не попадется... В принципе - это не через факторизацию, но еще хуже...
Если бы $pn^{-1} \mod m$ было бы просто устроено...
По-моему, какой-то информации не хватает...

[bikineev]

Ну надо написать программу на си, которая бы это число находила. В условие входило лишь еще то, что программа должна находить число за время - не более 2 минут. Я бы с радостью и через факторизацию, но, говорят, работают в этом случае только алгоритмы квадратичного решета, числового поля и алгоритм Ленстры(метод эллиптических кривых), а их я не знаю как прописать на си, в интернете кода не нашел. Поэтому больше ориентируюсь на какой-либо обходной путь очень здоровые - это число m к примеру имеет 100 знаков

[venco]

Может, числа $n,m,p$ какие-то особенные, что можно относительно легко решить?