{"entities":{"Q850783":{"pageid":852631,"ns":120,"title":"Item:Q850783","lastrevid":49963585,"modified":"2026-01-12T08:06:04Z","type":"item","id":"Q850783","labels":{"en":{"language":"en","value":"Polynomial basis multiplication over \\(\\text{GF}(2^m)\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5070964"}},"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":"Q850783$BD8ECD36-B377-4677-A967-D40CB32F4071","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2123083a0e6a614db4b1cdb34f11e160fb65ee96","datavalue":{"value":{"text":"Polynomial basis multiplication over \\(\\text{GF}(2^m)\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q850783$6D69F5EA-BC61-4E88-A7C1-6AFF1FF10D9B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5d0ab66ea6b3c572e2f4ce6a32342798d1214edd","datavalue":{"value":"1108.11089","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q850783$2A21CD4C-9CC6-4976-944F-FE02E3FAFC95","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"55ca4542eea0d4fab23294e170d818cc19129934","datavalue":{"value":{"entity-type":"item","numeric-id":850781,"id":"Q850781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q850783$94B91BB8-45F2-4602-9D31-5FA2078C35CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4c7f501714e968968dea65722a881e323b82d28f","datavalue":{"value":{"entity-type":"item","numeric-id":850782,"id":"Q850782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q850783$E928FAE7-2D5E-47CB-BB0E-771EC8D0541A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6cdee9a1b6c5b80989dfaf599ac468ebed2c828","datavalue":{"value":{"entity-type":"item","numeric-id":1319518,"id":"Q1319518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q850783$6454FBFE-ABAA-469B-ACF8-1F4C9F754A88","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8d1231d86866fb01586b04e1f50e347c0a84f9cd","datavalue":{"value":{"entity-type":"item","numeric-id":190587,"id":"Q190587"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q850783$342AF318-8244-4026-A9FD-95BE956B9A92","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c71db60bf43a1ea4dede9849e45957abbf8f35c4","datavalue":{"value":{"time":"+2006-11-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q850783$A7E8B0F7-424C-4F6C-A2E0-55CDF803FC8C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d3a8a7bfac90e207c80a37b7bd6847d864664c47","datavalue":{"value":"The purpose of this survey is, in the authors' words, ``to describe, analyze and compare various \\(\\text{GF}(2^m)\\) multipliers''.  Efficient hardware and software implementations of the multiplication in binary finite fields \\(\\text{GF}(2^m)\\), with \\(m\\) large, are crucial in applications such as Cryptography. The authors argue that ``multiplication methods that use polynomial base representations are very efficient in comparison to the best methods using other basis representations''.  Section 2 of the paper introduces to the problem of polynomial basis multiplication of two \\(\\text{GF}(2^m)\\) elements and its two main stages: multiplication of two degree \\(m-1\\) polynomials \\(a(x), b(x)\\) and reduction of the product \\(d(x)\\) modulo the degree \\(m\\) irreducible polynomial \\(\\omega(x)\\) defining \\(\\text{GF}(2^m)\\), to obtain a field element \\(c(x)\\). In Section 3 the authors calculate the space and time complexity of these two arithmetic operations. Particular attention is paid to the cases \\(\\omega(x)\\) an equally spaced polynomial and \\(\\omega(x)\\) an \\(r\\)-nomial, cases that provide better complexity in the modular reduction.  Section 4 of the paper reviews the matrix vector product techniques. An approach is to reduce the polynomial \\(d(x)\\) using an \\((m \\times m-1)\\) reduction matrix, defined in terms of \\(\\omega(x)\\). A second approach is to simultaneously perform the polynomial multiplication and the reduction operation using the so-called (\\(m\\times m\\)) Mastrovito matrix, whose entries are function of the coefficients of \\(\\omega(x)\\) and the polynomial \\(a(x)\\) (the multiplicand), see [\\textit{E. D. Mastrovito}, Applied algebra, algebraic algorithms and error-correcting codes, Proc. 6th Int. Conference, AAECC-6, Rome/Italy 1988, Lect. Notes Comput. Sci. 297--309 (1988; Zbl 0673.94024)]. Tables with complexities for both techniques are provided.  Finally the Montgomery multiplication method is explained in Section 5. The Montgomery multiplication [see \\textit{C. K. Koc} and \\textit{T. Acar}, Des. Codes Cryptogr. 14, No. 1, 57--69 (1998; Zbl 0887.11054)] calculates \\(c(x)=a(x)b(x)r(x)^{-1} \\bmod \\omega(x)\\), where \\(r(x)\\) is a fixed polynomial (Koc and Acar take \\(r=x^m\\)). The special case where \\(\\omega(x)\\) is an irreducible trinomial gives good space and time complexity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q850783$96652541-2D88-405B-91E2-C2317BCE07CE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q850783$94D12869-7C8C-4412-A25A-706DCB543A87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cd80e9ade304e6b9b43fd50d0c3436276c3c217e","datavalue":{"value":"68M07","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q850783$70018013-ADD9-4FCF-8476-9EE11033B428","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"58bd804a9b32ab16fea71636cf187b83a20de8f7","datavalue":{"value":"68P25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q850783$C28E1A52-0D14-45F1-BEBB-C50A6D640894","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dcefd1e200eae54420c5080733f6b5a349da9f6a","datavalue":{"value":"11T71","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q850783$C2E3E8D6-B7DE-4F9D-85BD-3619354BB41C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e054c62c15164857bca592628e30c0fe69046df4","datavalue":{"value":"5070964","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q850783$6EA27483-9770-470B-84B0-A48EBBB5DA70","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac07c7d6c5cdc2dbc4590f3ecbac0ebb59196bea","datavalue":{"value":"finite fields","type":"string"},"datatype":"string"},"type":"statement","id":"Q850783$B1072CAD-AA21-4400-9982-90FA259A67A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f2331ea390dc0c561720d015f9e2f312de9629a","datavalue":{"value":"binary fields","type":"string"},"datatype":"string"},"type":"statement","id":"Q850783$8F845389-0B27-4575-9829-79CFCEE47916","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"96b6ad93fcf346e772b6dba2265b62bf50199db5","datavalue":{"value":"polynomial basis","type":"string"},"datatype":"string"},"type":"statement","id":"Q850783$10B4BCB2-C438-4377-A77F-CA0D83D386BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e5b7d825081d90817135f688e03582cc5c56d14c","datavalue":{"value":"modular multiplication","type":"string"},"datatype":"string"},"type":"statement","id":"Q850783$FB83BF2D-6E87-4370-9DF7-3F80EF71E34E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af3afd72e9a0403714267016ea206d8ec976b321","datavalue":{"value":"matrix reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q850783$3CD5CECA-231C-4530-AE58-309A91419F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"126d250390ac61689f468307204c4233f414ada7","datavalue":{"value":"Montgomery multiplication","type":"string"},"datatype":"string"},"type":"statement","id":"Q850783$9E71470E-94DA-4AF4-8D44-1F7EEEE4AF06","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8892955fafe16ba1bddb104e5d82ec8889d70fd9","datavalue":{"value":{"entity-type":"item","numeric-id":1313210,"id":"Q1313210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q850783$BB456A8A-89CF-4161-8422-B351723A09A4","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":"Q850783$FF707243-6527-4FCF-BFBC-58316D6B78FB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d87663dc85add9cf6b32c5c3613fb3dc052cda2a","datavalue":{"value":"https://doi.org/10.1007/s10440-006-9047-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q850783$2BAFC648-DC93-46FF-9576-31A6F8649104","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2cefdb6454264ab633d417b931a2f31b59cbdb4c","datavalue":{"value":"W2052587062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q850783$E4EEDCD7-0B0D-4EAB-8722-36FD50B12093","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"91f3410d6c5276a805ba8541b348c8d711b59e40","datavalue":{"value":{"entity-type":"item","numeric-id":1124585,"id":"Q1124585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q850783$E0FDE31A-B97B-43A8-BBF4-8EE109E265FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73576cbb40a2d9b98f32fda2fbb02b450761dcce","datavalue":{"value":{"entity-type":"item","numeric-id":1379662,"id":"Q1379662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q850783$050598E4-CCB5-45A8-B97D-0D5CEEB0C64B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e71cc6aa4f26e84d5067311c35aaa9955e645252","datavalue":{"value":{"entity-type":"item","numeric-id":4301239,"id":"Q4301239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q850783$54F07E25-18B9-4340-9FE0-0904CF846C35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c5c1aa602e2ab6867eb09c994970bc604aacfee","datavalue":{"value":{"entity-type":"item","numeric-id":4718481,"id":"Q4718481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q850783$AD2FC905-F5C8-4386-A2BE-99F4BD7B6001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26667b76d24fd875d0bc9653c54f53624ba7af44","datavalue":{"value":{"entity-type":"item","numeric-id":3417023,"id":"Q3417023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q850783$E5260271-9C30-4D8C-AD85-D73D7A386986","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c66415771b5992e7982348703bc9d18134f87afc","datavalue":{"value":{"entity-type":"item","numeric-id":4571476,"id":"Q4571476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q850783$27F0F5DC-160D-446C-AF07-2A0B5A99F59E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f550df79344a60be9f8e339fe43d1fe0db6f00f","datavalue":{"value":{"entity-type":"item","numeric-id":4571292,"id":"Q4571292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q850783$E50F8545-6003-4CF1-B6E4-79E82A45B346","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d176677a75356a70462e912fa0eca3f10a94a02","datavalue":{"value":{"entity-type":"item","numeric-id":4571282,"id":"Q4571282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q850783$E4BD248C-B469-473D-BDF1-CA45FCA4041D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"893e4d869b21c4d6968f24ebf49476cdd318abb7","datavalue":{"value":"10.1007/S10440-006-9047-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q850783$026D875B-75E8-421E-A9D8-E81A446F7B65","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bfd20909191329fe49ad035ee8c52f1343eb1675","datavalue":{"value":{"entity-type":"item","numeric-id":4536232,"id":"Q4536232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"245f92bd60cc1d926511a90c173c672cbf5f626e","datavalue":{"value":{"amount":"+0.8621012568473816","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q850783$307D1B5B-4DFF-444F-9CA5-A55713108A7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83008eb3f42e3e5f6dfea31c1e8cb7b7b271183a","datavalue":{"value":{"entity-type":"item","numeric-id":1379662,"id":"Q1379662"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c68fa398a826735ac5078b7f50767c280ee917c","datavalue":{"value":{"amount":"+0.8501279354095459","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q850783$C56D030B-6B85-4D59-9BEB-0665573F24C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8532805531c87d6914db9842d290e79d4b38335","datavalue":{"value":{"entity-type":"item","numeric-id":2512883,"id":"Q2512883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d942635350d051043b07849a88d60f2351ec4b74","datavalue":{"value":{"amount":"+0.8345251679420471","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q850783$A3F397EC-7734-40C2-873D-087AC38F77FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ea31a6077c16b0fbd0aaa42056a2bc5a3e8b722","datavalue":{"value":{"entity-type":"item","numeric-id":605724,"id":"Q605724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"71a97b7a1b00dbbd7644f8b815f0f2fca51e0ed2","datavalue":{"value":{"amount":"+0.8228638768196106","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q850783$60E4977B-4E56-4570-A894-E46978A7553E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d75266862cc149639955b5abcf82bb732b26846b","datavalue":{"value":{"entity-type":"item","numeric-id":2707607,"id":"Q2707607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a4002651465b8e3a80c1d1468b35e5fbd9850e5","datavalue":{"value":{"amount":"+0.8219201564788818","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q850783$6BAD64FE-A369-4425-B654-E2614380BC43","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:850783","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:850783"}}}}}