{"entities":{"Q1808846":{"pageid":1819588,"ns":120,"title":"Item:Q1808846","lastrevid":46876242,"modified":"2025-12-25T18:40:42Z","type":"item","id":"Q1808846","labels":{"en":{"language":"en","value":"Curves with many points and multiplication complexity in any extension of \\(\\mathbb{F}_q\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1369827"}},"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":"Q1808846$1E336A92-D317-4AA0-9296-20582658C296","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0e206ec110e81aae37540d07b3ddabb59f24b3a6","datavalue":{"value":{"text":"Curves with many points and multiplication complexity in any extension of \\(\\mathbb{F}_q\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1808846$00743093-8DD4-4BC3-A57E-76700E3B7221","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d0120e03bdb2344cceefaf67889daf4776cad790","datavalue":{"value":"0953.11022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1808846$28F86E74-8A36-4255-9387-782FC4480FED","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f9f931c5c1629bd5c161e2b423472b718ad135db","datavalue":{"value":{"entity-type":"item","numeric-id":398930,"id":"Q398930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808846$4493DAA7-C5D5-4B0E-992A-41D7EF5E963B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"33122a93dfb64681be222c65bf841053fa198b88","datavalue":{"value":{"entity-type":"item","numeric-id":165874,"id":"Q165874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808846$7CFDCBF0-6492-40B0-AE61-72733B3300B4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"24ed60e311a3dce35e332152ceed7e3958c9282f","datavalue":{"value":{"time":"+2000-02-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1808846$4BFE52A2-6C58-4FBE-8CA1-61435B5FC8ED","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9566395726f221f074c75ea11a75a11c7796fff5","datavalue":{"value":"The subject of this paper concerns bounds for the bilinear complexity \\(\\mu_n(q)\\) of multiplication in the finite field \\(\\mathbb F_{q^n}\\) viewed as an \\({\\mathbb F_q}\\)-algebra. An essential tool is \\textit{D. V. Chudnovsky} and \\textit{G. V. Chudnovsky}'s approach to the construction of fast bilinear multiplication algorithms via algebraic curves [J. Complexity 4, 285-316 (1988; Zbl 0668.68040)] (see also \\textit{I. E. Shparlinski, M. A. Tsfasman} and \\textit{S. G. Vladut} [Coding theory and algebraic geometry, Proc. Int. Workshop, Luminy/Fr. 1991, Lect. Notes Math. 1518, 145-169 (1992; Zbl 0805.14028)]).    It is known that \\(\\mu_n(q)\\geq 2n-1\\) with equality holding if and only if \\(q\\geq 2n-2\\) [see \\textit{H. F. de Groote}, SIAM J. Comput. 12, 101-117 (1983; Zbl 0513.68039)]. The optimal algorithms realizing the lower bound \\(2n-1\\) all can be viewed as certain algorithms on the projective line over \\(\\mathbb F_q\\); [cf. \\textit{S. Winograd}, Theor. Comput. Sci. 8, 359-377 (1979; Zbl 0404.12016) and \\textit{D. V.} and \\textit{G. V. Chudnovsky}, Proc. Natl. Acad. Sci. USA 84, 1739-1743 (1987; Zbl 0644.68066)]. The aforementioned optimal algorithms were generalized to (projective, geometrically irreducible, non-singular algebraic) curves satisfying certain arithmetical conditions; cf. \\textit{D. V.} and \\textit{G. V. Chudnovsky} [Zbl 0668.68040], \\textit{I. E. Shparlinski} et al. [Zbl 0805.14028]. Using a slightly modified version of these algorithms on elliptic curves \\textit{M. A. Shokrollahi} [SIAM J. Comput. 21, 1193-1198 (1992; Zbl 0778.11075)] noticed that \\(\\mu_n(q)=2n\\) provided that \\(q/2+1<n<N_q(1)/2\\), where \\(N_q(1)\\) is the number of \\(\\mathbb F_q\\)-rational points of an optimal elliptic curve over \\(\\mathbb F_q\\).    The main results of this paper are:    (I) A generalization of Shokrollahi's result, namely: \\(\\mu_q(n)\\leq 2n+g-1\\) whenever there exists a curve of genus \\(g\\) such that (a) it has at least one point of degree \\(n\\), and (b) it has more than \\((2n+2g-2)\\) \\(\\mathbb F_q\\)-rational points;    (II) The construction of infinitely many curves satisfying both the hypothesis (a) and (b) provided that \\(q\\) is a square, \\(q\\geq 9\\), and \\(n>q/2+1\\). In addition, \\(\\mathbb F_q\\)-maximal curves do satisfy (a) above as their genera \\(g\\) fulfill \\(g\\leq (\\sqrt{q}-1)^2/4\\) or \\(g=\\sqrt{q}(\\sqrt{q}-1)/2\\) [\\textit{R. Fuhrmann} and \\textit{F. Torres}, Manuscr. Math. 89, 103-106 (1996; Zbl 0857.11032)]. Therefore \\(2n\\leq \\mu_q(n)\\leq 2n+g-1\\) whenever \\(q/2+1<n<(q+3)/2+(\\sqrt{q}-1)g\\) with \\(g\\) being the genus of a \\(\\mathbb F_q\\)-maximal curve. The proof of (I) uses the same method as in \\textit{D. V.} and \\textit{G. V. Chudnovsky}'s paper [Zbl 0668.68040]; (II) is proved by using a \\textit{Garcia-Stichtenoth} optimal tower [\\textit{G. Garcia} and \\textit{H. Stichtenoth}, Invent. Math. 121, 211-222 (1995; Zbl 0822.11078)] as a building block. Finally, the author applies these results to show that for each \\(q\\), \\(\\mu_n(q)\\) is upper bounded by a linear function of \\(n\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1808846$61F8FD5A-20A4-4054-8CB1-0D4DDD2B4922","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0c196069a3cf79cf414495553bf74e2282e02cd5","datavalue":{"value":{"entity-type":"item","numeric-id":329182,"id":"Q329182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808846$3A65E9CE-3C1F-4850-8B1B-182B91CE2497","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ccf6cf9514426243b160a3a06e070c16a64dbff","datavalue":{"value":"11G20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1808846$F375A398-13A9-47DD-B99D-84E09D597003","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"db2b8853a52c7f02af86453b6ee74c018fc3284f","datavalue":{"value":"14H25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1808846$F5CA7E27-CEB8-449C-A3D7-D60F4A1592D0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4747e6c0e80921333bca7bba4a8a01df01249ece","datavalue":{"value":"1369827","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1808846$C5A49E65-F0B2-4F95-954D-12E005A94E1E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"242fde13fe99aebfb5ba91ea68a9a71e030b6bb3","datavalue":{"value":"bilinear complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1808846$671D18B9-D3D4-4BDE-A186-6506A246DD5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac07c7d6c5cdc2dbc4590f3ecbac0ebb59196bea","datavalue":{"value":"finite fields","type":"string"},"datatype":"string"},"type":"statement","id":"Q1808846$0D815FE7-BBE8-4F76-8067-804D1E6660D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bae2e32ca3e6f8db8e838bf659d6d1723d41386d","datavalue":{"value":"algebraic function fields","type":"string"},"datatype":"string"},"type":"statement","id":"Q1808846$949E26AB-643D-46C7-B6FB-6612B7A03D44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d516c22531720e4453e883202f4d4205efddf019","datavalue":{"value":"algebraic curves","type":"string"},"datatype":"string"},"type":"statement","id":"Q1808846$B37E00B4-1D21-4C32-B06F-B048708E0129","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":"Q1808846$C999E7ED-DAA2-47A7-918E-B2325D410143","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a7b44522eceb462141d1c957f4bd8bda740f6718","datavalue":{"value":"https://doi.org/10.1006/ffta.1999.0255","type":"string"},"datatype":"url"},"type":"statement","id":"Q1808846$AC187321-02A0-49A0-B568-D789CD473A1C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8a7134f9d197b5e6109b99e7b418773d16e082d2","datavalue":{"value":"W1998210995","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1808846$43FFB1D7-2CB7-4D35-BA93-7CBFA6C2BABF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a6077e2e54fd6a54fd3728489a248cfff870e3c","datavalue":{"value":{"entity-type":"item","numeric-id":4331740,"id":"Q4331740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808846$5041B8E4-A5A8-43F8-B976-1D4AA5048AEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b831b167903ef130df39c58f2e8054c1dcecd26c","datavalue":{"value":{"entity-type":"item","numeric-id":5903919,"id":"Q5903919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808846$D5BC9137-57B4-444C-9188-C90AAD299D62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8a454fd64168f558aae37864bc0a7199ddb22f8","datavalue":{"value":{"entity-type":"item","numeric-id":2556360,"id":"Q2556360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808846$34FBFE2C-607C-450A-B202-42D8FD2CEA6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2f1c1e654ab6068a45f319cdd15c0b173f725ca","datavalue":{"value":{"entity-type":"item","numeric-id":1910156,"id":"Q1910156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808846$50BA0B6A-52FB-42E8-B77E-E54B0885C96A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63cd33df58b889a1d52dd29efa8b537172deb749","datavalue":{"value":{"entity-type":"item","numeric-id":1895702,"id":"Q1895702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808846$5B8FD59E-3661-4C8C-9788-D94FC9552D9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09991387f3bcdafa5c54fa4db7b36b70f18aab93","datavalue":{"value":{"entity-type":"item","numeric-id":1171378,"id":"Q1171378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808846$BFC8C00C-C7FF-4CA9-8CB9-4B1BD3D32DE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c6fb55b76df95fef96653206098725cffd7ad47","datavalue":{"value":{"entity-type":"item","numeric-id":4027853,"id":"Q4027853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808846$71647FC9-39C2-4605-8713-143961C4343D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45046a8e3169cff85cca2406de3eb6585fbdca71","datavalue":{"value":{"entity-type":"item","numeric-id":4027646,"id":"Q4027646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808846$9C377F3F-DF3D-4318-AE4D-D99A0FAA949B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1114411dd5edb40fc6b539704403c2a071251e91","datavalue":{"value":{"entity-type":"item","numeric-id":685743,"id":"Q685743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808846$F7BD1F77-3A9C-4EA7-B0F7-659B2AD5F58B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8f7aac40c88ae4bfbbb058db128447c4fa2192e4","datavalue":{"value":{"entity-type":"item","numeric-id":5582828,"id":"Q5582828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1808846$16A3BA80-E7A9-4D78-9AD5-3C3569ED19AB","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":"Q1808846$ABA30151-5992-405A-AB29-316E9EE07E62","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2da5226b50e6e0f685942549ed396a2b0d7f90a0","datavalue":{"value":"10.1006/FFTA.1999.0255","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1808846$3FCB3A50-C714-43B7-8E84-F29E16494DE9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"14d4f1e4743eb46279fc427a275448df8405ae49","datavalue":{"value":{"entity-type":"item","numeric-id":4027646,"id":"Q4027646"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"66ea8759163f2bafd1cd6ef57b36253e8645f8bc","datavalue":{"value":{"amount":"+0.9328728914260864","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":"Q1808846$547AE055-F308-42E1-821B-D2337DDCE53E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31651a5afcdf04cbb894f03791b6b37333e034ed","datavalue":{"value":{"entity-type":"item","numeric-id":2506478,"id":"Q2506478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bd49e758585079fb905a4ff63bd3d737a678caf","datavalue":{"value":{"amount":"+0.8952688574790955","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":"Q1808846$62D8709F-985D-43F4-AAEC-8BEBCFCDE3CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a959e89f888b78bc44b5a7bfd2ab9458b98ff7c","datavalue":{"value":{"entity-type":"item","numeric-id":818142,"id":"Q818142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5461a63a75f02ecbe7c9fc634aaf45f70c4f2037","datavalue":{"value":{"amount":"+0.8923812508583069","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":"Q1808846$0B3B149E-92C8-4C04-BFFF-0A0B2FFB0964","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0caa2d259f577ec0d3951be8a429f89b3b05279","datavalue":{"value":{"entity-type":"item","numeric-id":4027853,"id":"Q4027853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c2415769a39a267fc22c2aa953a667adf1a593ee","datavalue":{"value":{"amount":"+0.8892737030982971","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":"Q1808846$B601A880-FE00-4F9A-96AE-03645535EB25","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1808846","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1808846"}}}}}