{"entities":{"Q862343":{"pageid":864191,"ns":120,"title":"Item:Q862343","lastrevid":64938561,"modified":"2026-04-11T23:14:00Z","type":"item","id":"Q862343","labels":{"en":{"language":"en","value":"Polynomial multiplication over finite fields: from quadratic to straight-line complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5118077"}},"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":"Q862343$D734B5B1-619A-4725-9B24-DA0AE6ED634A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"283522e800b7f5ee6ad6e5eafd1a9601369a62de","datavalue":{"value":{"text":"Polynomial multiplication over finite fields: from quadratic to straight-line complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q862343$CA8E85CF-C355-4576-B0A5-A418A584A349","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"daffab3e5fd9f11c0fcc1751b847d2d6bcf4baa1","datavalue":{"value":"1130.68062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q862343$A3DF4DE9-119B-401D-A939-66B599F2756A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5ea23ab68f685e1719f8b72c579f7993f3b0845","datavalue":{"value":{"entity-type":"item","numeric-id":287181,"id":"Q287181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862343$DCF161A2-15CA-4342-9BCE-C1A3DA46CB11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8cbf639b300d72e78610ef679f5196c1e753facf","datavalue":{"value":{"entity-type":"item","numeric-id":332085,"id":"Q332085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862343$68DBBFF5-5696-4F7D-886D-A71C2AA2A883","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862343$9841E199-469F-4C4E-A328-0414F36EC7DE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b780548d1931bae4ac5b1caff374698a268a9351","datavalue":{"value":{"time":"+2007-01-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q862343$2BBE8746-EFD1-452F-8E4F-71536846AF1F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8048d583bcd72f4957c6e3c4878a0ac2e6754ebf","datavalue":{"value":"To obtain the coefficients of the product of two degree \\(n\\) polynomials, its known that \\(2n\\) multiplications/divisions are required for straight-line algorithms, if the polynomials belong to infinite fields. For finite fields, however, there is an additional problem because of the lack of elements. In this paper, the authors show that computing the coefficients of the product of two \\(n\\)-degree polynomials over finite fields by straight-line algorithms requires at least \\(3n-o(n)\\) multiplications/divisions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q862343$E0B8F2B4-19CF-44F5-A193-3A5F727DF753","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q862343$4A46E7BE-B085-43D4-8D9F-B3EC438D9420","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"661c831991cdebd51f9465b74d929024bd00f373","datavalue":{"value":"12Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q862343$9B22FA3F-74BC-41D3-AB60-81B38CBB7065","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q862343$43935844-064B-4AEB-8AF4-3A1EBE4115CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q862343$4CEED8F6-37D8-4424-B459-DB6328D9DF9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q862343$614950A4-F05C-4CDD-A6AB-A0B3133BCC03","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"95a29be56fddd10a7267a355ce13003170dfa288","datavalue":{"value":"5118077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q862343$A832B951-2059-4F5D-8BC2-F86AB1DB2F6F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"90bc349d6d55eb8026148892e900ce256ffdd986","datavalue":{"value":"analysis of algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q862343$F20F1AA0-388A-40D9-A4BC-CB475C7E8229","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa65c8c5545344241b6a3f44870abc3959d5f6a0","datavalue":{"value":"straight-line algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q862343$5C74C7FA-069A-4779-9BF7-A17A3CBB15FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7fececce1852ae652754c42ff25444ca99d4b2a1","datavalue":{"value":"quadratic algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q862343$7EB2019B-34F3-436E-A8E9-1C52E3EE6757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5ba416b3228e58d69cc95841fcf815946973061","datavalue":{"value":"polynomial multiplication","type":"string"},"datatype":"string"},"type":"statement","id":"Q862343$A2E34BAF-99EA-4A6B-9C1A-380A3BF81181","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"57a05efc87855e633754ee0bacc3c29e0f2a2ffa","datavalue":{"value":"Hankel matrices","type":"string"},"datatype":"string"},"type":"statement","id":"Q862343$A12CD88A-31BE-4F4E-8790-65E869409BD4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2fbaabd45ced54cadc0390bc9cd343b83bec0729","datavalue":{"value":{"entity-type":"item","numeric-id":307804,"id":"Q307804"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q862343$1D971B21-4AAD-463D-B5E7-090A72E173B1","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":"Q862343$7FAFC9A5-6341-407A-9157-40FAF77ED317","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"71712a154eded85f41869db0ea0fe2848e761d9c","datavalue":{"value":"https://doi.org/10.1007/s00037-006-0215-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q862343$083FABFB-038E-4197-B564-617836CF8C54","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"537df9aef4a2e920dc49fd4bb0f4c80f0fac6ce3","datavalue":{"value":"W2090959762","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q862343$0BF3A38D-6441-4C41-8FC6-50EE2C0E7570","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a4bd7e9dfc0a4a2adc35b50aaf975031e1b0e57f","datavalue":{"value":"10.1007/S00037-006-0215-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q862343$FA86CBA8-C219-436C-B034-3615A821BE92","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"492fc0f29cae13dd315aef14adfad92d35be580a","datavalue":{"value":{"entity-type":"item","numeric-id":3832671,"id":"Q3832671"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f915191357a71fb57adaca3f4f359ed109163afd","datavalue":{"value":{"amount":"+0.95469713","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":"Q862343$66CD0666-2B01-47CD-85DA-35B8D1D62670","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc29315663720dc8df218a8b0a73cc57c07d4b5e","datavalue":{"value":{"entity-type":"item","numeric-id":5710701,"id":"Q5710701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4c5e41ba2397bb70a789ab8a19f9b619185422c","datavalue":{"value":{"amount":"+0.94029266","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":"Q862343$E044F40C-656D-4C52-BDD7-2CEE3516B513","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33de3c9a3574470cedb73f0ecec2223ddd9bed43","datavalue":{"value":{"entity-type":"item","numeric-id":5317184,"id":"Q5317184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4c5e41ba2397bb70a789ab8a19f9b619185422c","datavalue":{"value":{"amount":"+0.94029266","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":"Q862343$3497AFA0-8311-43A5-A972-A5EF0AF17FF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5046546756041ef159f13c49a73c4b42f021a985","datavalue":{"value":{"entity-type":"item","numeric-id":5066949,"id":"Q5066949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c88d60784f44c3b51c77a97eae7cdb232747cdd","datavalue":{"value":{"amount":"+0.9326901","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":"Q862343$97888FCA-231A-4D75-841E-FB3C955A17EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53f2baadadef45dedf296136d0f123c3b8e97559","datavalue":{"value":{"entity-type":"item","numeric-id":5706775,"id":"Q5706775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93240ab5e513d7b3f962a99fa5ac94c70ec61337","datavalue":{"value":{"amount":"+0.92227155","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":"Q862343$A42AC204-B487-4DE9-AF6C-54BD5B914572","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfd54fb66aa7c3c4d80e66b68f1f600a620092e6","datavalue":{"value":{"entity-type":"item","numeric-id":1171378,"id":"Q1171378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a445c325297f6e3ae7f5f53cc7ee01fc11e0c3d4","datavalue":{"value":{"amount":"+0.9198431","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":"Q862343$049A49DA-8B39-4ED3-9D7E-66BA5F8E7537","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4078caaff7a963d04c20cd7cef2aa8786d67846a","datavalue":{"value":{"entity-type":"item","numeric-id":3478495,"id":"Q3478495"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d36690de2f7b3517eb762d60d24783a66a6b8b3","datavalue":{"value":{"amount":"+0.9192735","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":"Q862343$778AD9CD-B5E7-4B6E-993E-C41E7AE53167","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d91c2e6eb62e5619aa74f569b8b379a5293dbc08","datavalue":{"value":{"entity-type":"item","numeric-id":6113915,"id":"Q6113915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9006d5b3fec7d2fe6aa3b8be4fa7c8c69c717c29","datavalue":{"value":{"amount":"+0.91850615","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":"Q862343$F5F61DCC-E789-4990-85E9-B3D98A99ADFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7158454b0ba788014a7d34600ec6be032071ef9","datavalue":{"value":{"entity-type":"item","numeric-id":3177879,"id":"Q3177879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f25f460b3589cb21d97b431374614ca6b0b3afa5","datavalue":{"value":{"amount":"+0.91796905","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":"Q862343$CD283DBD-EFFF-4935-8305-4147F04069C4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Polynomial multiplication over finite fields: from quadratic to straight-line complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Polynomial_multiplication_over_finite_fields:_from_quadratic_to_straight-line_complexity"}}}}}