{"entities":{"Q1110328":{"pageid":1121077,"ns":120,"title":"Item:Q1110328","lastrevid":49214692,"modified":"2026-01-06T18:58:56Z","type":"item","id":"Q1110328","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. I: The algebra \\(G[u]/<Q(u)^{\\ell}>\\), \\(\\ell >1\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4072373"}},"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":"Q1110328$DD0BF7F3-E1AD-4099-B7B6-DBCE112A2ABC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"318e314b12c29eefd8b81a8fb426050b69f55fc2","datavalue":{"value":{"text":"Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. I: The algebra \\(G[u]/<Q(u)^{\\ell}>\\), \\(\\ell >1\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1110328$17440F4C-18A5-4A38-8048-1BCADBFEA9E5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b46cbfad439d13fd6e6414a1e0a3c1acbe93846f","datavalue":{"value":"0656.68040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110328$BF88E16B-D396-48DB-90BD-1853170C89D8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ec590d9d1e55f264830203f785c2f8cada1d07d2","datavalue":{"value":"10.1016/0304-3975(88)90017-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110328$D23F16B1-A4CD-4B9E-B6C3-1A85B5985A73","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":"Q1110328$106AFA3F-B702-4B53-A2FC-6FB527EBB01E","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":"Q1110328$17EF07F7-999E-469D-87E2-9C503E231CD8","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":"Q1110328$54B6394A-1BD2-4902-A986-72BE5298511F","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":"Q1110328$59F1A17E-AB5F-417C-9DC6-C2651DB14907","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1110328$DB4194AA-FA4C-4F7C-9219-ED6CE8EA4B09","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b4f3a1a72b3b544fa389a3aa235982e96834048a","datavalue":{"value":"Let K be a field and let \\(r=\\sum^{n-1}_{i=0}x_ iu^ i\\in K[x_ 0,...,x_{n-1},u]\\) and \\(s=\\sum^{n-1}_{i=0}y_ iu^ i\\in K[y_ 0,...,y_{n-1},u]\\) be polynomials with indeterminate coefficients. Let h be a polynomial of degree n in K[u]. This paper investigates algorithms for computing \\(rs\\quad mod h\\in K[x_ 1,...,x_{n-1},y_ 1,...,y_{n- 1},u].\\) A bilinear algorithm is an algorithm that uses apart from computations in K only multiplications of the form \\((\\sum^{n- 1}_{i=0}u_ ix_ i)(\\sum^{n-1}_{i=0}t_ iy_ i)\\). A minimal bilinear algorithm for a given computation uses the least number of such multiplications.    In this paper the minimal bilinear algorithms for computing rs mod h in the case that \\(h=q^{\\ell}\\) is given, where q is a monic irreducible polynomial over K and \\(\\ell >1\\). Moreover, they assume that \\(\\deg (q)>1\\). They find that the minimal algorithms all use 2n-1 multiplications of the given form. In all these algorithms one of the following facts is used:  \\[  rs=rs\\quad mod\\prod^{2n-2}_{i=0}(u-\\alpha_ i)\\quad,  \\]  or  \\[  rs=(rs\\quad mod\\prod^{2n-2}_{i=1}(u-\\beta_ i))+x_{n-1}y_{n- 1}(u-\\beta_ i)\\quad,  \\]  for certain \\(\\alpha_ i\\) or \\(\\beta_ i\\) in K. These computations are done by using the fact that rs mod (u- \\(\\alpha)=r(\\alpha)s(\\alpha).\\)    The cases that \\(\\ell =1\\) or that h is the product of two relatively prime polynomials is treated before. The case that \\(\\ell >1\\) and \\(\\deg (q)=1\\) will be treated in a forthcomming paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110328$72F0ACAE-86F6-44C4-9D2D-0B7D090E9DBE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110328$1E4620B7-F450-4E95-86FF-B5C12361B684","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110328$E1FBBA5B-C918-4671-AF6A-5130DC2A982D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cfeaad0862a23378a3c738963be2d25d4928c7a1","datavalue":{"value":"12-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110328$AC8EF025-76DD-4FE8-9DFC-96B348362A73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"56c7f76923b29a06e5df502ec9e72c901e9849fe","datavalue":{"value":"12E05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110328$2B219D27-F93F-43F9-9FC1-239C74F2E557","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"03e27ff08db84d977ad8b44cc695b33f6231b4cb","datavalue":{"value":"4072373","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110328$A2E3315D-FDCB-4837-B872-E484822B9E4B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"010c7d2ed2de24e1d8a535188cc19c40627ba1be","datavalue":{"value":"algebraic complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110328$0A125C47-258E-4211-8B87-349CE48B083C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"729574a0d5a12d874f96ca0fd1bc8eccc82a4543","datavalue":{"value":"minimal bilinear algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1110328$6C2E1071-EA57-4061-A807-690A4C7B48AE","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":"Q1110328$9F580F15-C673-4DEB-A504-BD8053607B1D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1276daf2f5de3036b02ec9d13314576a844ab5db","datavalue":{"value":"https://doi.org/10.1016/0304-3975(88)90017-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1110328$15DFFC5A-759A-4300-B424-5BB0D334D2D6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ae0050889859058a4ec6f150f22de7063b46f130","datavalue":{"value":"W2060449504","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1110328$8478F53A-588B-4C20-B15E-53AD7FF48B86","rank":"normal"}],"P223":[{"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":"Q1110328$6ED2FB24-37A1-408E-B272-77F25D1B4E2B","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":"Q1110328$8F54210A-C44B-4E08-B8BA-1F943C133170","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b45bb4a89b164c364e53b0d578d39c18c4748fb4","datavalue":{"value":{"entity-type":"item","numeric-id":3883493,"id":"Q3883493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110328$B5259C60-8375-455C-BC42-2BF763E33196","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a148e12ed1f41044f529beae0e83ef7878225c9f","datavalue":{"value":{"entity-type":"item","numeric-id":5584925,"id":"Q5584925"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110328$F3D98B7B-A95D-4BAE-95E5-A0BB1F4711F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"009aa9032d460a712726f3301e92c16c0440e104","datavalue":{"value":{"entity-type":"item","numeric-id":1259162,"id":"Q1259162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110328$B99B3CDE-7171-4C71-B568-F11F2B4CC79B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0582a0a6fffe4ca8a1004571425ae9626fef4114","datavalue":{"value":{"entity-type":"item","numeric-id":4151723,"id":"Q4151723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110328$ECEC077E-ACCF-42A7-8B6C-0014D5AC6D64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0618290a7b629940c987789b6eb12858fbd01f56","datavalue":{"value":{"entity-type":"item","numeric-id":5601777,"id":"Q5601777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110328$FE7D94CF-C5F5-4A87-89DD-77BB49D3B1FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a6e7df10e35257d1931ffe195771015adc6b558f","datavalue":{"value":{"entity-type":"item","numeric-id":4160410,"id":"Q4160410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110328$99636354-9F2E-436D-BEA5-8103E581D54D","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":"Q1110328$B91DC3A2-2B72-4612-82C3-5F180CD9A127","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":"Q1110328$EDF15744-2F93-4DD1-9F88-D24A2E251F8D","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":"Q1110328$B5BE42E4-3F21-4604-9B15-D0364D73B926","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":"Q1110328$C27E8D32-091E-43A9-B4AA-3773DCE41077","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":"Q1110328$10C509E7-3334-4B20-84D2-9DC9E327A391","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a07070aa51b63ecd4a1f71f26fb5b118fb8d3703","datavalue":{"value":{"entity-type":"item","numeric-id":3776615,"id":"Q3776615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1110328$456332AB-C3F2-46B8-BC26-5A8CDAB64FCD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3994ae276d2e2eb725aa4e73822f88593f03e97e","datavalue":{"value":{"entity-type":"item","numeric-id":1178708,"id":"Q1178708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54da27dc3095dee841646bd6d906c7d420c9861f","datavalue":{"value":{"amount":"+0.957697093486786","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":"Q1110328$E3951D55-27F1-4253-A012-DB93C7E69FA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8dcb84df4c691618851a2ba89777d236a7cb73aa","datavalue":{"value":{"entity-type":"item","numeric-id":4217863,"id":"Q4217863"},"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":"Q1110328$CABEBBFD-1AF3-4A34-9C3A-64BC44729EA3","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":"a0f4c8db6c73c9a1fc10c2cda3066d937ee5cfbf","datavalue":{"value":{"amount":"+0.9523671269416808","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":"Q1110328$963C6466-89C7-4269-84B8-14175A39FCC8","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":"36d8262f3ec8a3c0597d493ab087f2b301a850ed","datavalue":{"value":{"amount":"+0.8167549967765808","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":"Q1110328$CA1B18C6-3432-44CD-A357-4194952778D8","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":"9d8f5895005ca31ed6fdbf75548bc2fe26285e17","datavalue":{"value":{"amount":"+0.8110495209693909","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":"Q1110328$F88F1757-9BEE-40A0-A90B-CC08F44D6B3B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1110328","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1110328"}}}}}