{"entities":{"Q2093686":{"pageid":2104429,"ns":120,"title":"Item:Q2093686","lastrevid":57724848,"modified":"2026-04-01T02:54:08Z","type":"item","id":"Q2093686","labels":{"en":{"language":"en","value":"A deterministic algorithm for finding \\(r\\)-power divisors"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7608407"}},"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":"Q2093686$226FCE74-C4A4-4D00-A298-5AA644237217","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"31663787849749373c2edb9926cd3691c8b86238","datavalue":{"value":{"text":"A deterministic algorithm for finding \\(r\\)-power divisors","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2093686$26EA2F99-7CE2-48AC-B0C1-D1AFA7BBD6A0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e69e9df05c651df5c68ef0c49a15da905e0c815c","datavalue":{"value":"1505.11155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2093686$C2A3E04B-070D-4F21-92F5-47C7C11F4BD0","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":"Q2093686$5B25C715-5298-471D-B8DC-7AE232774939","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b081e00ed349b607d216f2109d0792e46894c1bd","datavalue":{"value":{"entity-type":"item","numeric-id":2023316,"id":"Q2023316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$2A46CF67-3C57-4D7D-9083-0E33703CB7E9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"df5f8c354fea6f60fb60c332660963d0551b6095","datavalue":{"value":{"entity-type":"item","numeric-id":254941,"id":"Q254941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$B69F7A30-4ABF-4D93-A321-A8141D4D7303","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"98f4f5bf88e7cf6cb5883450d0b7f2980cf26dac","datavalue":{"value":{"time":"+2022-10-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2093686$9D77550C-CBBA-4042-86F0-F39EDF2C440A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2b0a57be23e4245e17487357afd81c60592c963f","datavalue":{"value":"https://arxiv.org/abs/2202.12401","type":"string"},"datatype":"url"},"type":"statement","id":"Q2093686$86BE48A2-79E8-4A89-A832-650CC403CAF5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b243a01c45337fe31ec447df1f7ec49c3fa086a4","datavalue":{"value":"In this paper under review the author provides a deterministic algorithm, where on input a positive integer \\(N\\), outputs all the positive integers \\(d\\) such that \\(d^r|N,\\) \\(r\\) positive integer. If we assume that \\(r\\ll \\log_2{N},\\) then the running time, in bit operations, is \\(O\\bigg(N^{1/4r}\\frac{(\\log_2{N})^{10+\\varepsilon}}{r^3}\\bigg), \\) for any \\(\\varepsilon>0.\\) The author remarks that, the algorithm is impractical for small \\(r\\), so it can not compete the general-purpose factorization algorithms. It is important to notice that, the algorithm is \\textit{fully} deterministic, whereas in other factorization algorithms such as ECM and NFS, the algorithms are based on heuristic assumptions in order to be analyzed with respect to their running time. If we apply the algorithm of the paper in the squarefreeness problem of an integer \\(N,\\) the best algorithms have running time \\(O(N^{1/6 +\\varepsilon}) \\), however the algorithm of the paper provides running time \\(O(N^{1/8+\\varepsilon}).\\) As far as the case \\(r=1\\), the algorithm does not provide any improvement from the Coppersmith's algorithm, i.e. the running time remains \\(O(N^{1/4+\\varepsilon}).\\) The proof of the Theorem builds on the work of Boneh, Durfee and Howgrave-Graham.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2093686$2775AECF-4516-4C40-8E5B-3D3D0F2D807E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2093686$349A2F75-A678-415B-A8F7-B12555B07D4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2093686$725833D3-44FA-4A50-9071-F6801430E17C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"20afa916015e6219375b9937ece6e51d63990b6f","datavalue":{"value":"11Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2093686$80C35275-788D-4807-AB8D-3EB414CEE02E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"73a8f38f3f75c75b510f7587bc4a2651e6d175e9","datavalue":{"value":"7608407","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2093686$E56C9BBA-ADA8-4E94-B472-F35205958544","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3184b11a31d7da69732803fd79ace03f08629407","datavalue":{"value":"factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q2093686$8677164E-5C78-4384-8405-EC207EF27A85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"201bb28bcccb142dcb5663217cc697fc05670b9a","datavalue":{"value":"LLL","type":"string"},"datatype":"string"},"type":"statement","id":"Q2093686$AE539AA5-D96F-4765-AA99-0A33C78880BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"415aa5dac7f47fdaea9050e90100e1d85b8d985d","datavalue":{"value":"Copersmith's method","type":"string"},"datatype":"string"},"type":"statement","id":"Q2093686$CCC99670-7550-4E8E-B2B6-9BFBE26079CD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ba9b9b8b272cff31f2a029a4bbcc57f78fba1593","datavalue":{"value":{"entity-type":"item","numeric-id":280949,"id":"Q280949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$F78740F3-B2E7-426A-958A-6F564F63F5FD","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"54a42ebcd493d14c168e95ef4c51dd56eddd67ce","datavalue":{"value":{"entity-type":"item","numeric-id":13798,"id":"Q13798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$CDE2D22F-8E49-4459-9D05-86C7F26C37A3","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":"Q2093686$1819E8EA-CF14-4C86-BC8F-2A1408CDAA09","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"44bd337fe9a2cf8cc37d930f560529d7d0a87f37","datavalue":{"value":"W4307086467","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2093686$EC3137DE-5E0D-49AE-87A3-B62F50482DDC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1f74c7c2971383433ec24293db5222b2eb073d18","datavalue":{"value":{"entity-type":"item","numeric-id":4941863,"id":"Q4941863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$9A57F00B-1AF4-45E2-8B5D-E00B74C06069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d1fa6d8f1250dd18c27e9d91d9e03ac2a89215c","datavalue":{"value":{"entity-type":"item","numeric-id":3615929,"id":"Q3615929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$42C41F98-C5F4-4324-A3CD-C9E4F1B50DE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"547427d506a35672c556073c6de35b4672e46fbf","datavalue":{"value":{"entity-type":"item","numeric-id":2263800,"id":"Q2263800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$D54D72D8-34E9-4C3F-A46A-3C2A9DB4F285","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a14827d9bb7d827953fbb64d29f8309430201c4","datavalue":{"value":{"entity-type":"item","numeric-id":3060337,"id":"Q3060337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$50559883-D501-47FA-AAD3-4D01C42E69D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbd9853f36448729dfca6b95b6e1f942875c416f","datavalue":{"value":{"entity-type":"item","numeric-id":3707405,"id":"Q3707405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$36702A24-C3F9-417E-9718-E9A0FACA5210","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e88326418ce589202405019cf656161fb43c67b7","datavalue":{"value":{"entity-type":"item","numeric-id":1382143,"id":"Q1382143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$199D9F41-8C3B-4539-B40D-4D8E77F72907","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b0c9e975d62c78a840733848507c836d9802dd0","datavalue":{"value":{"entity-type":"item","numeric-id":3740227,"id":"Q3740227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$8017D7C6-A543-4C78-927C-1424EC9962C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4dabdbaf8be4a947301a3bb3da27942dd8cfaf0","datavalue":{"value":{"entity-type":"item","numeric-id":2880040,"id":"Q2880040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$DC7F8A45-3E5E-4AB4-9E2C-A6BE49F1E64D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bb046514cfa3ab7a8e56d4ca52e6eb37df4d26c","datavalue":{"value":{"entity-type":"item","numeric-id":5070544,"id":"Q5070544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$ACE51772-BBD6-46C6-A0A7-A5C9C5CAAEB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2496d76f7d7fec9d96f39f6e3a59ed93c78d8e95","datavalue":{"value":{"entity-type":"item","numeric-id":1165896,"id":"Q1165896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$F9647D9B-B8E9-477D-A62F-67B60B88AD16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0422dbaab910c5a7f3e097381b94ce94eaaf540","datavalue":{"value":{"entity-type":"item","numeric-id":3321471,"id":"Q3321471"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$0BFB50A4-00E7-4117-9C70-8B3AD5B1E9F5","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":"Q2093686$5299A9C9-47F9-4AC7-BE8B-925ABE0EDB83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5a78b39c47b8ce7651037e1276f0da03489475d","datavalue":{"value":{"entity-type":"item","numeric-id":4046106,"id":"Q4046106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$796F4321-26A1-427A-AD62-8B0E729031C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6a88e7c87651eeb3ff2433bf71733b763895cdc","datavalue":{"value":{"entity-type":"item","numeric-id":2626710,"id":"Q2626710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$02170A26-3EDF-4705-AD8D-47C89885FA9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"696056ff49d7c9804ae219e65f4a8593ba5a580c","datavalue":{"value":{"entity-type":"item","numeric-id":3796740,"id":"Q3796740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$0C8990A9-81DC-413D-BBE7-268EEF8BDC48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c8fb2517a72a37de4c3e4a053678d0381153b9c","datavalue":{"value":{"entity-type":"item","numeric-id":1239605,"id":"Q1239605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$AEE24D51-8082-4300-A101-A1622013282D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9584bf30734f7f82097f4720ee16c825113f67fd","datavalue":{"value":{"entity-type":"item","numeric-id":5465641,"id":"Q5465641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$A5B1FF6E-C603-4107-B068-8C2B88C6099B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd70e15b35f8a08de7af7e5f78880a55220bcb51","datavalue":{"value":{"entity-type":"item","numeric-id":2862994,"id":"Q2862994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2093686$FBD712AA-B5F7-46BD-A571-449A8D804F8F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5e218ddc55dd52ef32fa172637e5d5cefcf0fa00","datavalue":{"value":"10.1007/S40993-022-00387-W","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2093686$DAC9398F-AEA8-4E6E-8D55-7CD38C9A8658","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10d457553129390f33b793d5ff962b847a052587","datavalue":{"value":{"entity-type":"item","numeric-id":2796032,"id":"Q2796032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d2539368969e82f0b013684cf35dd03ac7f51e7","datavalue":{"value":{"amount":"+0.7601364850997925","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":"Q2093686$BA96D122-A5BD-4B02-8FAE-A08DEE84BF49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dea6a4f126813df0fc6f06b28accad0fe6a205c2","datavalue":{"value":{"entity-type":"item","numeric-id":3420437,"id":"Q3420437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a1bf5dd717d523084595b2e25561015f432ebb0","datavalue":{"value":{"amount":"+0.7319966554641724","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":"Q2093686$65A1C360-AAD1-4464-9651-C59BD4304D3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02f7ec01bbb83b84d5c7a8366403196ec946284b","datavalue":{"value":{"entity-type":"item","numeric-id":4396462,"id":"Q4396462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e28143dcc80626db4f4fcc588c86739e79e64952","datavalue":{"value":{"amount":"+0.7282257080078125","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":"Q2093686$FDB166A6-6363-47D6-8B15-B0DCFB13952F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05f417861a1b49656394dbb0fca1caa295290f4c","datavalue":{"value":{"entity-type":"item","numeric-id":3097076,"id":"Q3097076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d48a8aee297d079937741f75577641acbd46e04","datavalue":{"value":{"amount":"+0.7276145219802856","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":"Q2093686$4D029BB9-0B87-4D92-8920-0177D0ABA01E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"974201f06aba18bdd35279e6de9293a7d61130b4","datavalue":{"value":{"entity-type":"item","numeric-id":4683943,"id":"Q4683943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc6366cbfaaaf83d7a43659f538934898290d695","datavalue":{"value":{"amount":"+0.7072362303733826","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":"Q2093686$FD1866FC-D4D6-49E5-9E8E-BA33938AA320","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":"Q2093686$2F3ACE19-EBF6-4BBC-B3EC-1853BCAAAA3F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2093686","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2093686"}}}}}