{"entities":{"Q1909875":{"pageid":1920617,"ns":120,"title":"Item:Q1909875","lastrevid":73061334,"modified":"2026-04-14T10:06:08Z","type":"item","id":"Q1909875","labels":{"en":{"language":"en","value":"Counting points on elliptic curves over finite fields"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 858026"}},"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":"Q1909875$B7C3929F-878B-41AB-A49A-3B5179AA8819","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"96f7d1fdcc6cc98583399bddc58f612a0b0f40f6","datavalue":{"value":{"text":"Counting points on elliptic curves over finite fields","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1909875$93CF8FA0-2DE6-4AF2-8706-2C26FC10C803","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"95c53d535caadd6f1a80546db3ebd60ac194e9db","datavalue":{"value":"0852.11073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1909875$F59B41CA-F093-4E0F-8FCB-E253735A5814","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"2af5fe3b27a04082f1eae9cf17090e68be06cc07","datavalue":{"value":{"entity-type":"item","numeric-id":194678,"id":"Q194678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$23E7FB7F-EE88-48A7-A290-C41462A02A44","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"08830651a950d2a53916831025f618726bf5dd9b","datavalue":{"value":{"time":"+1996-03-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1909875$99E71722-0446-45BF-8F8F-F3B6B040B2A3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"155168244dc8e6b43cb8575a9d0d5162da2e9517","datavalue":{"value":"http://www.numdam.org/item?id=JTNB_1995__7_1_219_0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1909875$03277990-30F5-49DD-8A31-5110DBF798C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"5406cb4ebb29d4d48b1297e4706c82d3c320699a","datavalue":{"value":"https://eudml.org/doc/93624","type":"string"},"datatype":"url"},"type":"statement","id":"Q1909875$4E15F31F-4FA8-4317-9D00-E5A2E0CF6802","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"967ac89ec80c98392e5397bbc6d32c628c1c1c6a","datavalue":{"value":"http://www.emis.de/journals/JTNB/1995-1/jtnb7-1.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1909875$309F124E-2AF6-4FB5-B58E-B16EE89DD70F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"baef3b50366b3c028331031b9f77fc0ead6bcdb7","datavalue":{"value":"The author reports on algorithms for counting the number of points on an elliptic curve over a finite field. The first one works well when the finite field is not too large and is based on Shank's baby-step-giant-step strategy [\\textit{D. Shanks}, 1969 Number Theory Institute, Proc. Symp. Pure Math. 20, 415-440 (1971; Zbl 0223.12006)]. Then he discusses an improvement due to Mestre which avoids some group theoretical problems in this algorithm; this has been implemented in the computer algebra package PARI [\\textit{H. Cohen}, A course in computational number theory, Grad. Texts Math. 138 (1993; Zbl 0786.11071), Alg. 7.4.12; \\textit{C. Batut}, \\textit{D. Bernardini}, \\textit{H. Cohen} and \\textit{M. Olivier}, User's guide to PARI-GP, version 1.30, Bordeaux (1990)]. The second algorithm is efficient when the endomorphism ring of the elliptic curve is known, and it is based on a reduction algorithm for lattices in \\(\\mathbb{R}^2\\). A related algorithm due to Cornacchia and Lenstra's proof of its correctness are also discussed. Finally the last algorithm is a deterministic one which runs in polynomial time and is based on calculations with torsion points. Practical improvements due to Atkin and Elkies are also presented. The latter methods can be extended to large finite fields of small characteristics, and its origin comes from cryptography [\\textit{A. J. Menezes}, \\textit{S. A. Vanstone} and \\textit{R. J. Zuccherato}, Math. Comput. 60, 407-420 (1993; Zbl 0809.14045)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1909875$6D8EB7B8-3B7F-4C03-BECD-871FF4719CE9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1909875$8643F644-BFB9-4F38-904F-E51560FF6C68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ccf6cf9514426243b160a3a06e070c16a64dbff","datavalue":{"value":"11G20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1909875$F0B5E5E2-5976-4F54-88B4-73C2085A72C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"216939729202fc4b9c96cf3f62d6f618570d6e85","datavalue":{"value":"14Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1909875$71C7E952-CA5D-4618-93DE-DFFD773D0791","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f00aec7b2c940e365c27808f50e4aeed90366677","datavalue":{"value":"14H52","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1909875$367F14AA-E633-44E9-B5F8-7EAD0FE2EC64","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4be130bb9a668f58232fadb764ad2e970c6cc510","datavalue":{"value":"858026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1909875$6C236FB5-B03D-4299-BEB6-B59E2F8AD76C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f22dc04e3f9814c23bf4de80653d575eccfbc490","datavalue":{"value":"elliptic curve over a finite field","type":"string"},"datatype":"string"},"type":"statement","id":"Q1909875$F914A168-0295-4E2C-895C-BC4176CF725A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d855c12fc54ce77b4d0ad178d8b916d66d39c7f","datavalue":{"value":"reduction algorithm for lattices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1909875$52BBA797-D525-4725-B252-E50964C640E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b7220fdfca49282078e8d5196ee3f192b4e194a","datavalue":{"value":"torsion points","type":"string"},"datatype":"string"},"type":"statement","id":"Q1909875$E9925955-598D-44F3-870B-8F635C67667D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d99e36eceb4a14dfd4891d4d94c74baa6172d69d","datavalue":{"value":{"entity-type":"item","numeric-id":199207,"id":"Q199207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$71E4828A-08DD-4410-A07C-33DF48EE2AFE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4b5b0420ac0f1a664e2a2c91677beb74b5cc782c","datavalue":{"value":{"entity-type":"item","numeric-id":374054,"id":"Q374054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$BF14AD92-95B0-410E-BF67-A032A5A1CA21","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"5199c731888cb3ba10630bedfbd9575640bb4daa","datavalue":{"value":{"entity-type":"item","numeric-id":13434,"id":"Q13434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$21F07D6C-B01A-4552-AAC8-2D36699B9A18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1463","hash":"45631fadf4ff832c5caf7fe397ed08b98f50f15b","datavalue":{"value":{"entity-type":"item","numeric-id":18970,"id":"Q18970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$F301778D-7A79-4415-9909-BE179D2496A3","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":"Q1909875$2A4C278A-BBF5-4136-ACF7-90F7E871B342","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cbad3219a4b144db554496c8fa7281dfd07cf4cf","datavalue":{"value":"W2037816851","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1909875$48C7AB68-33C2-485B-8E62-5E8159346ACA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"021141ad7aff596d514b0b75000803eaee47d358","datavalue":{"value":{"entity-type":"item","numeric-id":3137447,"id":"Q3137447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$8D19F47F-584E-40E0-A289-DCF31617C7CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b7d03acfe694d55b5bfb81a8721b654f11fafd6","datavalue":{"value":{"entity-type":"item","numeric-id":3139838,"id":"Q3139838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$01ADE746-929A-472C-AA4B-38010141413C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"627fe5e4a05209954e5c426b92442db4661fb9fd","datavalue":{"value":{"entity-type":"item","numeric-id":4847913,"id":"Q4847913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$B176F170-D8AC-4EF0-B534-400B8D1E50E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83f629c180f6436ab6ea9a75b06b545548804bab","datavalue":{"value":{"entity-type":"item","numeric-id":4143433,"id":"Q4143433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$A4C18EEF-AAA6-4543-8283-96201BA737AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eaf3f32825b8a3612582001fdfdbc36e9651fc47","datavalue":{"value":{"entity-type":"item","numeric-id":4075566,"id":"Q4075566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$27F90672-8DD1-4565-BF0C-71164ABAE61E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bbbdbe36b69090cd03bb2dfa77ec91a1f3aee0f","datavalue":{"value":{"entity-type":"item","numeric-id":4847916,"id":"Q4847916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$21AC1C5D-68F4-435B-A15B-1BD9B6BA94CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"021e3803bf643abc7d55ac0d8738502d6fc6b853","datavalue":{"value":{"entity-type":"item","numeric-id":4204265,"id":"Q4204265"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$DBF9E88D-01F5-4084-83D3-FCF139F8036C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ad73d21b4f5a7b4229517397889ad8d14e20c7d","datavalue":{"value":{"entity-type":"item","numeric-id":4293980,"id":"Q4293980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$52C5A86D-B008-4088-9D34-38B98B7C520B","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":"Q1909875$FBB1CF86-2FA8-45F5-815B-7E992DF66F89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a684d2d985ea55b5741184a846412f2085599101","datavalue":{"value":{"entity-type":"item","numeric-id":5628224,"id":"Q5628224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$B3AB1FFA-EFD0-4AE7-8ACF-B14BB69ABB35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23284f6aa1f5a0314ad839b56b9de3ad21fa0de6","datavalue":{"value":{"entity-type":"item","numeric-id":4063214,"id":"Q4063214"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$6694B50E-27BC-4F3F-B182-975604E85D83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb380c40c10a7d9d6dec3becc8293ee7708df6a0","datavalue":{"value":{"entity-type":"item","numeric-id":3710637,"id":"Q3710637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1909875$E689591D-2932-4F94-B483-44C596F795AA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5e0bab6af2d82e7fa083610bf77ce102d9778333","datavalue":{"value":"10.5802/JTNB.142","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1909875$BDC42477-1BB9-4F38-AE49-B308D7074C6D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8322f0a16679ba7e7b78cfb71a29affee471ae9","datavalue":{"value":{"entity-type":"item","numeric-id":4237387,"id":"Q4237387"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94b86942e0103492c58b0b1c49051e17c7c4b704","datavalue":{"value":{"amount":"+0.9087541699409484","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":"Q1909875$956165B0-5328-4524-BED2-D6637E93A32D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4662ac632df75a7b246352b4666f65365d736b4","datavalue":{"value":{"entity-type":"item","numeric-id":4293980,"id":"Q4293980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07885f19acbb857a8a323ed7e01ebba5e9ab5786","datavalue":{"value":{"amount":"+0.902439534664154","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":"Q1909875$915654C6-A495-4785-A61F-2E2F8444C807","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4c90ceddbb80910052c9c4999dcdc970b6c107ab","datavalue":{"value":{"entity-type":"item","numeric-id":3169301,"id":"Q3169301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5254c11aba3633bc5dd9d0adea2c42de49816a6","datavalue":{"value":{"amount":"+0.8827614784240723","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":"Q1909875$BA5F9331-E188-4910-A248-B079E9A0A5D8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Counting points on elliptic curves over finite fields","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Counting_points_on_elliptic_curves_over_finite_fields"}}}}}