Дискретный логарифм за полиномиальное время

[Sinay]

Здравствуйте!

Я, как мне кажется, нашел способ нахождения дискретного логарифма в полях Галуа за полиномиальное время. Я приложу ссылки на файлообменники, где будет находится препринт моего метода. Я допускаю возможность, что где-то мог ошибиться, поэтому пишу на этот форум и буду рад замечаниям, предложениям и всему прочему. Я также отправил статью в редакцию журнала "Проблем передачи информации", но хочу получить ответ прав ли я быстрее. Думал, опубликовать препринт на сайтах вроде http://arxiv.org/, но решил, что это тоже будет дольше.

Спасибо!


http://ifolder.ru/27028712
http://www.getzilla.net/files/2242664/dl.pdf.html
http://www.sharemania.ru/0108771

[Sonic86]

Здравствуйте!

У Вас в главе "Вычислительная сложность алгоритма" число всех операций линейно зависит от $p$, то есть экспоненциально зависит от $\ln p$, а надо, чтобы оно от $\ln p$ зависело полиномиально. Правильно? Или я чего-то не понимаю?

(ссылка на задачу в Вики)

Про дискретное логарифмирование кратко можно почитать в Вики:
http://ru.wikipedia.org/wiki/%D0%94%D0% ... 0%B8%D0%B5
Я вот тут вижу самый простой алгоритм со сложностью $O(\sqrt{p} \ln p) = o(p)$.

[Sinay]

Нет, смотрите: поле у нас $F_{p^{m}}$ и экспоненциальная сложность это величина порядка $p^{m}$, то есть входное n это размерность поля, а у меня логарифм соответственно.

В ссылке Вы указываете сложность для простых полей, я же рассматриваю поля Галуа. Если Вы посмотрите ниже на статью в вике, то увидите, что алгоритмы имеют экспоненциальную и субэкспоненциальную сложность.

Я в своей статье, наверное, несовсем точно выражаюсь, когда говорю, что первый полиномиальный. Алгоритм Сильвера–Полига–Хеллмана тоже может иметь полиномиальную, когда $p^{m}-1$ факторизуется на маленькие сомножители.

[Kallikanzarid]

Лучше все же на архив.

[Sinay]

Я столкнулся там с проблемой:
You are not endorsed for this archive.
Нужен человек, который мог бы за меня поручиться. Но высылать каждому из них свою работу и просить, чтобы подтвердили --- помоему неправильно.

[Руст]

Вчера встречался с академиком криптографии Нечаевым. Эта задача нерешенная. Пока существует полиномиальный алгоритм только для квантового компьютера. В том виде вряд ли кто-то будет читать. Перепишите на математическом языке. Возведение в степень р называется автоморфизмом Фробениуса. Группа Галуа циклическая и порождается этим автоморфизмом. Ваш циклотоматический класс называется множеством сопряженных элементов. Только он у вас упорядочен по степеням образующего $\alpha$. Я не представляю как можно упорядочить их для элемента $b$ не решив задачу $b=\alpha^y$. Напишите на нормальном математическом языке и если не будет ошибок помогу с публикацией.

[AV_77]

Алгоритм нахождения ведущего элемента работать не будет, точнее если $\alpha^s$ - ведущий элемент циклотомического класса, содержащего $b$, то не всегда $\frac{b^{p^j}}{\alpha^s} \in A_1$.
Например, рассмотрим поле $\mathbb{F}_8$, порожденное корнем многочлена $x^3 + x + 1 \in \mathbb{F}_2[x]$. Пусть $\alpha$ - порождающий. Степени $\alpha$ имеют вид:
$\alpha$
$\alpha^2$
$\alpha^3 = \alpha + 1$
$\alpha^4 = \alpha^2 + \alpha$
$\alpha^5 = \alpha^2 + \alpha + 1$
$\alpha^6 = \alpha^2 + 1$
При этом $A_1 = \{ \alpha,\ \alpha^2,\ \alpha^2 + \alpha \}$.
Пусть $b = \alpha + 1$ (он как раз и является ведущим элементом). Тогда $\Omega = \{ \alpha + 1,\ \alpha^2 + 1,\ \alpha^2 + \alpha + 1 \}$.
Выполняя алгоритм нахождения ведущего элемента получим
$\frac{\alpha + 1}{\alpha^2 + \alpha + 1} = \alpha^2 + \alpha + 1 \notin A_1,$
$\frac{\alpha^2 + 1}{\alpha + 1} = \alpha + 1 \notin A_1,$
$\frac{\alpha^2 + \alpha + 1}{\alpha^2 + 1} = \alpha^2 + 1 \notin A_1.$