{"entities":{"Q1408372":{"pageid":1419112,"ns":120,"title":"Item:Q1408372","lastrevid":67377249,"modified":"2026-04-12T17:13:13Z","type":"item","id":"Q1408372","labels":{"en":{"language":"en","value":"Computing discrete logarithms with the parallelized kangaroo method."}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1981501"}},"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":"Q1408372$BE7B2988-8B16-4DA0-BF46-67D1312098CB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d7ea76e8f90d37f072b860fe92375d757c138ede","datavalue":{"value":{"text":"Computing discrete logarithms with the parallelized kangaroo method.","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1408372$3A0D4ACE-702F-41B8-967C-F9EBAF76335E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7ca94f260bc0ab48bca5cf8bc8cd9468f440578f","datavalue":{"value":"1044.11107","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408372$715B51FF-8587-464F-9672-7BF4D25FC7A7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c548c2581a31092c686ceae246dd1c8ea71ce11f","datavalue":{"value":"10.1016/S0166-218X(02)00590-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408372$C3A25080-7BF7-4205-8E24-4F0C61908071","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce248613f92a3e6b8e8d637fc8e54f4491fc3d92","datavalue":{"value":{"entity-type":"item","numeric-id":1300625,"id":"Q1300625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408372$3F458DBD-7919-4685-9327-3D51E3CC6C69","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408372$F52BBCFD-922F-4818-92A6-7FFC10FB3B2D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"bdb952d10b49f391b9728d4aaf2d3506fc5000a3","datavalue":{"value":{"time":"+2003-09-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1408372$6F4D2B3C-8F43-4BB2-879A-2350BCBBD4B3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"65ca98f3d5308cf8597b8aa41896fc24081df264","datavalue":{"value":"Some methods to solve the Discrete Logarithm Problem (DLP) take advantage of some specific property of the underlying cyclic group (the archetype being the Index-Calculus method which provides a subexponential-time algorithm to attack DLP on the multiplicative group of a finite field, group used in cryptographic applications) while others are generic (valid for any cyclic group) like the BSGS of Shanks, the rho and the kangaroo methods.   The kangaroo method due to \\textit{J. M. Pollard} [Math. Comput. 32, 918--924 (1978; Zbl 0382.10001)] is so called because Pollard suggested the parallelism with the catch of a wild kangaroo using a tame one (the method is also known as \\textit{lambda} method, because the paths of the two kangaroos look like that Greek letter). The running time of the kangaroo method is \\(O(\\sqrt N)\\), with \\(N\\) the order of the group and it requires little storage.   As \\textit{P. C. van Oorschot} an \\textit{M. J. Wiener} pointed out [J. Cryptology 12, 1--28 (1999; Zbl 0992.94028)], the method can be parallelized, using \\(n\\) instead of two kangaroos, the parallelized version providing a linear speed up. The present paper discusses in detail some theoretical and practical aspect of this parallelization.   After a description of the kangaroo method and the two parallelized versions of van Oorschot-Wiener and Pollard the paper focus in the study of the appropriate choice of parameters and the analysis of the running time. Section 8. `Experimental results' shows the performance of the studied methods in a concrete case: the group of rational points of the elliptic curve \\(y^2=x^3+5x+19\\) over the prime field \\(F_p\\), \\(p=10^{15}+37\\). The paper finishes (section 9) with a discussion of applications and open problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1408372$46D5343D-8EA1-4763-9ADA-7E5470DCB220","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408372$E9C26D97-4E6D-4357-9213-41BBAF3BB354","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408372$646D6FB4-9380-4EE6-8E66-FB9D1A7FC9DE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c4bb7ffa3fa747903163a0aca54ea2503406bfb9","datavalue":{"value":"1981501","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1408372$99881090-2BA3-4C86-85DE-6E706633C6CC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"76c3b676e35ac52749b3f6c477b01691c4b0dc96","datavalue":{"value":"discrete logarithm problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1408372$CF9E1252-A6EE-424F-9E22-4ECF4E426DD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"57effeae943b3864235217a7c75f43b74fd64c88","datavalue":{"value":"kangaroo method","type":"string"},"datatype":"string"},"type":"statement","id":"Q1408372$784C7309-E169-4140-BC95-1FB18A85D116","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e4adb18bcac430f0482b7bf62c08c92b29c5f7df","datavalue":{"value":"parallelization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1408372$008DCA8F-8506-4DF1-AF8A-8369B26D27AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f3d4c4f0402aa58af4ddf1e2cea9445dfba8f84","datavalue":{"value":"running time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1408372$41DB99A8-3B22-4FC3-ACFE-65E52379C65E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8892955fafe16ba1bddb104e5d82ec8889d70fd9","datavalue":{"value":{"entity-type":"item","numeric-id":1313210,"id":"Q1313210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408372$65367DCA-B2E9-4DF6-AEB2-AAF1405531F4","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"15fbe2014501734f4e2ae251748396451dc6e563","datavalue":{"value":{"entity-type":"item","numeric-id":13274,"id":"Q13274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408372$6628C9BF-8C33-4CFC-A33F-5AC058E428CC","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":"Q1408372$28E474BC-8506-4377-A277-74EBF2BF1434","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c5c1aa602e2ab6867eb09c994970bc604aacfee","datavalue":{"value":{"entity-type":"item","numeric-id":4718481,"id":"Q4718481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408372$CFC7CE0D-A87F-4D9A-8A4F-6EA35A9B679C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"597ee61d307f0a24a311b4f4235d308587e8cc84","datavalue":{"value":{"entity-type":"item","numeric-id":4161380,"id":"Q4161380"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408372$C1107FC2-AFBE-4A2F-90E7-068345A883FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd00b759df72d688c445e57f25cc1faf3ed88d52","datavalue":{"value":{"entity-type":"item","numeric-id":1590361,"id":"Q1590361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408372$454402F1-C7DA-40D3-8235-AC6DA3E237C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e3927d2784e3bfbe1afa6aaeb0d7041e8bc59f3","datavalue":{"value":{"entity-type":"item","numeric-id":2781226,"id":"Q2781226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408372$A6F0413C-1AA9-4EC8-907D-6FAF738D58CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"356899f9ca42e43b362a67e83a96f7ce142d24ff","datavalue":{"value":{"entity-type":"item","numeric-id":2759107,"id":"Q2759107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408372$75CFCCCA-3C3B-44FE-86D0-F012203AD6ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8fd0a5e781bd4af68bfd632ba19172cb519305f","datavalue":{"value":{"entity-type":"item","numeric-id":2701566,"id":"Q2701566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408372$CB91C14B-FD1C-444A-85F8-A40D341D7F66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"062725fa11333a6a4e3a9aa8bf0926590782491f","datavalue":{"value":{"entity-type":"item","numeric-id":1284011,"id":"Q1284011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1408372$F0D5C4EB-0418-4CE8-B7F8-642DCDAEA11E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37e91f11a641a87e0adc20a57da6d70a024ff27b","datavalue":{"value":{"entity-type":"item","numeric-id":2765016,"id":"Q2765016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72735c299455d3d92fe9a1400416cd10dbe6219f","datavalue":{"value":{"amount":"+0.8338346","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1408372$023809DA-2C48-4ED5-BCAA-06F3CA76B290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26b633eeb09b607e86c0e6ae4f733c65d8f07b98","datavalue":{"value":{"entity-type":"item","numeric-id":2781226,"id":"Q2781226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e3e4761dc826b845519c0d0ab1b44f91014d6af7","datavalue":{"value":{"amount":"+0.8175175","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1408372$72EA1B95-3DC3-4520-9175-97320A1E00CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b532b6e2b0e5a91f429f5e53f3bac3243e5da6db","datavalue":{"value":{"entity-type":"item","numeric-id":1590361,"id":"Q1590361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ad1b3c53ffe250897ee08f5df07d3dd03e0932e9","datavalue":{"value":{"amount":"+0.8029115","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1408372$FD64FA8C-3646-4B59-B8D2-3192ACC1E92E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e4505da8de9253b102a8141635e2c04bf5a539ac","datavalue":{"value":{"entity-type":"item","numeric-id":3840196,"id":"Q3840196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d305d0bbcc4c1d74d773a2dc2e713511d5547122","datavalue":{"value":{"amount":"+0.80202425","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1408372$8DBA01FF-5A60-4A8C-8E35-2E4745C9E0B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bce22b1ccea6f48270f6ef1a1a71ab95f84934ef","datavalue":{"value":{"entity-type":"item","numeric-id":3615927,"id":"Q3615927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c02573094bfbd59ab62b5ca184a2eb624fb6cf6f","datavalue":{"value":{"amount":"+0.80093956","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1408372$90690482-2E28-4438-A7FE-B14B4313D360","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e77f27d1476b75b8dcaeef6ee11b7cf4f775dc4","datavalue":{"value":{"entity-type":"item","numeric-id":4675703,"id":"Q4675703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99d15a430b2aafd80cfb4ee598537110e5ae74ed","datavalue":{"value":{"amount":"+0.7994017","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1408372$B107D611-4916-4615-BD20-970D6DD4AEC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24198f0823af081f80ecf8acc794864aae3a0350","datavalue":{"value":{"entity-type":"item","numeric-id":3381832,"id":"Q3381832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8455acecb7359d746323bdf3d59202adf7cf773f","datavalue":{"value":{"amount":"+0.7967333","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1408372$5749C2F7-165A-4C5B-B1DE-E5454CCBE69A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbc83cb77eb44be196fa5b638a493bed9cf648a6","datavalue":{"value":{"entity-type":"item","numeric-id":3562909,"id":"Q3562909"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"765bcadcdd8b4e3dc3351e5781b462f0227d24aa","datavalue":{"value":{"amount":"+0.79602444","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1408372$87E41ADE-FAF2-4512-ADBF-B4408E0F0CA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ceb709465ea5891dd8ca91056cb1c257accbc7c1","datavalue":{"value":{"entity-type":"item","numeric-id":2701566,"id":"Q2701566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"144a1c931f1141c27eb2a1d603c570314ac791cf","datavalue":{"value":{"amount":"+0.792832","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1408372$8548FFA3-576C-4FF0-9DD9-6B1BA8A97F47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30e87cf87b72f050882acd84aca4750434e43838","datavalue":{"value":{"entity-type":"item","numeric-id":1738058,"id":"Q1738058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7f69ca60b34c33ef266ddbb877f7b2668cf8501","datavalue":{"value":{"amount":"+0.7878272","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1408372$7FDD9A19-4EC4-4522-BCC0-CB69C63437F2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computing discrete logarithms with the parallelized kangaroo method.","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computing_discrete_logarithms_with_the_parallelized_kangaroo_method."}}}}}