Faugères F4 och F5 algoritmer
I datoralgebra beräknar Faugère F4-algoritmen , av Jean-Charles Faugère , Gröbnerbasen för ett ideal för en multivariat polynomring . Algoritmen använder samma matematiska principer som Buchberger-algoritmen , men beräknar många normala former på en gång genom att bilda en generellt gles matris och använda snabb linjär algebra för att göra reduktionerna parallellt.
Faugère F5-algoritmen beräknar först Gröbner-basen för ett par generatorpolynom av idealet. Sedan använder den denna bas för att minska storleken på de initiala matriserna för generatorer för nästa större bas:
Om G prev är en redan beräknad Gröbnerbas ( f 2 , …, f m ) och vi vill beräkna en Gröbnerbas av ( f 1 ) + G prev så kommer vi att konstruera matriser vars rader är m f 1 så att m är en monomial inte delbart med den inledande termen för ett element av G föregående .
Denna strategi tillåter algoritmen att tillämpa två nya kriterier baserat på vad Faugère kallar signaturer av polynom. Tack vare dessa kriterier kan algoritmen beräkna Gröbnerbaser för en stor klass av intressanta polynomsystem, kallade reguljära sekvenser , utan att någonsin förenkla ett enda polynom till noll – den mest tidskrävande operationen i algoritmer som beräknar Gröbnerbaser. Det är också mycket effektivt för ett stort antal icke-regelbundna sekvenser.
Genomföranden
Faugère F4-algoritmen är implementerad
- i FGb , Faugères egen implementering, som inkluderar gränssnitt för att använda den från C/C++ eller Maple ,
- i Maple datoralgebrasystem , som alternativet method=fgb för funktion Groebner[gbasis]
- i Magma datoralgebrasystem ,
- i SageMath- datoralgebrasystemet,
Studieversioner av Faugère F5-algoritmen implementeras i [ citat behövs ]
Ansökningar
Det tidigare svårlösta "cykliska 10"-problemet löstes av F5, [ citat behövs ] liksom ett antal system relaterade till kryptografi; till exempel HFE och C * . [ citat behövs ]
- Faugère, J.-C. (juni 1999). "En ny effektiv algoritm för att beräkna Gröbner-baser (F 4 )" (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. (juli 2002). En ny effektiv algoritm för att beräkna Gröbner-baser utan reduktion till noll (F 5 ) (PDF) . Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation (ISSAC) . ACM Tryck. 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ères F5 Algorithm Revisited ( alternativ länk ). Diplom-Mathematiker Thesis, rådgivare Johannes Buchmann, Technische Universität Darmstadt, september 2005 (reviderad 27 april 2007). Många referenser, inklusive länkar till tillgängliga implementeringar.
externa länkar
- Faugères hemsida (inkluderar pdf-uttryck av ytterligare papper)
- En introduktion till F4-algoritmen.