Algorytmy F4 i F5 Faugère'a

W algebrze komputerowej algorytm Faugère F4 autorstwa Jean-Charlesa Faugère'a oblicza podstawę Gröbnera ideału wielowymiarowego pierścienia wielomianowego . Algorytm wykorzystuje te same zasady matematyczne, co algorytm Buchbergera , ale oblicza wiele postaci normalnych za jednym razem, tworząc ogólnie rzadką macierz i używając szybkiej algebry liniowej do wykonywania równoległych redukcji.

Algorytm Faugère F5 najpierw oblicza podstawę Gröbnera pary wielomianów generatora ideału. Następnie wykorzystuje tę podstawę do zmniejszenia rozmiaru początkowych macierzy generatorów dla następnej większej bazy:

Jeśli G _prev jest już obliczoną bazą Gröbnera ( f ₂ , …, f _m ) i chcemy obliczyć bazę Gröbnera ( f ₁ ) + G _prev , to skonstruujemy macierze, których wiersze są m f ₁ takie, że m jest a jednomian niepodzielny przez wyraz wiodący elementu G _prev .

Ta strategia pozwala algorytmowi zastosować dwa nowe kryteria oparte na tym, co Faugère nazywa sygnaturami wielomianów. Dzięki tym kryteriom algorytm może obliczyć bazy Gröbnera dla dużej klasy interesujących systemów wielomianowych, zwanych ciągami regularnymi , bez upraszczania pojedynczego wielomianu do zera - najbardziej czasochłonnej operacji w algorytmach obliczających bazy Gröbnera. Jest również bardzo skuteczny w przypadku dużej liczby nieregularnych sekwencji.

Implementacje

Zaimplementowano algorytm Faugère F4

w FGb , własna implementacja Faugère'a, która zawiera interfejsy do używania jej z C/C++ lub Maple ,
w systemie algebry komputerowej Maple jako opcja method=fgb funkcji Groebner[gbasis]
w systemie algebry komputerowej Magma ,
w systemie algebry komputerowej SageMath ,

Wersje studyjne algorytmu Faugère F5 są zaimplementowane w ^{[ potrzebne źródło ]}

system algebry komputerowej SINGULAR ;
system algebry komputerowej SageMath .
w pakiecie SymPy Pythona .

Aplikacje

Poprzednio trudny do rozwiązania problem „cyklicznej 10” został rozwiązany przez F5, ^{[ potrzebne źródło ]} , podobnie jak wiele systemów związanych z kryptografią; na przykład HFE i C ^* . ^{[ potrzebne źródło ]}

Faugère, J.-C. (czerwiec 1999). „Nowy wydajny algorytm obliczania baz Gröbnera (F ₄ )” (PDF) . Dziennik algebry czystej i stosowanej . 139 (1): 61–88. doi : 10.1016/S0022-4049(99)00005-5 . ISSN 0022-4049 .
Faugère, J.-C. (lipiec 2002). Nowy wydajny algorytm obliczania baz Gröbnera bez redukcji do zera (F ₅ ) (PDF) . Materiały z Międzynarodowego Sympozjum 2002 na temat obliczeń symbolicznych i algebraicznych (ISSAC) . ACM Press. s. 75–83. CiteSeerX 10.1.1.188.651 . doi : 10.1145/780506.780516 . ISBN 978-1-58113-484-1 . S2CID 15833106 .
Till Stegers Faugère's F5 Algorithm Revisited ( link alternatywny ). Diplom-Mathematiker Thesis, doradca Johannes Buchmann, Technische Universität Darmstadt, wrzesień 2005 (poprawiona 27 kwietnia 2007). Wiele referencji, w tym linki do dostępnych implementacji.

Linki zewnętrzne

Strona główna Faugère'a (zawiera przedruki pdf dodatkowych artykułów)
Wprowadzenie do algorytmu F4.