Теория чисел

[maxmatem]

Вот забыл про сравнения....
Решить сравнение
$2^{x}=287(mod 491) $
если известно,что 2 первообразный корень по модулю 491.(знак $=$ я обозначил как сравнения)

Вот что такое первообразный корень я помню, а как решать такие нет.
Может где посмотреть можно....

[ИСН]

Дискретное логарифмирование же.

[maxmatem]

там модуль большой поэтому в вручную непересчитать....а как быть ?

[maxmatem]

ну хорошо.
действую как в алгоритме.
1. $H=23$
2.$C=2^{23}(mod 491 )$
т.е $c=364$

а теперь надо составить таблицу состоящую из чисел вида $364^{i}(mod 491)$где $i$ от 1 до 23.
но как эти числа вычислять....замонаешься ведь....

[Misorra]

maxmatem
Maple?

[ИСН]

maxmatem в сообщении #581907 писал(а):

замонаешься ведь

Так в том-то всё и дело!

Цитата:

Эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны.

[Sonic86]

Если повезет, то $287$ может оказаться какой-нибудь степенью, $491-1=2\cdot 5\cdot 7^2$ - можно проверить (это довольно быстро), в этом случае достаточно было бы перебрать какие-то степени двойки, но все равно - против

ИСН в сообщении #581989 писал(а):

Эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны.

не попрешь...