X ^ Y mod Z = R (Как найти Х?)

Автор темы tapatio 
ОбъявленияПоследний пост
ОбъявлениеРекомендации по использованию теха в нашем форуме15.04.2017 21:40
ОбъявлениеАспирантура в Clemson University (Computer Science, Mathematics)03.08.2015 22:20
ОбъявлениеВакансия: Разработчик WebCrawler и аналитик данных16.11.2015 10:19
23.12.2016 21:10
X ^ Y mod Z = R (Как найти Х?)
Дано:

$X^{273} mod 823746 = 463871$

Х - искомое целое число.
mod - деление по модулю (правильную запись операции не нашел)
Константы даны для примера и могут отличаться.

Есть ли возможность узнать Х, кроме как последовательный перебор?
Буду благодарен за любую помощь!
24.12.2016 04:46
Степенные сравнения
$823746=2\times3\times7\times11\times1783$
Решаем сравнения $x^{273} \equiv 463871 \pmod{p} $ по простым модулям p=2, 3, 7, 11, 1783 а затем применяем китайскую теорему об остатках.
Теорию можно посмотреть в Бухштабе.

_____________________________
Правила русского языка категорически против решения пределов, интегралов, рядов, матриц, определителей, функций, ...
..
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти