Аннотация:Множество элементов $B_G = \{ g_1, \ldots , g_q \}$ конечной абелевой (по умножению) группы $G$
называется базисом, если группа $G$ представляется в виде прямого ппоизведения циклических групп, порожденных элементами $g_1, \ldots , g_q$:
$G = \langle g_1\rangle \times \ldots \times \langle g_q\rangle$. Изучается вычисление элементов группы $G$ схемами из функциональных элементов умножения, в которых каждый функциональный элемент вычисляет
произведение подаваемой на его входы пары элементов группы $G$.
Под сложностью $L(S)$ схемы $S$ понимается общее число функциональных элементов
в схеме $S$. Сложность конечной абелевой группы $G$ над базисом $B_G$ определяется
равенством $L(G,B_G) = \max_{g \in G} \min_S L(S)$, где минимум берется по всем схемам $S$, вычисляющим элемент $g$ над базисом $B_G$. В работе доказано, что при $|G| \to \infty$ справедливо равенство
$$
L(G,B_G)= \frac{\log_2 |G|}{\log_2 \log_2 |G|}
\left(1+ O \left( \sqrt{ \frac{\log_2 \log_2 \log_2 |G|}{\log_2 \log_2 |G|} } \right) \right)
+ O(p + |B_G|),
$$
где $p$~--- наибольший порядок у элементов из множества $B_G$.
Для функции Шеннона, определяемой равенством
$L(n) = \max_{G: |G|=n} \min_{B_G} L(G, B_G)$, при $n \to \infty$
установлена асимптотическая формула
$$
L(n)= \log_2 n + (1+o(1))\frac{\log_n}{\log_2 \log_2 n} .
$$
Эти результаты основаны на использовании описанного в работе асимптотически оптимального метода
реализации двоичных матриц ступенчатого вида вентильными схемами.
