Простой вопрос по алгебре

Angela

Есть ли какой-то известный разумный способ вычисления суммы элементов поля в терминах степеней примитивного элемента. Если кто знает, буду благодарен за ответ. Ниже идет более конкретная формулировка вопроса.
[math]Дано число $q=p^n$. Пусть $\alpha$ --- образующий элемент мультипликативной группы поля $\mathbb{F}_q$ (то есть его примитивный элемент над $\mathbb{F}_p$). Можно ли как-то в общем виде вычислить $\log_\alpha(\alpha^i+\alpha^j)$, где $i,j\in\{0,\ldots,q-2\}$?[/math]

Angela

up!

incwizitor

Попробовал решить в лоб, но не получилось пока. Вот набросок:
Пусть [math]$$\alpha$$[/math] - образующий элемент циклической мультипликативной группы поля.
Задача равносильно тому, чтобы найти [math]$$x_k=log_\alpha(\alpha^k + 1 k\in [0, q-2]$$[/math]
Сразу получаем такой факт:
[math]$$x_0=log_\alpha(2)$$[/math]
Далее попробуем составить рекуррентное соотношение для [math]$$x_k$$[/math]:
[math]$$\alpha^{x_{k+1}} = \alpha^{x_k} \alpha + 1 - \alpha = \alpha^{x_k+1} + \alpha^z=\alpha^z(\alpha^{x_k+1-z} + 1)=\alpha^{z+x_{x_k+1-z \mod (q-1)}}$$[/math]
[math]$$z=log_{\alpha}(1-\alpha)$$[/math]
не знаю что с ним делать, но оно есть ;
Еще кое что можно получить:
[math]$$\alpha^{x_k}=\alpha^k + \alpha^{q-1} = \alpha^k(\alpha^{q-1-k} + 1)=\alpha^{k + x_{q-1-k}}$$[/math]
Следовательно, [math]$$x_k\equiv k+x_{q-1-k} \mod (q-1)$$[/math]
Еще свойство: все [math]$$x_k$$[/math] попарно различны и для некоторого k ответа нет, ибо может быть выполнено равенство [math]$$\alpha^{k_0}+1 = 0$$[/math].
Больше ничего не придумалось ;(

vsjshnikova

Если меня не глючит, эта задача полиномиально эквивалентна нахождению дискретного логарифма: Если мы запишем элемент поля в виде [math]$b = \sum\limits_{i=0}^n a_i \alpha^i = \sum\limits_{i=0}^n \sum\limits_{j=0}^{\log q} a_{ij}2^j\alpha^i$[/math](во втором равенстве раскладываем $a_i$ в двоичной системе то мы можем найти [math]$\log b$[/math] с помощью не более [math]$n \cdot2\log q \leq 2\log |F|$[/math] операций перехода [math]$\alpha^s+\alpha^r\mapsto \alpha^k$[/math]. Т.е. если мы умеем делать это быстро, мы сможем быстро находить дискретные логарифмы, а это сомнительно.

incwizitor

умеем делать это быстро
не очень ясно, что значит "разумно" =) ведь может существовать красивое с точки зрения математики решение, но трудно вычислимое :grin:
ТС, уточните, что вы под "разумностью" понимаете?:)

Angela

Пока нужно получить разумное хоть в каком-то смысле решение. Не обязательно быстро вычислимое. В идеале, конечно, хочется получить максимально прозрачное математическое выражение (комбинаторное или аналитическое) для логарифма через p, q, i и j, даже если оно будет трудно вычислимо.

incwizitor

Следовательно, [math]$$x_k\equiv k+x_{q-1-k} \mod (q-1)$$[/math]
Что-то у меня проблемы здесь возникают при [math]$$k=\frac{q-1}{2}, \frac{q}{2}, \frac{q-2}{2}$$[/math] (разные четности q рассматриваем). Либо при этих значениях [math]$$x_k$$[/math] не определен, либо где-то я накосячил в формуле :(
Оставить комментарий
Имя или ник:
Комментарий: