Временная сложность решения DLog, когда известны g и P

Это связано с распространенным заблуждением, особенно среди новичков в вычислительная сложность ; количество элементов или количество битов.

В вычислительной сложности вычислительная сложность обычно выражается как функция размера $n$ (в битах) входных данных, а сложность выражается как функция $n$.

Вы можете быть правы, учитывая, что алгоритмы сортировки используют количество элементов, однако контекст важен; число битов более естественно в криптографии, поскольку мы измеряем безопасность в битах.

Поэтому он экспоненциален по размеру ввода, когда ввод измеряется в битах.

Сказать, что это линейно, учитывая количество возможных значений, в криптографии вводит в заблуждение, поскольку в конечном итоге вы столкнетесь с трудностями в согласии с криптографами. Поэтому используйте число бит.