Алгоритмы Faugères F4 и F5 - Faugères F4 and F5 algorithms

В компьютерная алгебра, то Алгоритм Фогера F4, к Жан-Шарль Фогер, вычисляет Основа Грёбнера из идеальный многомерного кольцо многочленов. В алгоритме используются те же математические принципы, что и в алгоритме. Алгоритм Бухбергера, но вычисляет множество нормальных форм за один раз, формируя общий разреженная матрица и используя быструю линейную алгебру для параллельного выполнения редукций.

В Алгоритм Faugère F5 сначала вычисляет базис Грёбнера пары порождающих полиномов идеала. Затем он использует этот базис для уменьшения размера исходных матриц генераторов для следующего большего базиса:

Если грамм_{предыдущий} - уже вычисленный базис Грёбнера (ж₂, …, ж_м) и мы хотим вычислить базис Грёбнера в (ж₁) + грамм_{предыдущий} затем построим матрицы, строки которых м ж₁ такой, что м моном, не делящийся на главный член элемента из грамм_{предыдущий}.

Эта стратегия позволяет алгоритму применять два новых критерия, основанных на том, что Фожер называет подписи многочленов. Благодаря этим критериям алгоритм может вычислять базисы Грёбнера для большого класса интересных полиномиальных систем, называемых регулярные последовательности, без упрощения одного полинома до нуля - наиболее трудоемкая операция в алгоритмах вычисления базисов Грёбнера. Это также очень эффективно для большого количества нерегулярных последовательностей.

Реализации

Реализован алгоритм Faugère F4.

• в FGb, Собственная реализация Фогера, которая включает интерфейсы для ее использования из C / C ++ или же Клен,
• в Система компьютерной алгебры Maple, как вариант метод = fgb функции Грёбнер [gbasis]
• в Система компьютерной алгебры Magma,
• в SageMath система компьютерной алгебры,

Учебные версии алгоритма Faugère F5 реализованы в^{[нужна цитата ]}

• то ЕДИНСТВЕННОЕ ЧИСЛО система компьютерной алгебры;^[1]
• то SageMath система компьютерной алгебры.
• в SymPy Python упаковка.^[2]

Приложения

Ранее неразрешимая проблема "циклической 10" была решена с помощью F5,^{[нужна цитата ]} как и ряд систем, связанных с криптографией; Например HFE и C^*.^{[нужна цитата ]}

Рекомендации

1. Эдер, Кристиан (2008). «О критериях алгоритма F5». arXiv:0804.2033 [math.AC ].
2. https://docs.sympy.org/latest/modules/polys/internals.html#groebner-basis-algorithms

• Фогер, Ж.-К. (Июнь 1999 г.). "Новый эффективный алгоритм для вычисления базисов Гребнера (F₄)" (PDF). Журнал чистой и прикладной алгебры. 139 (1): 61–88. Дои:10.1016 / S0022-4049 (99) 00005-5. ISSN  0022-4049.
• Фогер, Ж.-К. (Июль 2002 г.). Новый эффективный алгоритм вычисления базисов Грёбнера без приведения к нулю (F₅) (PDF). Материалы Международного симпозиума по символьным и алгебраическим вычислениям (ISSAC) 2002 г.. ACM Press. С. 75–83. CiteSeerX  10.1.1.188.651. Дои:10.1145/780506.780516. ISBN  978-1-58113-484-1.
• Тилл Стегерс Возвращение к алгоритму F5 Фогера (альтернативная ссылка ). Diplom-Mathematiker Thesis, научный руководитель Йоханнес Бухманн, Технический университет Дармштадта, сентябрь 2005 г. (отредактировано 27 апреля 2007 г.). Множество ссылок, включая ссылки на доступные реализации.

внешняя ссылка

• Домашняя страница Фогера (включая оттиски дополнительных статей в формате pdf)
• Введение в алгоритм F4.