{"entities":{"Q411043":{"pageid":412810,"ns":120,"title":"Item:Q411043","lastrevid":61678911,"modified":"2026-04-11T00:55:00Z","type":"item","id":"Q411043","labels":{"en":{"language":"en","value":"An efficient collision detection method for computing discrete logarithms with Pollard's rho"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6021724"}},"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":"Q411043$7B701129-2128-4B88-9FE0-176A4133B929","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e94c549e3895d19b5491536093062a6ab1657b94","datavalue":{"value":{"text":"An efficient collision detection method for computing discrete logarithms with Pollard's rho","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q411043$0019F5F4-441A-47C1-9A2F-E9024132B18E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f3f1976cf99d87a56f662e9f408973a461a32d30","datavalue":{"value":"1235.65161","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q411043$F2338C5B-A735-4805-A556-C647F9B717DA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b197c78e0383b746f17aef1dea4dc210414ecaba","datavalue":{"value":"10.1155/2012/635909","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q411043$7C9C7BDD-F195-4EC1-8E1B-A1C653D13F7B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"914a45fe88ea62048334dce8cc4b2731467c3d32","datavalue":{"value":{"entity-type":"item","numeric-id":411042,"id":"Q411042"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$9E87432E-9AEB-4021-8D59-86F76202C21D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d2d6bbec9ef927b9ae29100c6b1fbfb84b212886","datavalue":{"value":{"entity-type":"item","numeric-id":265401,"id":"Q265401"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$1275571F-F821-4255-949B-7DA9D11F056D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"bb299feb2b87699ac8beef494c52fd2765eaf609","datavalue":{"value":{"entity-type":"item","numeric-id":118601,"id":"Q118601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$67389D39-3EF0-44F1-A6DF-D0FF09F0B6C5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"15742c770d0bc70f7b6d226092ab905ce008dd4a","datavalue":{"value":{"time":"+2012-04-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q411043$9E244320-0A2E-4977-B5A7-173F20399D40","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"97c36304fabef6532e3129e82374ba50efc9ccab","datavalue":{"value":"Summary: Pollard's rho method and its parallelized variant are at present known as the best generic algorithms for computing discrete logarithms. However, when we compute discrete logarithms in cyclic groups of large orders using Pollard's rho method, collision detection is always a high time and space consumer. In this paper, we present a new efficient collision detection algorithm for Pollard's rho method. The new algorithm is more efficient than the previous distinguished point method and can be easily adapted to other applications. However, the new algorithm does not work with the parallelized rho method, but it can be parallelized with Pollard's lambda method. Besides the theoretical analysis, we also compare the performances of the new algorithm with the distinguished point method in experiments with elliptic curve groups. The experiments show that the new algorithm can reduce the expected number of iterations before reaching a match from \\(1.309 \\sqrt{|G|}\\) to \\(1.295 \\sqrt{|G|}\\) under the same space requirements for the single rho method.","type":"string"},"datatype":"string"},"type":"statement","id":"Q411043$9B4B8CFD-AB1D-41AB-9AF8-56879EFBE070","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8a7edc01538ef78e7e423d9c49f622de0faa5a14","datavalue":{"value":"65Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q411043$EB661C89-9D5B-4F61-94C2-1B51816C7E64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f96720fe29e309c34c82deec20bd95823bb71652","datavalue":{"value":"20-04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q411043$E0AAAD47-4909-4C30-B75F-0BA5BF531EB8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"685743cd7b3539f4e3580cf64fd79d74c9f3013a","datavalue":{"value":"6021724","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q411043$5ABE4923-F20E-43A8-AC9E-0FE748F665AA","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":"Q411043$A2022D92-EE95-48E6-B05E-E8357E4B6BD3","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"5d94ad79f5b3f500c85242049a9ef624d6c607cc","datavalue":{"value":"Q58906288","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q411043$389AD665-CC70-4A40-A89E-07165AA4E654","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aa0b86f23c65c6b2b3fe74001812815fb9a7e500","datavalue":{"value":"https://doi.org/10.1155/2012/635909","type":"string"},"datatype":"url"},"type":"statement","id":"Q411043$43CE7819-7C21-4182-8BCB-5245CF1A8657","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b28d3fc262d5cec23fb076c8c349fff06d691250","datavalue":{"value":"W1968515799","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q411043$3BE72739-B789-42EC-A103-58AFC3F71A98","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e40651885e589ae16736b2ed26430168a8207418","datavalue":{"value":{"entity-type":"item","numeric-id":3875826,"id":"Q3875826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$A43E7576-1095-4D76-BF6D-AF0685AF3B55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc4c2f534223ec34c41fed80e42cbca489663773","datavalue":{"value":{"entity-type":"item","numeric-id":3689092,"id":"Q3689092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$0AAE8C43-2377-44B8-AF64-FA9BA3F213A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9555fd6e13661952c64bc2d93f0ff961be1bbd46","datavalue":{"value":{"entity-type":"item","numeric-id":1180508,"id":"Q1180508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$664C191A-9554-4607-90B9-0B4B13CBC368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c491ff117d59f1c15b50f5dd47e96a8d728de820","datavalue":{"value":{"entity-type":"item","numeric-id":3760431,"id":"Q3760431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$F24E7173-3EFD-4B27-A1A0-E415FF0806F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"152515035e7edb88a9510f93a6c48f5604d59ef7","datavalue":{"value":{"entity-type":"item","numeric-id":3718617,"id":"Q3718617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$B2750F0A-472D-4A87-896F-25F4E3C2AAE6","rank":"normal"},{"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":"Q411043$FF960C51-F38F-4175-BA1C-96E903F60503","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":"Q411043$D2667A5B-1D03-4264-A191-F4265D53D078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27c186dafcfcfbb3a8e2963b73cb2c672ac92111","datavalue":{"value":{"entity-type":"item","numeric-id":4501048,"id":"Q4501048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$5B97751D-AADA-454C-8E5E-90A07D04296D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08d33ec4beb8d2de451e1165cd720b27945e7649","datavalue":{"value":{"entity-type":"item","numeric-id":4250816,"id":"Q4250816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$4E1B9B4F-67E1-4F5E-81D5-8A505F723602","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":"Q411043$239668AA-2794-4AB0-9703-67E53BE62E1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d93b1bca22a668f970aca7b50abbc0d16fb7714","datavalue":{"value":{"entity-type":"item","numeric-id":3881775,"id":"Q3881775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$6894407D-2966-420E-8C8C-7134B56E829F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05adcb9a0095806abd3c9c382e7ce85d1b4a7716","datavalue":{"value":{"entity-type":"item","numeric-id":2390239,"id":"Q2390239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$0951A815-588E-4FA1-93EE-CDD32551ED54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"422187dd70b9619226571624878cb1c6a8b29870","datavalue":{"value":{"entity-type":"item","numeric-id":3877553,"id":"Q3877553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$20B4C5E6-7BD3-4541-AE1B-52E74DC93497","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb0fde01bb2315d11174b5916b77c40341f12463","datavalue":{"value":{"entity-type":"item","numeric-id":5541613,"id":"Q5541613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$DD277B27-1994-4DC8-B934-FD836F5EB378","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a62cdec956f493e0e23da573b7623b64aa5e4b5","datavalue":{"value":{"entity-type":"item","numeric-id":4154061,"id":"Q4154061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$5D1518A6-B95E-4F6B-8713-52DF735212F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fccf8d67254f95891c63c90c526631208e1cfdb","datavalue":{"value":{"entity-type":"item","numeric-id":3840196,"id":"Q3840196"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$BF71D46F-2BE3-403B-9994-98A1957C9815","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a5e25eea50ede0b2fe3a056631024e36aa91d61","datavalue":{"value":{"entity-type":"item","numeric-id":3347945,"id":"Q3347945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$AC476747-AF04-4586-B046-372B965C6680","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd5d7cbe8bfff66708a1d1ff67cd00bd6eba6fd3","datavalue":{"value":{"entity-type":"item","numeric-id":4210962,"id":"Q4210962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$CD189EB3-7F2D-4939-AEAB-5B9F35117C15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4921b85d36d7d1e029585226bb8116c777cb8e6","datavalue":{"value":{"entity-type":"item","numeric-id":4071300,"id":"Q4071300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$49298EB3-C843-43DE-A4C6-E572ABAC38B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"354743a0150c2505524747689903fce2fa318856","datavalue":{"value":{"entity-type":"item","numeric-id":4344097,"id":"Q4344097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$3892CE2E-52AD-4D68-B0F8-F53FD8E77C4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3dedb548b46ac9ed3983a986efd50d7c00919ea","datavalue":{"value":{"entity-type":"item","numeric-id":3491688,"id":"Q3491688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$7F088597-308E-4685-8D71-3130452B808D","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":"Q411043$9AC6C40A-4E30-4BCB-A5E3-F4768E05DD96","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"481011349ee103f3b00b5f0c8c7fd154be537a6d","datavalue":{"value":{"entity-type":"item","numeric-id":431795,"id":"Q431795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc65cf7bc95bcfb6831e6e1c43017c7464388f27","datavalue":{"value":{"amount":"+0.8476365208625793","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":"Q411043$2902CD88-A713-435A-8710-EDC0AA6023A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c70c7e1cf5d6bb4af6a8026ff58c523fbc9bb873","datavalue":{"value":{"entity-type":"item","numeric-id":2949487,"id":"Q2949487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6dd46a9098689cfdf1b8ab43d9441fbd27e3d393","datavalue":{"value":{"amount":"+0.8419191241264343","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":"Q411043$D744F4C1-C330-4852-9AF2-2D8D8AF9080C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b1d7787c5a984606c4d8854e8a69e6f78455e46","datavalue":{"value":{"entity-type":"item","numeric-id":2941189,"id":"Q2941189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17c509ad06b1e0b6a0888c5092460e872b25ab2b","datavalue":{"value":{"amount":"+0.8398971557617188","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":"Q411043$40BCEBEE-E9F1-4E60-8420-B9E53FEDEE77","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":"02b3881d028ca8b034fe84ac0c17d53a256651fa","datavalue":{"value":{"amount":"+0.8240590691566467","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":"Q411043$E0904056-BEB4-4F3E-A189-13BDE8BE2845","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e2a9a54cbae2bf269a636332657361e38cdfd25","datavalue":{"value":{"entity-type":"item","numeric-id":5396021,"id":"Q5396021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fdea13ea5d32f720021d0314ab0349836a5b157","datavalue":{"value":{"amount":"+0.8235790729522705","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":"Q411043$8E10A212-BF04-48A2-9981-BB9C6775578B","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"2b5c9b35d8e9d156fad0e174bf1ededba57ccca7","datavalue":{"value":{"entity-type":"item","numeric-id":13572,"id":"Q13572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$FEAD4A1B-E7A1-4305-B45D-B150776FD2A3","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q411043$068A20D1-B178-4FB8-9098-03C0D02B6F30","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An efficient collision detection method for computing discrete logarithms with Pollard's rho","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/An_efficient_collision_detection_method_for_computing_discrete_logarithms_with_Pollard%27s_rho"}}}}}