{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T04:26:49Z","timestamp":1778128009180,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,7,24]],"date-time":"2023-07-24T00:00:00Z","timestamp":1690156800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,7,24]]},"DOI":"10.1145\/3597066.3597077","type":"proceedings-article","created":{"date-parts":[[2023,7,5]],"date-time":"2023-07-05T18:15:27Z","timestamp":1688580927000},"page":"270-279","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Refined F5 Algorithms for Ideals of Minors of Square Matrices"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-0473-7291","authenticated-orcid":false,"given":"Sriram","family":"Gopalakrishnan","sequence":"first","affiliation":[{"name":"Sorbonne Universit\u00e9, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8311-9490","authenticated-orcid":false,"given":"Vincent","family":"Neiger","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9463-1257","authenticated-orcid":false,"given":"Mohab","family":"Safey El Din","sequence":"additional","affiliation":[{"name":"Sorbonne Universit\u00e9, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,7,24]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(81)90055-4"},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings CRYPTO","author":"Baena J.","year":"2022","unstructured":"J. Baena, P. Briaud, D. Cabarcas, R. Perlner, D. Smith-Tone, and J. Verbel. 2022. Improving Support-Minors Rank Attacks: Applications to GeMSS and Rainbow. In Proceedings CRYPTO 2022. Springer, Cham, 376\u2013405."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1108638.1716342"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2014.02.005"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00200-009-0117-1"},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings ISSAC","author":"Bannwarth I.","year":"2015","unstructured":"I. Bannwarth and M. Safey El Din. 2015. Probabilistic Algorithm for Computing the Dimension of Real Algebraic Sets. In Proceedings ISSAC 2015. ACM, 37\u201344."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45727-3_3"},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings ASIACRYPT","author":"Bardet M.","year":"2020","unstructured":"M. Bardet, M. Bros, D. Cabarcas, P. Gaborit, R. Perlner, D. Smith-Tone, J.-P. Tillich, and J. Verbel. 2020. Improvements of Algebraic Attacks for Solving the Rank Decoding and MinRank Problems. In Proceedings ASIACRYPT 2020. 507\u2013536."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2014.09.025"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2012.07.001"},{"key":"e_1_3_2_1_11_1","unstructured":"J. Berthomieu C. Eder and M. Safey El\u00a0Din. 2022. New efficient algorithms for computing Gr\u00f6bner bases of saturation ideals (F4SAT) and colon ideals (Sparse-FGLM-colon). (2022). https:\/\/hal.science\/hal-03590430 Working paper."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-15979-4_16"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"W. Bruns A. Conca C. Raicu and M. Varbaro. 2022. Determinants Gr\u00f6bner bases and cohomology. Springer.","DOI":"10.1007\/978-3-031-05480-8"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"W. Bruns and U. Vetter. 1988. Determinantal Rings. Springer Berlin Heidelberg.","DOI":"10.1007\/BFb0080378"},{"key":"e_1_3_2_1_15_1","volume-title":"Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Ph.\u00a0D. Dissertation","author":"Buchberger B.","unstructured":"B. Buchberger. 1965. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Ph.\u00a0D. Dissertation. University of Innsbruck."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1608"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45682-1_24"},{"key":"e_1_3_2_1_18_1","volume-title":"D.\u00a0A. Cox, J. Little, and D. O\u2019Shea. 2015. Ideals, Varieties, and Algorithms","unstructured":"D.\u00a0A. Cox, J. Little, and D. O\u2019Shea. 2015. Ideals, Varieties, and Algorithms (fourth edition). Springer."},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings ACNS","author":"Ding J.","year":"2005","unstructured":"J. Ding and D. Schmidt. 2005. Rainbow, a New Multivariable Polynomial Signature Scheme. In Proceedings ACNS 2005. Springer, 164\u2013175."},{"key":"e_1_3_2_1_20_1","series-title":"Series A, Mathematical and Physical Sciences 269, 1337","volume-title":"Ideals Defined by Matrices and a Certain Complex Associated with Them. Proceedings of the Royal Society of London","author":"Eagon A.","year":"1962","unstructured":"J.\u00a0A. Eagon and D.\u00a0G. Northcott. 1962. Ideals Defined by Matrices and a Certain Complex Associated with Them. Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences 269, 1337 (1962), 188\u2013204."},{"key":"e_1_3_2_1_21_1","unstructured":"C. Eder and J.-C. Faug\u00e8re. 2016. A survey on signature-based algorithms for computing Gr\u00f6bner basis computations. J. Symbolic Comput. (2016) 1\u201375."},{"key":"e_1_3_2_1_22_1","volume-title":"Commutative Algebra: with a View Toward Algebraic Geometry","author":"Eisenbud D.","unstructured":"D. Eisenbud. 1995. Commutative Algebra: with a View Toward Algebraic Geometry. Springer."},{"key":"e_1_3_2_1_23_1","volume-title":"The geometry of syzygies: A second course in commutative algebra and algebraic geometry. Vol.\u00a0229","author":"Eisenbud D.","unstructured":"D. Eisenbud. 2005. The geometry of syzygies: A second course in commutative algebra and algebraic geometry. Vol.\u00a0229. Springer."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(99)00005-5"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/780506.780516"},{"key":"e_1_3_2_1_26_1","volume-title":"Proceedings CRYPTO","author":"Faug\u00e8re J.-C.","year":"2008","unstructured":"J.-C. Faug\u00e8re, F. Levy-dit-Vehel, and L. Perret. 2008. Cryptanalysis of MinRank. In Proceedings CRYPTO 2008. Springer, 280\u2013296."},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings ISSAC","author":"Faug\u00e8re J.-C.","year":"2010","unstructured":"J.-C. Faug\u00e8re, M. Safey El Din, and P.-J. Spaenlehauer. 2010. Computing loci of rank defects of linear matrices using Gr\u00f6bner bases and applications to cryptology. In Proceedings ISSAC 2010. 257\u2013264."},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings ISSAC","author":"Faug\u00e8re J.-C.","year":"2012","unstructured":"J.-C. Faug\u00e8re, M. Safey El Din, and P.-J. Spaenlehauer. 2012. Critical points and Gr\u00f6bner bases: the unmixed case. In Proceedings ISSAC 2012. ACM, 162\u2013169."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.03.004"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0032839"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/130931308"},{"key":"e_1_3_2_1_32_1","unstructured":"The FFLAS-FFPACK group. 2019. FFLAS-FFPACK: Finite Field Linear Algebra Subroutines \/ Package (v2.4.1 ed.). http:\/\/github.com\/linbox-team\/fflas-ffpack."},{"key":"e_1_3_2_1_33_1","first-page":"16","article-title":"Un complexe r\u00e9solvant pour certains id\u00e9aux d\u00e9terminantiels","volume":"274","author":"Gulliksen H.","year":"1972","unstructured":"T.\u00a0H. Gulliksen and O.\u00a0G. Neg\u00e5rd. 1972. Un complexe r\u00e9solvant pour certains id\u00e9aux d\u00e9terminantiels. C. R. Acad. Sci. Paris 274 (1972), 16\u201318.","journal-title":"C. R. Acad. Sci. Paris"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2020.09.008"},{"key":"e_1_3_2_1_35_1","volume-title":"Proceedings ISSAC","author":"Hong H.","year":"2009","unstructured":"H. Hong and M. Safey El Din. 2009. Variant real quantifier elimination: algorithm and application. In Proceedings ISSAC 2009. 183\u2013190."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2011.05.014"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2013.04.004"},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings CRYPTO","author":"Kipnis A.","year":"1999","unstructured":"A. Kipnis and A. Shamir. 1999. Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization. In Proceedings CRYPTO 1999. Springer, 19\u201330."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0021-8693(89)90140-3"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2021.101557"},{"key":"e_1_3_2_1_41_1","volume-title":"Proceedings ISSAC","author":"Lairez P.","year":"2021","unstructured":"P. Lairez and M. Safey El Din. 2021. Computing the Dimension of Real Algebraic Sets. In Proceedings ISSAC 2021. ACM, 257\u2013264."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(78)90037-3"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-12868-9_99"},{"key":"e_1_3_2_1_44_1","volume-title":"Proceedings ISSAC","author":"Le P.","year":"2021","unstructured":"H.\u00a0P. Le and M. Safey El Din. 2021. Faster one block quantifier elimination for regular polynomial systems of equations. In Proceedings ISSAC 2021. 265\u2013272."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1994.1062"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68339-9_4"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/860854.860901"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2996450"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/130936294"},{"key":"e_1_3_2_1_50_1","volume-title":"Algorithms for Matrix Canonical Forms. Ph.\u00a0D. Dissertation","author":"Storjohann A.","unstructured":"A. Storjohann. 2000. Algorithms for Matrix Canonical Forms. Ph.\u00a0D. Dissertation. Swiss Federal Institute of Technology \u2013 ETH."},{"key":"e_1_3_2_1_51_1","unstructured":"The Sage Developers. 2022. SageMath the Sage Mathematics Software System (Version 9.8.beta6). https:\/\/www.sagemath.org."}],"event":{"name":"ISSAC 2023: International Symposium on Symbolic and Algebraic Computation 2023","location":"Troms\u00f8 Norway","acronym":"ISSAC 2023"},"container-title":["Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3597066.3597077","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3597066.3597077","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T09:34:55Z","timestamp":1755855295000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3597066.3597077"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,24]]},"references-count":51,"alternative-id":["10.1145\/3597066.3597077","10.1145\/3597066"],"URL":"https:\/\/doi.org\/10.1145\/3597066.3597077","relation":{},"subject":[],"published":{"date-parts":[[2023,7,24]]},"assertion":[{"value":"2023-07-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}