Дискретный логарифм. Нужна помощь по теории.

[Denmarino111]

Здравствуйте, делаю сейчас работу на тему: Дискретное логарифмирование в криптографии.(в кольце вычетов по модулю простого числа). И столкнулся с таким вопросом. Как можно проверить существует ли дискретный логарифм? Просто мне нужно написать программу, и будет как-то не круто, если он будет считать пол дня, а потом напишет, что его не существует. И если кто-то знаком с этой темой, скажите пожалуйста, какой алгоритм работает быстрее всего. (и с большими числами тоже)
Вроде бы если основание является первообразным корнем по модулю, то диск. логарифм существует. Но по-моему это не 100% точно, ибо я пробовал перебором проверять и у меня вышло не всё правильно.

[bot]

Denmarino111 в сообщении #701880 писал(а):

Вроде бы если основание является первообразным корнем по модулю, то диск. логарифм существует.

Не вроде бы, а точно так. По модулю простого первообразный корень существует, иначе говоря мультипликативная группа по этому модулю циклична. Находить образующий можно методом научного тыка: начинаем пытать начиная с двойки. Для небольших простых первообразные корни есть в таблицах, приложенных к любому задачнику по ТЧ.

[Someone]

Первообразные корни по модулю простого $p$ можно находить так: берём целое $a$, удовлетворяющее условию $1<a<p-1$, и для каждого простого делителя $d$ числа $p-1$ вычисляем $a^{\frac{p-1}d}\pmod{p}$. Если все эти степени $\neq 1$, то $a$ - первообразный корень.
Нужно уметь разлагать на множители число $p-1$ (Wolfram Mathematica легко справляется с пятидесятизначными числами) и вычислять степень с большим показателем (есть очень быстрые алгоритмы).

[Denmarino111]

Ну ведь дискретный логарифм может существовать и основание не обязательно должно быть первообазным корнем по модулю.
Например:
12^x=119( mod 251)

Просто мне по курсовой нужно сделать программу. И обязательно сделать функцию проверки входных данных.

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

Denmarino111 в сообщении #702302 писал(а):

12^x=119( mod 251)

Denmarino111, наберите формулу $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.