{"entities":{"Q2445320":{"pageid":2456063,"ns":120,"title":"Item:Q2445320","lastrevid":57923886,"modified":"2026-04-03T02:44:56Z","type":"item","id":"Q2445320","labels":{"en":{"language":"en","value":"Counting points on hyperelliptic curves in average polynomial time"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6284348"}},"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":"Q2445320$20B8751B-74A2-4945-A060-2B7DCBFD705A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8e9c125b9ef85ebba6d34afacd1319dc50f06897","datavalue":{"value":{"text":"Counting points on hyperelliptic curves in average polynomial time","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2445320$02C98A81-BADE-441C-BA5A-0C202B6F3134","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"85b0f8b51658316f2c2751a09cb83a56a5c457b8","datavalue":{"value":"1294.11104","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2445320$3A3B2230-D900-4BC6-841B-CAD7057B5C1E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b5c97ee9b80dd355e4c4190137d89950391c981e","datavalue":{"value":{"entity-type":"item","numeric-id":278188,"id":"Q278188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$06192003-2C27-491D-8CFD-E4F7A1212BDC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"553c7ad508f4615999d4ef926cfdf75d436f510c","datavalue":{"value":{"entity-type":"item","numeric-id":175062,"id":"Q175062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$317DB448-3B10-49BC-8917-98C191AEC109","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"af2bd9793596aefadb295689a4db5fbda4fe4920","datavalue":{"value":{"time":"+2014-04-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2445320$63B7D9DE-FAFE-4913-9968-BBE9D14079EA","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a7e8e8eac8c63ed252a974dbf50af454935b6ad0","datavalue":{"value":"https://arxiv.org/abs/1210.8239","type":"string"},"datatype":"url"},"type":"statement","id":"Q2445320$EB5DD9E3-B6FC-4363-A538-A03F1CA3C73C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6735dde42e600a50aef66038c888bfcf63783703","datavalue":{"value":"An hyperelliptic curve \\(X\\) of genus \\(g\\) and a rational Weierstrass point over a finite field \\(\\mathbb F_q\\), \\(q\\) odd, can be written as \\(y^2=Q(x)\\) where \\(Q\\in\\mathbb F_q\\) is monic, square-free and of degree \\(2g+1\\). The zeta function of \\(X\\) has the form  \\[  Z_X(T)=\\frac{P(T)}{(1-T)(1-qT)},  \\]  where \\(P\\in\\mathbb Z[T]\\) has degree \\(2g\\). An efficient algorithm for computing \\(P(T)\\), given \\(q\\), \\(g\\) and \\(Q\\), is useful for collecting data for the Birch-Swinnerton-Dyer conjecture and the Sato-Tate conjecture.  Known algorithms for computing the zeta function have a time complexity that is exponential in either \\(g\\) or in \\(\\log p\\). The author presents an algorithm that, for input \\(N\\geq 3\\), \\(g\\geq 1\\) and \\(Q\\in\\mathbb Z[x]\\) defining an hyperelliptic curve of genus \\(g\\), computes the sequence of zeta functions for \\(\\bar{X}_p\\), over \\(\\mathbb F_p\\), for all odd primes \\(p < N\\). The average time per prime is: \\(g^{8+\\epsilon}\\log^3 N\\log (\\|Q\\|N)\\), which is polynomial in the size of the input (here \\(\\|Q\\|\\) denotes the maximum of the absolute values of the coefficients of \\(Q\\)).  The starting point is \\textit{K. S. Kedlaya}'s algorithm [J. Ramanujan Math. Soc. 16, No. 4, 323--338 (2001; Zbl 1066.14024)]. The portion of this algorithm whose complexity is exponential in \\(\\log p\\) involves computing certain ``reduction matrices''. The main improvement comes from replacing these by matrices that do not depend on \\(p\\). Then the author adopts the accumulating remainder tree algorithm of Costa, Gerbicz and Harvey, replacing its linear polynomials with his new matrices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2445320$1826CD7A-B000-4C4C-8209-D69D382C2178","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ccf6cf9514426243b160a3a06e070c16a64dbff","datavalue":{"value":"11G20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2445320$F813BEB4-26E6-4709-A797-7E2142D818C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0e2417e055dac8201b2edbf4ce214140443124f6","datavalue":{"value":"11M38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2445320$A32D6C5B-5078-40C1-9EEE-8B27C120B2CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2445320$69DD6B19-AA9C-4C4C-8BCF-395CBA191645","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"99e50ca4d78779d992e178d20f0a06708e046829","datavalue":{"value":"6284348","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2445320$FC08AB04-1D0A-4B54-99E6-52581A233F4E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f958bde503706c7efa7f77a9578b1370ce58fff1","datavalue":{"value":"hyperelliptic curve","type":"string"},"datatype":"string"},"type":"statement","id":"Q2445320$488FF827-653E-407A-8CA4-152D816FF1B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a18043ce842406adf7d9e4c8f3cd17b240a5165a","datavalue":{"value":"zeta function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2445320$909924C0-56F2-4A8C-BE15-FD5B7C6F764F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53064f6609fb5177611c085d6f78e739c7e3f7f6","datavalue":{"value":"time complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2445320$EA1DB295-5B9F-47FB-8B4B-4FB14988F1D0","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":"Q2445320$E6D9408F-4921-426A-AF88-8204F82A25AC","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a8d0ebd0e31213424ad86bbfa17ea559df9eb22f","datavalue":{"value":"W2157531996","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2445320$F3C9627B-FC3E-4719-8E06-E62F8444D15D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"46ec51137de29793ec1a1c45e54d30b8f8fe718a","datavalue":{"value":{"entity-type":"item","numeric-id":5945287,"id":"Q5945287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$AAD21F94-34E8-4862-B337-631E7F4ED5DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d18f75416a6bf924d34a2f497c1133f7318adb3b","datavalue":{"value":{"entity-type":"item","numeric-id":3615926,"id":"Q3615926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$DCB51A0D-16D8-4E76-BB4E-79C644118630","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ff95cf9d4ceb86ce5090c97e97fbcd0a940d41b","datavalue":{"value":{"entity-type":"item","numeric-id":5432372,"id":"Q5432372"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$B964582B-58F2-4B89-A564-B44BB6FF83F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a91727adb09e3ae9f87cb2de87f8378136fc7485","datavalue":{"value":{"entity-type":"item","numeric-id":4265362,"id":"Q4265362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$A259CDB9-1856-4868-9DA2-281B8A9766D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f723c1fd00c5451ba17c56a8f1f7bac03a2ab891","datavalue":{"value":{"entity-type":"item","numeric-id":3189466,"id":"Q3189466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$E5B158B7-7BAC-4C24-AE7F-33BF01ACC99B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5c10a1b82c865e4ec0d76eda5a5a6265535843b","datavalue":{"value":{"entity-type":"item","numeric-id":3167318,"id":"Q3167318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$DB595DDB-C298-482D-848C-29F025FB0549","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"476260ab9cf869569e03b11cf065db4f3845c4a9","datavalue":{"value":{"entity-type":"item","numeric-id":4474194,"id":"Q4474194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$98F912E5-B7A0-4D70-9115-B684C021FFC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1888c35ac60df31da926e1e093c106cd01c28ef","datavalue":{"value":{"entity-type":"item","numeric-id":412199,"id":"Q412199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$DE75E876-E546-4B67-9110-A33814095E3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"faa9b83d8980512557270409bb030b74684a3e6c","datavalue":{"value":{"entity-type":"item","numeric-id":5439938,"id":"Q5439938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$6D4C7A23-9CC6-4D4C-9A8F-7BD1D7E29DC8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a23284f641b9ae2e993818df3a9038695c23ee1","datavalue":{"value":{"entity-type":"item","numeric-id":654037,"id":"Q654037"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$040FF0A4-C807-4407-B7A3-F98DADABED8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d1142a13dc568d66ea794032649036ee250e93d","datavalue":{"value":{"entity-type":"item","numeric-id":4542306,"id":"Q4542306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$EF8D5C74-246F-4B87-A33D-0F6D2B4BC99E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e38643b7848496dbc401f4e8b91d09c89d16ba0","datavalue":{"value":{"entity-type":"item","numeric-id":5387607,"id":"Q5387607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$C735A4C3-4B97-4BE2-941A-EE52DFE34B2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fd187d18b4637eb4c9b0d90f0fb3719b25c4cab","datavalue":{"value":{"entity-type":"item","numeric-id":5325561,"id":"Q5325561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$9782AEDC-829B-4D7B-9509-88CA24A5CD38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce362a2dde0e6ad2e9f35896055b278411749412","datavalue":{"value":{"entity-type":"item","numeric-id":626953,"id":"Q626953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$ACFD80A2-A62F-4509-AA77-BE46E18DD641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"042e90bf450ba074850445841726e82361b4c8a9","datavalue":{"value":{"entity-type":"item","numeric-id":2528865,"id":"Q2528865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$D03B3C1C-E534-4EDC-BC65-33A9D8AF6E31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$32661F2F-85EC-4D58-98FF-E0FEC44F5547","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"22346abb731f8de1e632b5eb496488f6abe6adf3","datavalue":{"value":{"entity-type":"item","numeric-id":5202279,"id":"Q5202279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$2215CF4F-0C1E-4544-ADF5-CC2FC1475B77","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbbf3981c0eebe6ce5f31f55e4084ae628b3ad39","datavalue":{"value":{"entity-type":"item","numeric-id":3701545,"id":"Q3701545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$6DD8C09C-A2F0-43C3-A3CB-7A6A7A81C289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f1746c0002a982167f6b872896509d0ce78aa9e","datavalue":{"value":{"entity-type":"item","numeric-id":2536323,"id":"Q2536323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$095A4F6C-F99C-4C9D-AFD5-59CDEA8658ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"41375a54075658edb0bdaf6d0bf7f2f136a850ee","datavalue":{"value":{"entity-type":"item","numeric-id":5389449,"id":"Q5389449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$5956823E-A3AD-4F9F-8D77-07287BF54525","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0543f1e8c81032cff0b481c190929fef1b006bd","datavalue":{"value":{"entity-type":"item","numeric-id":4406533,"id":"Q4406533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$ED809840-9B48-495B-9F75-DC815752CDC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"731189e275a6b16e4ce2ada55d4b41186a01e79c","datavalue":{"value":{"entity-type":"item","numeric-id":3615933,"id":"Q3615933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2445320$5654D0A0-1852-4AE3-B0F9-B538AF8E2691","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3daa1d178e5d2bd601cb28338e44b6ec380a7348","datavalue":{"value":"10.4007/ANNALS.2014.179.2.7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2445320$E2C9AB42-6F0A-4897-8D33-AD079C9DD185","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7add8bb23da0e18d0a1039651264061d7b2173e6","datavalue":{"value":{"entity-type":"item","numeric-id":2420634,"id":"Q2420634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3166dc3a4ee442bbaea249d931e42028dd3f0ea","datavalue":{"value":{"amount":"+0.8781794905662537","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":"Q2445320$3F9ED194-B470-4E64-8A9C-464AB900125E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54661efcba48654b411964475a78bfb87e866f3d","datavalue":{"value":{"entity-type":"item","numeric-id":3085111,"id":"Q3085111"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14a607beb3eaada0f9e2fb9b94141f60da6c5dee","datavalue":{"value":{"amount":"+0.869528591632843","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":"Q2445320$B9B5DD66-1206-43D6-B170-FBC8A04F552C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"287f401d26737838e06e07e42ff8818507f02c5b","datavalue":{"value":{"entity-type":"item","numeric-id":937277,"id":"Q937277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f63cb626a08e7dd320dcf9a65e182824c2481c83","datavalue":{"value":{"amount":"+0.8681631684303284","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":"Q2445320$097EB429-B68C-465D-AE1D-787A4EE747DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2064539d4b52c625202c8ad48d8b2b12eba150ee","datavalue":{"value":{"entity-type":"item","numeric-id":3091945,"id":"Q3091945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ba546fd3d0b732405868c7904e314857f9b4404","datavalue":{"value":{"amount":"+0.8594944477081299","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":"Q2445320$4BFF8595-9F14-46BC-B74F-EEDE025F03FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b504e7424646fd720b553d0d933fe977c95a49fd","datavalue":{"value":{"entity-type":"item","numeric-id":2878840,"id":"Q2878840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21e084f9018bb7df6c56cb40b37b529d9ff32ca3","datavalue":{"value":{"amount":"+0.8590192198753357","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":"Q2445320$BC0667DE-35F1-42AB-8163-1AD1BF9728F0","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2445320","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2445320"}}}}}