{"entities":{"Q607065":{"pageid":608841,"ns":120,"title":"Item:Q607065","lastrevid":63127392,"modified":"2026-04-11T10:46:30Z","type":"item","id":"Q607065","labels":{"en":{"language":"en","value":"F5C: A variant of Faug\u00e8re's F5 algorithm with reduced Gr\u00f6bner bases"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5817632"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$6800B955-0245-4ED2-B99B-CAEFDF1C4D52","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0c6709d1f7560aff04b1e80afed1b4ee92122f35","datavalue":{"value":{"text":"F5C: A variant of Faug\u00e8re's F5 algorithm with reduced Gr\u00f6bner bases","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q607065$D01CD88D-7E28-4D1B-B07F-3C4F600ADA85","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d95d70db894b858b19a697e20dca975d2acdb70a","datavalue":{"value":"1227.13018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q607065$18A35D4A-F9D9-4791-BA02-C904A149F4D0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e2531ac654b96934296b90a1c02d978bac511847","datavalue":{"value":{"entity-type":"item","numeric-id":607064,"id":"Q607064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$A25FA532-9315-487C-8F67-E3F1722C8099","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a9fbaa56e9ce073a4821e17410c169b1159c6ec8","datavalue":{"value":{"entity-type":"item","numeric-id":512376,"id":"Q512376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$50BC293E-FB05-4586-B86E-A35FD74AD552","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$80F4CA11-3CA9-4672-BF2B-6B739658BEF2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b1a8b0b4410e75478f392738ec80b73d0645c344","datavalue":{"value":{"time":"+2010-11-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q607065$49A76F90-A3CF-4517-8201-8284CF99FE43","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"992d2b2242618a622a80ecc8c662d557d0c008f8","datavalue":{"value":"https://arxiv.org/abs/0906.2967","type":"string"},"datatype":"url"},"type":"statement","id":"Q607065$779F6038-2B93-4865-B9A6-281E52FCFE81","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8e50a83e68110a86e20cc3f2d567c2fd396cd754","datavalue":{"value":"One of the best algorithm computing Gr\u00f6bner bases is Faug\u00e8re's F5 algorithm. This algorithm is incremental, i.e. to compute the Gr\u00f6bner basis of the ideal generated by the list of polynomials \\(F=(F_1,\\dots,F_m)\\) it computes the Gr\u00f6bner bases of the ideals \\(\\langle F_m\\rangle\\), \\(\\langle F_{m-1},F_m\\rangle\\),\\dots, \\(\\langle F_2,\\dots,F_m\\rangle\\).  \\textit{J.-C. Faug\u00e8re} [ISSAC 2002. Proceedings of the 2002 international symposium on symbolic and algebraic computation, Lille, France, July 07--10, 2002. New York, NY: ACM Press. 75--83 (2002; Zbl 1072.68664)] proposed to add to each polynomial \\(p\\) an information, called ``signature'', about how \\(p\\) is computed from \\(F\\) and then exploit these informations hereinafter. This strategy turns out to be very efficient, but a analysis of the execution of the algorithm led to think that it could be further improved, because in general F5 reduces also many redundant polynomials useless for the final Gr\u00f6bner basis.  In this paper, the authors present a new strategy, mainly based on the construction of a reduced Gr\u00f6bner basis instead of a generic one, as for F5. \\textit{T. Stegers} [Faug\u00e8re's F5 Algorithm Revisited (Thesis, Technische Universit\u00e4t Darmstadt, Germany) (2006)] proved that the generic Gr\u00f6bner basis can not be simply replaced by the reduced basis because such a variant of F5 would be incorrect. The authors consider again reduced bases even ensuring the correctness of the algorithm by updating at each incremental step the signatures, so that this variant returns a reduced Gr\u00f6bner basis and moreover during the computation it uses only the signatures of the polynomials in such a basis. The computational experiments show that the modified algorithm is a faster and requires less reductions than F5.","type":"string"},"datatype":"string"},"type":"statement","id":"Q607065$C0CCBFF7-D05B-47AA-8CE7-0CD9B58DBEEA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"46839b777f337535372d0a005512686d6191c29b","datavalue":{"value":{"entity-type":"item","numeric-id":311783,"id":"Q311783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$7F859FC6-288A-400E-8CA7-DF53F8143D6D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"173b0c3afec7c4f9f987722665cc7bdb6b8f5813","datavalue":{"value":"13P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q607065$FDC80974-1F4A-444A-8DEE-5E3D20BCD172","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f7f43158b42f0a7240ceb9aa177f89dce451dc7","datavalue":{"value":"13-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q607065$541971F9-26CC-4513-A978-F80D52D601AB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"898b78254e9a54db799c7f1becd12587f3ccca1e","datavalue":{"value":"5817632","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q607065$AB350417-88B9-4D8E-A55B-BB8D3A6746B1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be3fd4353ea84060667427d62c7bee4ac590185a","datavalue":{"value":"Faug\u00e8re","type":"string"},"datatype":"string"},"type":"statement","id":"Q607065$28C0380A-E363-4CB6-8F6B-B910F6A5E0E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"436357586c6f8f5bbd441af7d4cd797dd0ef2116","datavalue":{"value":"F5 algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q607065$3D7D6425-9FA7-4AC1-BCC5-692236E3D922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c4298192177634a067f10700948262e6596bf09","datavalue":{"value":"reduced Gr\u00f6bner basis","type":"string"},"datatype":"string"},"type":"statement","id":"Q607065$8A41F8F8-602C-4181-AB8F-EB3293B1B4E8","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"ef03848f41f59da431665c121436ac0a6bc94ac2","datavalue":{"value":{"entity-type":"item","numeric-id":13610,"id":"Q13610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$9BB59D91-B5CC-4B94-8A29-821B7877B2E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"8e3b850e2d06ba453bf5be8d0a388537ed706b70","datavalue":{"value":{"entity-type":"item","numeric-id":25149,"id":"Q25149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$16D75CC0-0C14-44A4-BBD8-8326EE40D7C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"31a461888bfe9315ad7d7f5e0da5f5d5d2bfb22e","datavalue":{"value":{"entity-type":"item","numeric-id":13048,"id":"Q13048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$79B50934-A328-40E4-BB76-FF568A07E0AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"62306d7c2342b11e3aca05e63d0f86e0f78995d7","datavalue":{"value":{"entity-type":"item","numeric-id":46744,"id":"Q46744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$A59E57EF-BC46-4D7F-912E-5E4B14419432","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"2b5c9b35d8e9d156fad0e174bf1ededba57ccca7","datavalue":{"value":{"entity-type":"item","numeric-id":13572,"id":"Q13572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$49BDAB7D-8EBC-4229-B64F-1BB434FBAD2A","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$7BEE94AF-3109-41BF-8F5F-402C426CF4E7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6de5e357112d9c1cdaa270cae7249194750d641d","datavalue":{"value":"W1993995116","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q607065$B8178C93-DA79-41DF-B482-00B00042B8D9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1eb52b96c4c974f9d9523f367ef64dded6d05761","datavalue":{"value":{"entity-type":"item","numeric-id":4693774,"id":"Q4693774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$F4803285-0C52-4E06-A845-1AA7D9072603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d0d60285ae04471993c98b6fd4f9789d850bb6c","datavalue":{"value":{"entity-type":"item","numeric-id":2902935,"id":"Q2902935"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$454DEF0D-A397-49E5-83A5-8DC52AE3F1FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"477fad7e9eb44ad8a11dffc84ce40c6dfab6c50e","datavalue":{"value":{"entity-type":"item","numeric-id":1295781,"id":"Q1295781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$9A6E8A86-8261-4337-A972-E60CEDF2C178","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43a68a509eadf6111b0e06ec4b721711237d6038","datavalue":{"value":{"entity-type":"item","numeric-id":4660688,"id":"Q4660688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$0A98D079-5E90-4968-A55D-279862508409","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbae617fb6e166742561c17d105ae1ea0ce6a7f9","datavalue":{"value":{"entity-type":"item","numeric-id":1121950,"id":"Q1121950"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$4290FFCD-0F79-40A3-9058-B1294FD7BC40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3040b285a507cb4716dfd187c5350872fcac2998","datavalue":{"value":{"entity-type":"item","numeric-id":5176452,"id":"Q5176452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$06CF7670-C6ED-46C3-A638-338FAEEF12D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b39e4578c7484bdb81de3234837b3ae698fb5a09","datavalue":{"value":{"entity-type":"item","numeric-id":3325833,"id":"Q3325833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$D299F5A6-EFF4-4168-A160-A39CF84A9FE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6bbb008a97901b6864246c34dae06398b9e67d5","datavalue":{"value":{"entity-type":"item","numeric-id":4234258,"id":"Q4234258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$FBE77040-E870-48A8-8B86-856FE83A913A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a9fa8227fbf1eb5097c67ab8c391efa427a4a2f","datavalue":{"value":{"entity-type":"item","numeric-id":4674258,"id":"Q4674258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$04DF0598-8355-4D69-B9EE-2330D3CD0A04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c60deea7785192df8a7cf25a408140a2f317a6c","datavalue":{"value":{"entity-type":"item","numeric-id":4953977,"id":"Q4953977"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q607065$E6699956-347E-4FA7-9DDE-F420F1F6D168","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c5a9d6b4bd3544a19d9f1977a54f2cf4bf3cb5ab","datavalue":{"value":"10.1016/J.JSC.2010.06.019","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q607065$34E03002-B8E0-49E6-BA7D-BE37F4658138","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6375c7a18ae15738c07e235cc1b64d1ce484d1b","datavalue":{"value":{"entity-type":"item","numeric-id":2343240,"id":"Q2343240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"108c1308042a7b6ee4c624ab9a2cc90d0867645b","datavalue":{"value":{"amount":"+0.88913774","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q607065$91999700-2F2D-4862-AC0B-F6B99B19D29E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d575bdb1ac5ef6de3e889b2ea0a48edc09cde3e","datavalue":{"value":{"entity-type":"item","numeric-id":1956953,"id":"Q1956953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71b97a534b85161d51668e09a18f05787148ba85","datavalue":{"value":{"amount":"+0.88828516","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q607065$473336AD-4AE9-4468-ABE6-99E6BB5A6FCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28c9e508febd4706f29ab62826e86aa790cf76b5","datavalue":{"value":{"entity-type":"item","numeric-id":4660688,"id":"Q4660688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef26ec04f92be503bf035e9753300f04d7205930","datavalue":{"value":{"amount":"+0.88656145","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q607065$F03A2320-8673-42C0-9886-722136673E6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9c7c0faa2ec0a1e4ab107e048d4e2d9bf4cf420","datavalue":{"value":{"entity-type":"item","numeric-id":2437322,"id":"Q2437322"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a610f8f2f3792f1c647ac33e22b6bb0f6e5d623","datavalue":{"value":{"amount":"+0.8558725","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q607065$BDDA0B3D-B1E0-4572-ADED-491246D7AA8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2bb86fa0d07ac9ffed84db21505f8c3243cc6357","datavalue":{"value":{"entity-type":"item","numeric-id":301017,"id":"Q301017"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"102a6ca02c4e87d7079b731e4af5b287ca85ed7e","datavalue":{"value":{"amount":"+0.8393376","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q607065$FF4BD595-5B48-472D-971C-9109EA7A7750","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4661fc469da39e5e2c215df3a9f5a80b9e13fc46","datavalue":{"value":{"entity-type":"item","numeric-id":650306,"id":"Q650306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"013679cbe45246a18785a7b4f446127351e6113b","datavalue":{"value":{"amount":"+0.8378841","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q607065$5A9C283F-DDDB-4A7B-9C89-D878A15C283E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"071c5cf121840f55697a3532afffdb076d6be121","datavalue":{"value":{"entity-type":"item","numeric-id":2430791,"id":"Q2430791"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b14e5dfdf8e829d5535acfad26883ab8817e6c4f","datavalue":{"value":{"amount":"+0.8314969","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q607065$1EF2F385-9CFA-4BA0-8B24-17B1B876AFFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c59074c86a7a2defb95c9758ccc08267930818c1","datavalue":{"value":{"entity-type":"item","numeric-id":6081937,"id":"Q6081937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6a0d279b406a2cec2a7734ef1cbff64d95818ac","datavalue":{"value":{"amount":"+0.8250748","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q607065$EEBD26BC-387C-4779-9402-5A5EE6478AE4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"F5C: A variant of Faug\u00e8re's F5 algorithm with reduced Gr\u00f6bner bases","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/F5C:_A_variant_of_Faug%C3%A8re%27s_F5_algorithm_with_reduced_Gr%C3%B6bner_bases"}}}}}