Сравнение сложности вычисления одночленов и элементов конечных абелевых групп

В работе сравниваются значения сложности вычисления элемента $a_1^{k_1} a_2^{k_2} \ldots a_q^{k_q}$ абелевой группы $\langle a_1 \rangle_{u_1} \times \langle a_2 \rangle_{u_2} \times \ldots \times \langle a_q \rangle_{u_q}$ (предполагается, что $k_i < u_i $ для всех $i$) и сложности вычисления одночлена $x_1^{k_1} x_2^{k_2} \ldots x_q^{k_q}$. Под сложностью вычисления понимается минимально возможное число операций умножения, при этом результаты промежуточных вычислений могут использоваться многократно. Установлено, что при выполнении условия $u_1 u_2 \ldots u_q \le n$ максимально возможные разность и отношение второй и первой величин асимптотически растут при $n \to \infty$ как $ \log_2 / (\log_2 \log_2 n)$ и $\sqrt{\log_2} / (2 \log_2 \log_2 n)$ соответственно.