Algoritmy Faugères F4 a F5 - Faugères F4 and F5 algorithms - Wikipedia

v počítačová algebra, Algoritmus Faugère F4tím, že Jean-Charles Faugère, počítá Gröbnerův základ z ideál vícerozměrného polynomiální kruh. Algoritmus používá stejné matematické principy jako Buchbergerův algoritmus, ale spočítá mnoho normálních forem najednou vytvořením obecně řídká matice a pomocí rychlé lineární algebry provádíme redukce paralelně.

The Algoritmus Faugère F5 nejprve vypočítá Gröbnerův základ dvojice generátorových polynomů ideálu. Poté používá tento základ ke zmenšení velikosti počátečních matic generátorů pro další větší základnu:

Li G_předchozí je již vypočítaný Gröbnerův základ (F₂, …, F_m) a chceme vypočítat Gröbnerův základ (F₁) + G_předchozí potom vytvoříme matice, jejichž řádky jsou m F₁ takhle m je monomiál, který není dělitelný úvodním členem prvku G_předchozí.

Tato strategie umožňuje algoritmu použít dvě nová kritéria na základě toho, co Faugère volá podpisy polynomů. Díky těmto kritériím může algoritmus vypočítat Gröbnerovy základy pro velkou třídu zajímavých polynomiálních systémů, tzv. pravidelné sekvence, aniž by došlo ke zjednodušení jediného polynomu na nulu - časově nejnáročnější operace v algoritmech, které počítají Gröbnerovy báze. Je také velmi efektivní pro velké množství nepravidelných sekvencí.

Implementace

Je implementován algoritmus Faugère F4

v FGb, Faugèreova vlastní implementace, která zahrnuje rozhraní pro jeho použití C / C ++ nebo Javor,
v Javorový počítačový algebraický systém, jako možnost metoda = fgb funkce Groebner [gbasis]
v Systém počítačové algebry Magma,
v SageMath počítačový algebraický systém,

Studijní verze algoritmu Faugère F5 jsou implementovány v^{[Citace je zapotřebí ]}

the JEDNOTNÉ ČÍSLO počítačový algebraický systém;^[1]
the SageMath počítačový algebraický systém.
v SymPy Krajta balík.^[2]

Aplikace

Dříve neřešitelný problém „cyklické 10“ byl vyřešen pomocí F5,^{[Citace je zapotřebí ]} stejně jako řada systémů souvisejících s kryptografií; například HFE a C.^*.^{[Citace je zapotřebí ]}

Reference

^ Eder, Christian (2008). „Kritéria algoritmu F5“. arXiv:0804.2033 [matematika AC ].
^ https://docs.sympy.org/latest/modules/polys/internals.html#groebner-basis-algorithms

Faugère, J.-C. (Červen 1999). "Nový efektivní algoritmus pro výpočet Gröbnerových bází (F₄)" (PDF). Journal of Pure and Applied Algebra. 139 (1): 61–88. doi:10.1016 / S0022-4049 (99) 00005-5. ISSN 0022-4049.
Faugère, J.-C. (Červenec 2002). Nový efektivní algoritmus pro výpočet Gröbnerových bází bez redukce na nulu (F₅) (PDF). Sborník příspěvků z Mezinárodního sympozia 2002 o symbolických a algebraických výpočtech (ISSAC). Stiskněte ACM. str. 75–83. CiteSeerX 10.1.1.188.651. doi:10.1145/780506.780516. ISBN 978-1-58113-484-1.
Dokud Stegers Faugèreův algoritmus F5 se vrátil (alternativní odkaz ). Diplom-Mathematiker Thesis, poradce Johannes Buchmann, Technische Universität Darmstadt, září 2005 (revidováno 27. dubna 2007). Mnoho odkazů, včetně odkazů na dostupné implementace.

externí odkazy

Faugèrova domovská stránka (zahrnuje dotisky dalších dokumentů ve formátu PDF)
Úvod do algoritmu F4.

[1] Eder, Christian (2008). „Kritéria algoritmu F5“. arXiv:0804.2033 [matematika AC ].

[2] ttps://docs.sympy.org/latest/modules/polys/internals.html#groebner-basis-algorithms

[1]

[2]