К проблеме дискретного логарифма

Пусть ${ \Bbb F}_{q}$ – конечное поле характеристики $p$, состоящее из $q =p^{ \nu}$ элементов, $g$ – примитивный элемент, $a \neq 0$ – произвольный элемент поля ${ \Bbb F}_{q}$ и $x= \log_{g} a$ – дискретный логарифм элемента $a$ по основанию $g$. В работе рассматривается проблема дискретного логарифма в поле ${ \Bbb F}_{q}$, $q \equiv 1 ( \bmod\,4)$, и указывается полиномиальный относительно $q$ детерминистический алгоритм вычисления первых $k \leq c \log n$ знаков $x_{0},x_{1}, \ldots,x_{k}$, $k < n$, бинарного представления $x=x_{0}+x_{1}2+x_{2}2^{2}+ \cdots + x_{n}2^{n}$ числа $x$.