{"entities":{"Q896029":{"pageid":897877,"ns":120,"title":"Item:Q896029","lastrevid":57209502,"modified":"2026-03-27T11:50:17Z","type":"item","id":"Q896029","labels":{"en":{"language":"en","value":"Integer factoring and modular square roots"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6520025"}},"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":"Q896029$15B59FA9-3ADF-4D9C-9C9D-E3D8293DFA42","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f6497229530e28a3f4bb023e2612b7e693bc37b7","datavalue":{"value":{"text":"Integer factoring and modular square roots","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q896029$B0DE149B-D8DF-4A07-989A-0D8318B47AB0","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8d7df462267a49ea062f4d792a0dc12828e0b4d5","datavalue":{"value":"1330.03088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896029$08B15C88-0E73-476F-9FBB-199B5189C118","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e1376d5316fb71db1c6e9bf664dff79c67388b0d","datavalue":{"value":{"entity-type":"item","numeric-id":331053,"id":"Q331053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896029$CB042939-FD51-4E82-AACB-2127DE043FA4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896029$0BA55586-6157-43C9-9CA4-44781D6D8AEE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5f98ff43191c7d2cedf25947a17beeb973f5b0c2","datavalue":{"value":{"time":"+2015-12-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q896029$8D507375-D3D8-4693-BF28-C4F67FE84D33","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"493193a0a211013202063bcbe8eff19fe716237c","datavalue":{"value":"https://arxiv.org/abs/1207.5220","type":"string"},"datatype":"url"},"type":"statement","id":"Q896029$512C20BE-2156-4718-BF16-62C1A6CE791A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1a9cadfe2bbffa45f9e6302f50cb377d602b6ea6","datavalue":{"value":"In the paper under review, it is shown that general integer factoring is reducible in randomized polynomial time to a PPA problem and to the problem WEAKPIGEON \\(\\in\\) PPP. It is claimed that both reductions can be derandomized under the assumption of the generalized Riemann hypothesis. It is also proved that PPA contains some related problems such as square root computation modulo \\(n\\) and finding quadratic nonresidues modulo \\(n\\). In the proofs, some ideas from bounded arithmetic are used. The results of the paper extend the results of \\textit{J. Buresh-Oppenheim} [``On the TFNP complexity of factoring'', (unpublished note), \\url{http://www.cs.toronto.edu/~bureshop/factor.pdf}] to arbitrary integers.","type":"string"},"datatype":"string"},"type":"statement","id":"Q896029$00B96632-748E-4CB6-9692-2E1263109B30","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"c15287dbb142f8dc10ab92a91b8457ac3c169cd3","datavalue":{"value":"03F30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896029$5F545318-786F-41A6-8A22-E33DF99E1E8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896029$CD67FAB3-9446-4532-AD33-4BC94294AF7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"20afa916015e6219375b9937ece6e51d63990b6f","datavalue":{"value":"11Y05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896029$27843036-DBC9-4197-8EF6-888502B975DE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"98fbc56894ca11e049e41177e906fb1becf7aefe","datavalue":{"value":"6520025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896029$5C6E396D-74A6-4330-AC11-F9BA039B4813","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4fe6883e7864a010be3c18ec9bd3e26693c4a398","datavalue":{"value":"integer factoring","type":"string"},"datatype":"string"},"type":"statement","id":"Q896029$B4A6FAC0-51F4-4AEE-9D7C-F0132B205AB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"671b724c7f622837711cd64770685dbc851ca4d8","datavalue":{"value":"search problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q896029$0488881E-6E63-49B7-BE3C-67A30E6BC926","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f20dadf35c75fa60da5cf59f11f656db3bad210b","datavalue":{"value":"PPA","type":"string"},"datatype":"string"},"type":"statement","id":"Q896029$8CCFFDAA-7691-4C8A-B4CA-9E12BFA0D0A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ee0278cf3262e2aedc982fe8d68bfd756c990b1","datavalue":{"value":"quadratic residue","type":"string"},"datatype":"string"},"type":"statement","id":"Q896029$22A3B624-96AA-44F6-8B9A-A178874A20F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cba2903ab2dafc050042cd489ae05396ebe51a19","datavalue":{"value":"bounded arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q896029$E83A280A-AFCB-446C-AB55-EE449F9FC3D2","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c45938d3b1c1a5c68183caabb02f42934d9ff682","datavalue":{"value":{"entity-type":"item","numeric-id":588140,"id":"Q588140"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896029$A52AFD85-BAA1-44B4-A665-FF574CA42DB5","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":"Q896029$8FA13340-8FC9-4AAF-BCED-598078E70E83","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ce3356751ffa9f4f50448ccfac967bdcc3c9c297","datavalue":{"value":"W1804423330","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896029$1A614710-EFE6-4921-AAB8-9E136CE32BFE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1234570f11caddb900135131d2fd06479f5792ac","datavalue":{"value":{"entity-type":"item","numeric-id":1772458,"id":"Q1772458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896029$83B96D33-261A-4AA4-B91A-AD7407648179","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"654ef497bc56536d1acc44d89e9f6eaa5d631fe0","datavalue":{"value":{"entity-type":"item","numeric-id":2649761,"id":"Q2649761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896029$87744FF4-8228-4AFA-BE09-F29A250E06E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b3f8593cf1d67e57f8d301788ad8e11e669843f","datavalue":{"value":{"entity-type":"item","numeric-id":3478501,"id":"Q3478501"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896029$C51654A6-01F9-4724-9FCC-32C4D3AEC347","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f0206d3a695d8d8e1728212c926a47f4d0e22e7","datavalue":{"value":{"entity-type":"item","numeric-id":1273858,"id":"Q1273858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896029$C7884BC1-DFEE-4820-ABC2-40E61C760160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"305afa85a8cc04e13d160761258e43b79fcfb022","datavalue":{"value":{"entity-type":"item","numeric-id":1182430,"id":"Q1182430"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896029$088B24D6-7FF5-46E8-9C1F-F136A0DF9442","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c967ae4b0fba59ac6a0c72fafaafab5e42d0c5f","datavalue":{"value":{"entity-type":"item","numeric-id":4215631,"id":"Q4215631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896029$9259A2CA-C37C-4A95-9BAD-56B2A6437861","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0aa0d6b54f6be3a440a4bb5a78e5668dceeb60c0","datavalue":{"value":{"entity-type":"item","numeric-id":435190,"id":"Q435190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896029$7E59A185-017D-45EF-B77B-D9B8DBD4AD04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13ac01476efbe2c2327bb137d4a4618ad684caf9","datavalue":{"value":{"entity-type":"item","numeric-id":5431613,"id":"Q5431613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896029$3B475E8B-F2A3-45A6-A5B2-553829E02E86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b712369c9d70d1f4eb2fa189cd3668dbf9934b47","datavalue":{"value":{"entity-type":"item","numeric-id":3566945,"id":"Q3566945"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896029$D9D807B1-754A-4F40-B666-1A500697213C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6fa34ae3e34f6a863a9f8db67c2bfb8bb6401943","datavalue":{"value":{"entity-type":"item","numeric-id":4856172,"id":"Q4856172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896029$E6E3A8E8-0884-4F87-A201-287E2A89BD3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a35ee073efb257c2ff6944a7cc91fcd0fe8bb82","datavalue":{"value":{"entity-type":"item","numeric-id":1329155,"id":"Q1329155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q896029$C06B914F-FDC3-46FA-BABB-21D50B42520F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"894f2d62f0f59e7f0d75fa691dec915e57be6e4c","datavalue":{"value":"10.1016/J.JCSS.2015.08.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q896029$E347F671-0096-4B41-B799-0D17A048E3FE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d6362dee9cd859684eb028f62355cd24aa58056","datavalue":{"value":{"entity-type":"item","numeric-id":2023317,"id":"Q2023317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5964d6733e3d078b34213a9c2b2b21299b6345be","datavalue":{"value":{"amount":"+0.7287635207176208","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":"Q896029$D06C48F6-1B99-4832-99DB-25BB38EC6808","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1c7bd6ca644a5f609423f4f011b6e4d57e2e27b","datavalue":{"value":{"entity-type":"item","numeric-id":1091136,"id":"Q1091136"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8591065da709e0d1ab67714806262b31bb9be54e","datavalue":{"value":{"amount":"+0.7191289067268372","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":"Q896029$9B9F96AA-4BF6-4F84-B777-4D2B248EEAC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ff1576a5528bd45f284e53cd7217ba175353702","datavalue":{"value":{"entity-type":"item","numeric-id":3724235,"id":"Q3724235"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0415c0fe4ed5f07ba4a65a66f064244abc525316","datavalue":{"value":{"amount":"+0.6883360743522644","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":"Q896029$39E7BB9E-ACC0-4998-8CA9-1A12E5F2E2D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c4003092b788c4b980e3b5a914ef07c1e7f2e5c","datavalue":{"value":{"entity-type":"item","numeric-id":4034689,"id":"Q4034689"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb9aae6535b96fbe2e6ca42fd2969e5db1c02e72","datavalue":{"value":{"amount":"+0.6879665851593018","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":"Q896029$7413FDB0-9CC9-408D-9D67-7CFCF88B2281","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc6b3f48cb923c0484482397bc964a18720cb957","datavalue":{"value":{"entity-type":"item","numeric-id":1730025,"id":"Q1730025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"add147d9380bf35f40eb88ad346768cd72fb9ba0","datavalue":{"value":{"amount":"+0.6859883666038513","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":"Q896029$F82541E3-2371-4816-B64D-250385A6596F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:896029","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:896029"}}}}}