Как измерить сложность задачи дискретного логарифма?

Ответы на этот вопрос о Crypto Stack Exchange в основном говорят о том, что для измерения сложности проблемы логарифма мы должны принять во внимание длину числа, представляющего размер группы. Это кажется произвольным, почему мы не выбрали размер группы в качестве аргумента? Есть ли критерий, чтобы узнать, какой аргумент выбрать? На самом деле, я знаю, что упустил что-то важное, поскольку сложность сильно меняется, если мы делаем это в зависимости от размера группы.

Неважно, выбираете ли вы размер группы или размер целого числа, представляющего его n в качестве параметра, поскольку n ≈ log | G | , Есть две причины, по которым сложность обычно описывается в терминах n, а не | G | :$|G|$$n$$n \approx \log |G|$$n$$|G|$

1. - длина входа (точнее, длина ввода равна Θ ( n ) ), и мы обычно измеряем сложность алгоритмов как функцию длины ввода.$n$$\Theta(n)$

2. Обычно - это небольшое число, например 1024 , тогда как | G | это огромное число, такое как (примерно) 2 1024 .$n$$1024$$|G|$$2^{1024}$