{"entities":{"Q752762":{"pageid":754611,"ns":120,"title":"Item:Q752762","lastrevid":64198998,"modified":"2026-04-11T18:17:37Z","type":"item","id":"Q752762","labels":{"en":{"language":"en","value":"Toward a theory of Pollard's rho method"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4179491"}},"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":"Q752762$5060367F-EFBA-4BAF-93F7-1024F81339FF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c8edd86fb1bd6a284da5569520c72a5cc071abb6","datavalue":{"value":{"text":"Toward a theory of Pollard's rho method","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q752762$D0F86F0C-7429-4185-9F6A-7E5087A9C1A7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3ee9a352748b4a0f0c6fc34da09b5f09fbae1055","datavalue":{"value":"0716.11065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q752762$D5F69B79-67EA-4ECA-B8A0-A6AC79001E51","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"be003461521a63f9bb97a5dc1251e99fff6384de","datavalue":{"value":"10.1016/0890-5401(91)90001-I","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q752762$B0F53A81-C9A6-4133-A47B-0BF0F6323A5A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f50b9c64daeb4c22304773eb129c7254f42354e7","datavalue":{"value":{"entity-type":"item","numeric-id":165878,"id":"Q165878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752762$94497F34-DE93-4C7F-AB21-C3ED33D04183","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752762$7F734623-7A44-4401-BC84-DDE2246ED866","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q752762$BC349AA9-AB79-4B17-9497-85DC1DF1E900","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ae0731e21fc1a34db068f6aedd852902ca2b3999","datavalue":{"value":"The author offers a nonheuristic explanation of the remarkable effectiveness of the Pollard rho method of factorization, see [\\textit{H. Riesel}, Prime numbers and computer methods for factorization (1985; Zbl 0582.10001)]. If N has a factor p then the factor appears from finding the sequence  \\[  f_ 0=x,\\quad f_{n+1}=f^ 2_ n+y  \\]  and seeing that \\(\\gcd (f_ i-f_ j,N)\\) is p in about \\(\\sqrt{p}\\) iterates. The author factors \\(f_ i-f_ j\\) and selects special simple factors \\(\\rho_{i,j}\\) monic in y in which to look for p. Indeed these factors, as curves, have a strong tendency to not intersect in \\({\\mathbb{Q}}\\) and thus in \\({\\mathbb{C}}\\). He uses A. Weil's theorem that for a polynomial f(x,y) of degree d, the number of projective zeroes \\(N_ p\\) in \\({\\mathbb{F}}_ p\\) satisfies \\(| N_ p-p-1| <(d-1)(d-2)\\sqrt{p}.\\) His main results are that for k fixed and \\(0\\leq x,y<p\\) randomly chosen, the probability that \\(f_ i-f_ j\\equiv 0\\) mod p for \\(i,j<k(i\\neq j)\\) is at least \\(k(k- 1)/2p+O(1/p^{3/2})\\), as \\(p\\to \\infty\\). Also if pq\\(| N\\) for two primes, \\(p<q\\), then for some \\(i<(\\log_ 2p)/4\\), \\(\\gcd (f_{2i+1}-f_ i,N)\\neq 1\\) with probability \\(\\Omega (\\log^ 2p)/p\\). The paper is remarkable for its heavy use of algebraic geometry to avoid the usual indulgence in heuristic.","type":"string"},"datatype":"string"},"type":"statement","id":"Q752762$D467354A-9EA5-4D25-ADF1-F67A0391A4A9","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0d7fdbc1a2b8e7639c3636cd9be0e2a4893e41d9","datavalue":{"value":{"entity-type":"item","numeric-id":588320,"id":"Q588320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752762$A22AB25F-9630-4C90-8638-A7AF2F3B864C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"20afa916015e6219375b9937ece6e51d63990b6f","datavalue":{"value":"11Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q752762$36CD34A3-6910-4C73-9EEF-0576C89707BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q752762$A45D03FA-4972-483E-A61E-BCE2C379FA8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q752762$70AC3EF5-5E51-41CD-AD1E-A655C72225ED","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b0514f6264af81b769edde5f868f34ba91e86195","datavalue":{"value":"4179491","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q752762$CC1B2CCE-6468-49F9-A0D9-A4D27015F36A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b576d25cabbf559173c94ea25519a9d9b37525e7","datavalue":{"value":"Pollard rho method of factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q752762$223C4F5C-F952-4542-A842-D2DFF00AD830","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"67e6f61a7fde6e41d9848f89177a795ddcdd22d5","datavalue":{"value":"Q29031634","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q752762$431D1F8C-066D-49BA-A592-D4DD30C67552","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":"Q752762$0A33E3A1-74DB-498D-840D-D63684E9BDBA","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"0cc103d2b765825cf270a79629938b04853722a7","datavalue":{"value":{"entity-type":"item","numeric-id":1051000,"id":"Q1051000"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752762$8394DC07-08C7-44CF-9E1B-A17543C2CB9E","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":"Q752762$310CCBBB-36FD-43CE-97DD-43EB7CD22AB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b176c36893d0c69959c3c8ee052280244ff2f4d3","datavalue":{"value":{"entity-type":"item","numeric-id":3933053,"id":"Q3933053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752762$D19C4EF2-924A-46D6-B6C4-5D605A3F54CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48009c1f73f42ac62705674dcadab4eab8e726bb","datavalue":{"value":{"entity-type":"item","numeric-id":3715247,"id":"Q3715247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752762$B8D4FC4F-E1D1-440A-BF69-C98EE18F087B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9539532d16bcb82516fae2db58a1eb7e9c6ca7b","datavalue":{"value":{"entity-type":"item","numeric-id":5538132,"id":"Q5538132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752762$8921FA1C-4D51-4937-9C3D-ABBE008810DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d228248ae3fc503d6b9b2cd0d8c1cd6d2fd95ec8","datavalue":{"value":{"entity-type":"item","numeric-id":5678941,"id":"Q5678941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752762$1B469147-5030-432A-BD58-6E3E0D381ACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f2c0b685389a8438f7f005ba501bef03f0b75b0","datavalue":{"value":{"entity-type":"item","numeric-id":3027108,"id":"Q3027108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752762$4CA11222-F9A4-437B-97E0-477F3C901E45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"18579cf08d72169ade2477ebd1b0f37fe272e568","datavalue":{"value":{"entity-type":"item","numeric-id":5571530,"id":"Q5571530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752762$84F58A1A-68ED-4539-9BD9-70AC164C13A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e893cedfafda0587f1dc0f3f9bd202d5b84af8de","datavalue":{"value":{"entity-type":"item","numeric-id":1172077,"id":"Q1172077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752762$BA8302B2-98BD-4F22-B147-E25E0CE32943","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f16b37544e6f1e8cd09b687f08f3c4a9d4de0129","datavalue":{"value":{"entity-type":"item","numeric-id":4105720,"id":"Q4105720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752762$8CF625B7-3009-46CD-A6BE-5B1091B47D52","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":"Q752762$78DE83EA-30F0-4A7E-936B-D55A91EAE77D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f7a10b1eac9fff79c6c675e24acfe95f872c89c","datavalue":{"value":{"entity-type":"item","numeric-id":3748330,"id":"Q3748330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752762$1BECC381-1838-4F1D-83B3-1B88FA619792","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":"Q752762$F7FF94CA-D57C-4650-95B6-863B2C0AE42A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b89ebaf98c8fde5131cef04a549821dcb75fe243","datavalue":{"value":{"entity-type":"item","numeric-id":5511421,"id":"Q5511421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752762$0A616E16-50F4-46A4-99D1-D5699E7C6744","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcc516d131cefd723c7e1a4a11485abb9a908393","datavalue":{"value":{"entity-type":"item","numeric-id":3249822,"id":"Q3249822"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q752762$BFB462E5-7494-4262-A8A3-2B7EA50E3381","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce7e365fe306e6b73c35045b7ce02cf60c940003","datavalue":{"value":{"entity-type":"item","numeric-id":3933053,"id":"Q3933053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc82f52ac3e42e1d97f47b937177de9c1efad08e","datavalue":{"value":{"amount":"+0.77860034","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":"Q752762$FFDF476C-9AF4-4537-B01C-786BAA5C5D1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fb5012d2e441133780e876de94ae3853d3fd44d","datavalue":{"value":{"entity-type":"item","numeric-id":912919,"id":"Q912919"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"047896c5d67cf6fe1bd99e0aef02ccef1faa8494","datavalue":{"value":{"amount":"+0.76725537","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":"Q752762$3054D56A-C1A1-47EC-BDC0-8F63C1207728","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ed52e302874fd110d1ff20debc4589510c94412","datavalue":{"value":{"entity-type":"item","numeric-id":3932864,"id":"Q3932864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d6c6c4a3e88b814efa1ab4372edf2aff5dc1cd2","datavalue":{"value":{"amount":"+0.7642336","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":"Q752762$ED7517C5-2DE2-4374-B6E2-A8FB43A6604E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b888d29bb152aa4b8fbbdd60529cf61fa9f2780","datavalue":{"value":{"entity-type":"item","numeric-id":2739443,"id":"Q2739443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4352cf686417f3614534b0270e3e2d3aff0175e1","datavalue":{"value":{"amount":"+0.7599503","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":"Q752762$E6A41001-EC32-4F43-954B-A018EB6561D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"173134497c53a5af698b6b857db027382ec0f62b","datavalue":{"value":{"entity-type":"item","numeric-id":3801677,"id":"Q3801677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aaf9c3c3573a22c27090f2dc54afb89bb6279cb1","datavalue":{"value":{"amount":"+0.7544229","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":"Q752762$5E53722A-96F9-46D3-9273-B64D7A1D11DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0f5645495c7c1830f98061beca63da728a1cd3e","datavalue":{"value":{"entity-type":"item","numeric-id":1377270,"id":"Q1377270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"836a05fa1ac1cc057d49af9a28d66fdc02e2989f","datavalue":{"value":{"amount":"+0.7502133","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":"Q752762$B83D1FF2-0927-4C61-B0E9-58B9774B69E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a9a7132f96f3049818fadafb17d6b2bed0e4bd9","datavalue":{"value":{"entity-type":"item","numeric-id":3345783,"id":"Q3345783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4cc38c73d4da412bf87b5bb0a231f2601a206262","datavalue":{"value":{"amount":"+0.75015455","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":"Q752762$D65CE72F-DFF0-4A22-B959-31159669B460","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4330eae727bc14ba5e7f99f89939716540ff24a1","datavalue":{"value":{"entity-type":"item","numeric-id":4654208,"id":"Q4654208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b10b973adc99f72114ccb9d05dbea9808519b44b","datavalue":{"value":{"amount":"+0.7499749","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":"Q752762$C16BAA6F-1827-4464-A5E5-DA15301B1158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3959022516d79157eef690c583fdcd9ec76e283","datavalue":{"value":{"entity-type":"item","numeric-id":1172077,"id":"Q1172077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"10c84ff36c86d6750b4c37cc08df1e08365cbaa8","datavalue":{"value":{"amount":"+0.7496636","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":"Q752762$DA508A49-E49E-412F-A352-97D94DBACC91","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Toward a theory of Pollard's rho method","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Toward_a_theory_of_Pollard%27s_rho_method"}}}}}