Базисы Гребнера (алгоритм Бухбергера)

[Сергей Михайлов]

Интересует следующее. Есть ли какие-нибудь оптимизации алгоритма (полезные для реализации) для конечного поля GF(2)?
Некоторые предложения по оптимизации я нашел в книжке "Идеалы многообразия и алгоритмы" (авторы Кокс Д. Литтл Д. О`Ши Д.), но это касается оптимизации для произвольного поля. Может кто-нибудь посоветует какие-нибудь новые публикации по теме?

[maxal]

А зачем оптимизировать алгоритм Бухбергера, если есть более быстрые алгоритмы $F_4$ и $F_5$ ?

Реализация для Maple есть на сайте автора: http://fgbrs.lip6.fr/jcf/Software/

[Сергей Михайлов]

Ссылка не открывается.

На вопрос отвечу. Нужно реализовать алгорит Бухбергера для специфического железа. И реализовать алгорит Фужера. И посмотреть, что быстрее, и затем пользоваться.

[maxal]

Сергей Михайлов писал(а):

Ссылка не открывается.

Видимо, у них какой-то сбой. Попробуйте через денек-два.

Сергей Михайлов писал(а):

На вопрос отвечу. Нужно реализовать алгорит Бухбергера для специфического железа. И реализовать алгорит Фужера. И посмотреть, что быстрее, и затем пользоваться.

Могу сразу сказать, что быстрее будет второе (если имеется в виду его алгоритм $F_4$), и никакое железо не сможет исправить эту ситуацию.

[Сергей Михайлов]

maxal писал(а):

Могу сразу сказать, что быстрее будет второе (если имеется в виду его алгоритм $F_4$), и никакое железо не сможет исправить эту ситуацию.

Если так, это хорошо. Но хотелось бы знать, чем вы руководствуетесть? По той ссылке есть сравнение этих алгоритмов? Может где-то есть чисто математическое сравнение этих алгоритмов? Насколько я себе преставляю, любой алгоритм построения базиса Гребнера может работать долго, и это связано с тем, что, при n начальных многочленах может получиться порядка 2^{2^n} многочленов в базисе. Поэтому мне нужно понять, в каком именно смысле алгоритм $F_4$ быстрее, чем Бухбергер. Нужели всегда?

[maxal]

Алгоритм $F_4$ можно рассматривать как оптимизированную ("распараллеленную") версию алгоритма Бухбергера. Возможно, есть экзотические примеры, когда такая оптимизация будет вызывать замедление, но в целом она работает быстрее.

Чисто с практической стороны, с изобретением алгоритмов $F_4$ и $F_5$ смогли построить базисы Грёбнера для задач, считавшихся практически недостижимыми для алгоритма Бухбергера. Например, т.н. HFE Challenge 1 (подробности).
В этом смысле сравнивать $F_4$ и $F_5$ (а можно еще и $FGLM$ до кучи) между собой куда интереснее чем их же с алгоритмом Бухбергера.

Вот очень неплохой обзор теории базисов Гребнера и алгоритмов Бухбергера, $F_4$ и $F_5$ (с упором на применение к задачам криптографии).

Эмпирическое сравнение $F_4$ с другими алгоритмами есть также в исходной статье Фужера об этом алгоритме:
A new efficient algorithm for computing Gröbner bases ($F_4$)

[Сергей Михайлов]

Большое спасибо за ссылки. Они дали мне много пищи для размышлений

[maxal]

До кучи неплохой обзор алгоритма $F_5$: http://eprint.iacr.org/2006/404