{"entities":{"Q1284218":{"pageid":1294968,"ns":120,"title":"Item:Q1284218","lastrevid":46581813,"modified":"2025-12-25T01:59:18Z","type":"item","id":"Q1284218","labels":{"en":{"language":"en","value":"A polynomial time algorithm for diophantine equations in one variable"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1271790"}},"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":"Q1284218$E616F8A5-F4EF-45BA-B110-088555CD5842","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5187ea03837ab86994e5b7a00b65afe106c08460","datavalue":{"value":{"text":"A polynomial time algorithm for diophantine equations in one variable","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1284218$2CF464D0-150E-464F-AEC2-B1FE9BB688EC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"773135f92f51d4a45eb222f96314a78d8908dd31","datavalue":{"value":"0920.11085","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1284218$2E2CBFA9-A190-4D2E-A7D8-06DC1154E74E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3c2e1176b7e05a6aa00019f286dc7036ccdb20da","datavalue":{"value":{"entity-type":"item","numeric-id":199198,"id":"Q199198"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1284218$DBC1F4EF-7329-4A8C-9ED7-B1A846E2A8F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5c6184dbf168c93692fa6f8742ab0b2d67a8b9b","datavalue":{"value":{"entity-type":"item","numeric-id":287066,"id":"Q287066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1284218$EE2D033F-E461-4C2E-8C34-D28F0D466199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"80056f0ffc9a74d5261eedd95a06d048390628f2","datavalue":{"value":{"entity-type":"item","numeric-id":486673,"id":"Q486673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1284218$77024693-0888-42D7-BCA6-0AC5CEC39599","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1284218$4D5D86AA-EACA-4E8D-A39E-DCB09ADD3BC6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"641f83e1b8c9394b4305abfb8491fe0a448b416c","datavalue":{"value":{"time":"+1999-06-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1284218$85C4066F-2B3A-492E-B2B6-ACB7C7344FFF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3c5916fb9531b62eb963dfb9b9ff3643eb6f2877","datavalue":{"value":"https://semanticscholar.org/paper/2a08fb87f8e8e368322bdf1e65245b5bcabc74c7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1284218$836DA9FF-1C8F-4D46-9C9C-666D3BFDDEE2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9411f848268841b7f8d602fa69c4f1fd73361dba","datavalue":{"value":"The goal of this paper is to prove that there is a polynomial time algorithm which given input \\(f\\in {\\mathbb Z}[X]\\) outputs the set of integer roots of \\(f\\). The authors choose a sparse representation of polynomials and define the size of polynomials with respect to this encoding. The main step is to find an algorithm (of polynomial cost) to compute the sign of \\(f(x)\\) for a given integer \\(x\\). The key lemma used by the authors is the following: There is an algorithm which given \\((x,\\alpha)\\in {\\mathbb N}^2\\), \\(x>0\\), outputs \\(\\ell\\in {\\mathbb N}\\) such that \\(2^{\\ell-1}\\leq x^\\alpha \\leq 2^{\\ell+1}\\); the halting time being bounded by a polynomial in the size of \\(x\\) and of \\(\\alpha\\). The proof of this lemma is based on a theorem of Brent concerning the computation of the first digits of \\(\\log x\\). The paper ends with several interesting open problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1284218$E14D0E78-74B8-4B7A-9561-BCA6C4992A61","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7b37a6de3a76a2f46603d2a1e14f19e4a44922ce","datavalue":{"value":{"entity-type":"item","numeric-id":168882,"id":"Q168882"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1284218$2759874F-1D4E-441F-8A2A-C731D07E49E1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"67c45964bb1554d8a802bf9a29e50db9b1c5a363","datavalue":{"value":"11Y50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1284218$9CB1BD2E-86CB-4B6F-A88E-75C7087363D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1284218$DD46C410-411E-40FC-B278-7D258311B434","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c62dcdab30534531627492ab560a7deb5759228e","datavalue":{"value":"11D41","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1284218$281367B3-251F-41C8-9945-BFAE501283F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1284218$DBD0A769-3BC7-43B3-869D-3D01363367EF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1e729aad87db2a852f68336e55a3da4556db62e5","datavalue":{"value":"1271790","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1284218$A291FDBA-454B-400C-B9BD-40F30B0029A0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a8581a4fe4c0d3571122fc96549003538cce73aa","datavalue":{"value":"sparse polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q1284218$5F17C1B4-5F6C-47F5-86C6-03D70AAB7D4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4266c089f59104913128a3557043086c3cc2da9b","datavalue":{"value":"roots of polynomials","type":"string"},"datatype":"string"},"type":"statement","id":"Q1284218$46BCB0E5-0220-45A4-90CA-32FF37046618","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11acd2fb6ad6c566c252aa4b6fd795400412f6ca","datavalue":{"value":"complexity theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1284218$32520E0E-954C-4808-9717-A633A5D8AEF1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f7c71ef55bff7944348e7028998e018bd4d01de","datavalue":{"value":"diophantine equations in one variable","type":"string"},"datatype":"string"},"type":"statement","id":"Q1284218$B988769E-803C-44E6-9CB9-0DC87D76571B","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":"Q1284218$AFFEF134-0C1F-45D7-BB0C-5A447DA059C6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5c6af6334096f442ba887b89ddd6e763cc908616","datavalue":{"value":"W1980469175","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1284218$441E07B8-0D58-4A7F-9B68-7E0CF62E0069","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"67f7789d5257155e01b94ee9bdb7e1bf4b7bcfbb","datavalue":{"value":"10.1006/JSCO.1998.0242","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1284218$174ED40E-CF97-4C8E-8F23-FC9E9B1697B6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48a6fb804286ec3e599776e12f8662b3926e3311","datavalue":{"value":{"entity-type":"item","numeric-id":3326837,"id":"Q3326837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18c90fba802c7f9392fd49f72f9d2aa4d64d2b42","datavalue":{"value":{"amount":"+0.7584517002105713","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":"Q1284218$96FDAB79-43FA-412E-BC5C-6EE836C4CC23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"299eb538866c73c48bcd9b0d7bd99c58a9151528","datavalue":{"value":{"entity-type":"item","numeric-id":1763426,"id":"Q1763426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4ccf82c732d150b3f0875498744b083b24a6346a","datavalue":{"value":{"amount":"+0.7520399689674377","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":"Q1284218$F17F8AE3-0454-4981-A018-1AB83DD64626","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a55e7d3c7f163c105e926cf27338e59901ea9367","datavalue":{"value":{"entity-type":"item","numeric-id":3452416,"id":"Q3452416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"525baa328ff3e6c6a890e9c48cd6026af4734e54","datavalue":{"value":{"amount":"+0.7493559122085571","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":"Q1284218$DD7558AE-E9BE-48F9-91B1-21C551B5B241","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"db9e5fac2ebc578f37dc4f073bc765f928b3ab8e","datavalue":{"value":{"entity-type":"item","numeric-id":3686034,"id":"Q3686034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99f960dc497f6fc508157ead86dd6f6005c6bf50","datavalue":{"value":{"amount":"+0.743829071521759","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":"Q1284218$A746E750-A2D9-4D40-8505-237DB4AF92AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"415aa420cb95b016aafade2675d3fa4c6ac08923","datavalue":{"value":{"entity-type":"item","numeric-id":650838,"id":"Q650838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b9280370d303ddd76276f8dcd58bd6de59979f0","datavalue":{"value":{"amount":"+0.7264365553855896","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":"Q1284218$7C078D7F-4D50-4D40-A61D-B1C4C535CF16","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1284218","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1284218"}}}}}