{"entities":{"Q1178708":{"pageid":1189457,"ns":120,"title":"Item:Q1178708","lastrevid":46235452,"modified":"2025-12-24T09:12:41Z","type":"item","id":"Q1178708","labels":{"en":{"language":"en","value":"Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. II: The algebra \\(G[u]/\\langle{} u^ n \\rangle\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 22293"}},"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":"Q1178708$68597558-5FDC-4A6F-AAB8-E31A730C1689","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"841117090b40ef45037a466d331452b2090c9349","datavalue":{"value":{"text":"Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. II: The algebra \\(G[u]/\\langle{} u^ n \\rangle\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1178708$69EF398F-06A0-411A-9F98-265DD8859094","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8ee573cc426fdf614d671162a63dfa1460d75fe9","datavalue":{"value":"0744.68071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178708$E2C5C13B-7D60-4CA1-8177-2EA5B7BBD87A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7754ae83eeb204d4e84e74630cc8f21c67bb18de","datavalue":{"value":"10.1016/0304-3975(91)90017-V","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178708$A44B6329-5466-4E72-BC70-D1C0A2AFAAA1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e427d06588e0f5e6a2a228b1ad8e00160bd43819","datavalue":{"value":{"entity-type":"item","numeric-id":673782,"id":"Q673782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178708$963A4F28-ECAE-4453-93D8-A9956BBAB9B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"369d0fc64902ba457c90a72163d431dd4d6b3cda","datavalue":{"value":{"entity-type":"item","numeric-id":915377,"id":"Q915377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178708$7CB44E49-3645-4DF8-92DC-C364F6E9CF1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3c17305e90cde68594c134869360740e7e1b8ad","datavalue":{"value":{"entity-type":"item","numeric-id":130265,"id":"Q130265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178708$B827B9E1-895F-499D-8F9C-80E5190F97E0","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178708$B1CB624B-2861-4099-B166-1E95B4CF084F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1422b5e3113eee9dc98f0455d275631058399b8b","datavalue":{"value":{"time":"+1992-06-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1178708$E718A6EA-840B-4A98-BB1F-F9F614CEF5C5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f69b0f5c890337a99e575d8305c11f26e32ab9dc","datavalue":{"value":"This paper deals with the classification of all minimal bilinear algorithms for the computation of a product of polynomials modulo another polynomial \\(R\\). As a consequence of the Chinese remainder theorem it is only interesting to consider the case that \\(R=Q^ \\ell\\) is a power of an irreducible polynomial \\(Q\\). The case that \\(\\ell=1\\) was already treated by \\textit{S. Winograd} [Theor. Comput. Sci. 8, 337-359 (1979; Zbl 0404.12016)]. The case that \\(\\ell>1\\) and \\(\\deg(Q)>1\\) was treated in the first part of the paper [\\textit{A. Averbuch}, \\textit{Z. Galil} and \\textit{S. Winograd}, Theor. Comput. Sci. 58, 17-56 (1988; Zbl 0656.68040)]. In this part the final case \\(\\ell>1\\) and \\(\\deg(Q)=1\\) is treated.   A minimal algorithm for computing the product of two polynomials modulo \\(u^ n\\) needs \\(2n-1\\) multiplications. Together with the results of the above mentioned papers it is shown that each minimal algorithm needs first to compute the coefficients of the product after which reduction is being done, hence large coefficients will appear during the computation.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178708$A6BADF96-2D1B-447E-844C-F63B6BD6687A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178708$B4491B44-8191-40EF-A3F9-7125147BEB3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"56c7f76923b29a06e5df502ec9e72c901e9849fe","datavalue":{"value":"12E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178708$3CF7BED4-66CB-4D32-93B5-081459BEEA02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178708$E1AE1486-6EE6-4BBE-B372-62DAAD2A644D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfeaad0862a23378a3c738963be2d25d4928c7a1","datavalue":{"value":"12-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178708$1D2387DD-5395-4300-AC94-6BA4B7C8C06E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e20915aa87f0d1dba065c05a7194e2b871edc1a9","datavalue":{"value":"22293","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178708$41D41E37-2F53-4CB3-A830-8AD7B3F684CF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc440ab64fdaadee37148239a8b2c4508ddb6593","datavalue":{"value":"field extension","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178708$FEFE5B8C-A2A1-43E4-9E33-5D7F69264757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b7a609ae2c21271342f267522dda74375687f014","datavalue":{"value":"polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178708$D4AA5284-C4AB-45AD-B6E4-2CD8B537310A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eccdd3fae1221938902e16932ea76f465483c2ca","datavalue":{"value":"minimal algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1178708$73997F38-F8FF-4935-9E7B-FCCA42157C7F","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":"Q1178708$F4E5F207-731D-4A08-9B66-2ECBB56C8835","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"48e22368efa0029f53e971924039c774f20c0c05","datavalue":{"value":{"entity-type":"item","numeric-id":1110328,"id":"Q1110328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178708$EC62B95F-EC1E-47DC-82C3-E5F5BEBC69C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dc65d328815feba27b4a16b92ab8bc09d86153e","datavalue":{"value":{"entity-type":"item","numeric-id":1131837,"id":"Q1131837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178708$3F865FB6-5B4A-4EB9-87C4-B7E78177178D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8da029e0a020010527506db93642b6f1c889e51","datavalue":{"value":{"entity-type":"item","numeric-id":1131838,"id":"Q1131838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178708$49C1C773-DB56-486D-913D-B5B2342E15CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13eb6bd839e26f22339cf27d0277356cb8637f35","datavalue":{"value":{"entity-type":"item","numeric-id":1146511,"id":"Q1146511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178708$6A46E56F-8813-4AC0-B485-AA544649B333","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bf856dc30e4afd9702dce1e371cd8c3a736b290","datavalue":{"value":{"entity-type":"item","numeric-id":3932296,"id":"Q3932296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178708$EA40FC13-8EFE-44AA-9F06-04FF2BB475DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e03a7b4ba755e265a186b061098bbfcb19203df3","datavalue":{"value":{"entity-type":"item","numeric-id":3667942,"id":"Q3667942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178708$513AFD4C-CDA8-4ED2-AC8B-0CA948C4DA99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa87e1f61f7929222f282235b48050c729363cd8","datavalue":{"value":{"entity-type":"item","numeric-id":1256512,"id":"Q1256512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178708$36D74C0E-312D-4D58-80EC-9305BDE86B82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1ee5add50999429f8a8274298b6925d30bc96d7","datavalue":{"value":{"entity-type":"item","numeric-id":4138004,"id":"Q4138004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1178708$69457450-5664-47CD-A224-8AD70A7FE999","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b7cbc049fc6a9bc16f7211b5b23a998079d59821","datavalue":{"value":"https://doi.org/10.1016/0304-3975(91)90017-v","type":"string"},"datatype":"url"},"type":"statement","id":"Q1178708$09B28042-BE4B-4CFE-94F0-2606F4A12904","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e1bbff44528f292c6f43a4b7b1fc3a03bcabbfb6","datavalue":{"value":"W4205152297","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1178708$8EB00E4B-868C-40B8-AE21-8871F8016E78","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4abba0bb0734da153cad9a40ce2f657f630bcc87","datavalue":{"value":{"entity-type":"item","numeric-id":1110328,"id":"Q1110328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e6a4d7e3ae5a1772e483e1642d3ddbe948a1d85","datavalue":{"value":{"amount":"+0.9548115134239196","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":"Q1178708$DF2629F7-5589-4C78-8A7C-0E542F7AF603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ea1a421180c9ea98675ebcfd57fa02e7b521d0a","datavalue":{"value":{"entity-type":"item","numeric-id":3776615,"id":"Q3776615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1a99044a9268f84761e3b6627082c9216848aae","datavalue":{"value":{"amount":"+0.9358413219451904","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":"Q1178708$D871572C-1897-4603-A282-CDA320E0D172","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff6eb5a8fdbba9c739f964d68e53f60fa8de5494","datavalue":{"value":{"entity-type":"item","numeric-id":4015275,"id":"Q4015275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20280bb880b7c62ce1c8ada6f9f52165bd54ce63","datavalue":{"value":{"amount":"+0.8054696917533875","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":"Q1178708$A0A98143-736D-4F4C-844C-10D183A4311E","rank":"normal"},{"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":"9f27e95481005fae882d0491bc33dda45d97c5a6","datavalue":{"value":{"amount":"+0.7861021757125854","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":"Q1178708$8DCF52AB-D272-4B11-81B7-88849349BEAC","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":"7d43b893dbb15aec78188f9965ec37398e40ceb3","datavalue":{"value":{"amount":"+0.773385763168335","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":"Q1178708$4FFF168A-6809-45E4-9FA5-B69A96209077","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1178708","badges":[]}}}}}