Товарищи, здравствуйте. Есть вопрос из области криптографии/математики по вычислению сложности алгоритмов.
Вопрос по асимптотике задачи дискретного логарифмирования в мультипликативной группе кольца вычетов по модулю m. Условно, известны g и a = g^x, найти x.
В самом тупом варианте решения - при переборе - мы возводим g в степени 2, 3, 4 ... x, соответственно, у нас идёт x операций умножения. Операция умножения в худшем случае выполняется за O(n^2), где n - это количество знаков в числе. Оно у нас ограничено модулем m, то есть выполняется за полиномиальное время.
Алгоритмов для решения задачи дискретного логарифмирования за полиномиальное время, как я понимаю, не существует. В лучшем случае есть субэкспоненциальные алгоритмы. И вот вопрос: как из выполнения полиномиальной операции (умножение) линейное количество раз (искомая степень) получается экспоненциальная (или хуже) асимптотика?
В гугле искал, не помогает.