{"entities":{"Q2366170":{"pageid":2376913,"ns":120,"title":"Item:Q2366170","lastrevid":78676361,"modified":"2026-05-06T12:10:31Z","type":"item","id":"Q2366170","labels":{"en":{"language":"en","value":"Fast exponentiation using the truncation operation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 223340"}},"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":"Q2366170$5B88A251-4338-4EA9-A6A3-7FE2FFEA3F83","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3fea60c5bed80ae4583c20eade2ca76651eac816","datavalue":{"value":{"text":"Fast exponentiation using the truncation operation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2366170$2547ECD7-BC54-4D6E-A4FB-E295B8BD5533","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"50efc378be03eb5f2724be0add1adecc94e08737","datavalue":{"value":"0771.65008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366170$E9AB7B22-929B-4992-8C67-702B9A406859","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"456f3498114f0a6b2d7cf2cb5b4894b5e6a95210","datavalue":{"value":"10.1007/BF01272076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366170$A07684AE-DC3D-4815-9FD2-868CE1AFBF92","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d5ea23ab68f685e1719f8b72c579f7993f3b0845","datavalue":{"value":{"entity-type":"item","numeric-id":287181,"id":"Q287181"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366170$E8587FA2-BD17-4A1C-B802-233B91DB5797","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0fa357464d74acb9975fa4cd05187c5de744d8ff","datavalue":{"value":{"entity-type":"item","numeric-id":222241,"id":"Q222241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366170$7CC55727-2FA0-4E7F-96D5-203FCDB10D8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dff9feb3c5b84d40611faa1bb1e3fe810be17c3e","datavalue":{"value":{"entity-type":"item","numeric-id":221691,"id":"Q221691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366170$62C0F805-56D0-4960-878A-C7FF90CA7CEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"74ab5fd86840fc5ffff602487c6ddd935d8a77ea","datavalue":{"value":{"entity-type":"item","numeric-id":287182,"id":"Q287182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366170$964ACB9A-3E1E-439C-9E40-9F6BC4AA3A0F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4472b31ebff52fa964618256e5b76c8eb3e874c2","datavalue":{"value":{"entity-type":"item","numeric-id":172540,"id":"Q172540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366170$A34627BA-044F-4AD3-8742-CCE22E40EFD6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"be4381b75afe2df0dbe37cd1a66e006418c0c5aa","datavalue":{"value":{"time":"+1993-06-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2366170$699A9E51-CF8F-4303-8FAA-0C5E513B4A83","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"05a329a13f31ae8e09bbb044e9b37cfb0903be3c","datavalue":{"value":"A tight bound of \\(\\Theta(\\sqrt k)\\) time required to compute \\(2^{2^ k}\\) is proved for the inputs: integer \\(k\\) and arbitrary integer greater than \\(2^{2^ k}\\), the operations \\(+,-,*,/,\\lfloor\\cdot\\rfloor,\\leq\\) and constants \\(\\{0,1\\}\\). It is applied to the algorithms: (1) for computing \\(\\lfloor\\log\\log a\\rfloor\\) for all \\(n\\)-bit integers \\(a\\), in \\(O(\\sqrt{\\log n})\\) time and (2) for deciding whether an integer \\(a\\) in some range \\([2^{2^ k},2^{2^ k+1}]\\) is a perfect square in \\(O(\\sqrt{\\log\\log a})\\) time.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366170$7812036C-42CD-40E8-96EA-752D58811C6E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d52a9790bd413da9f05e066965338e566eb3e865","datavalue":{"value":"65D20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366170$2A383F9E-3888-478A-981C-BA3C854695BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366170$23F88D4D-82F6-4A5F-9EA4-99A716593018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366170$1E94EEF8-89B9-403B-A419-BB79858E8E7B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b83c3661e4f2b552548ccef13eddb7b0de3b8ec0","datavalue":{"value":"223340","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366170$FF5245E3-90E5-4E5C-8DC1-41AB6521E220","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366170$0744F34C-A29C-4276-8C68-2737C7BB9F92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea9a528d71a0d70434effee32ecfe1207e474c6b","datavalue":{"value":"fast exponentiation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366170$5D37AA87-16EA-455C-9E0E-1BDBD658E990","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7339ca42e8ef41481313554babf174aa98dc21b3","datavalue":{"value":"truncation operation","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366170$AA2A2619-AD93-4A53-9AC5-187430B10A50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5cadc44a57f3163b00ef545ce8b0a09ba322399f","datavalue":{"value":"exponential function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366170$69F83C53-6279-4B6E-B850-57C8C0B95D2E","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":"Q2366170$01B7F328-FC5A-4729-96D8-45AC4A3911B0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366170$16D69216-8618-4F88-A5E2-4C3E78FB7655","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f3c5de43fa0f18625cc6b26062b0f0c192a4485","datavalue":{"value":{"entity-type":"item","numeric-id":1112603,"id":"Q1112603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366170$6C654141-9F2F-4CC7-8480-3A073081ECD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cf59a4a27f431b066773582953fa61e5ecbb2912","datavalue":{"value":{"entity-type":"item","numeric-id":3219782,"id":"Q3219782"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366170$B691C620-5B71-4523-953C-73F55BCB4EF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3eb082ca5948e1a752483fe8cca978a09994714","datavalue":{"value":{"entity-type":"item","numeric-id":1838280,"id":"Q1838280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366170$109793D0-2792-4B48-BEE4-77648F9A81B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4cd7ae099659679ff6eae24635fd42820a6e2e6","datavalue":{"value":{"entity-type":"item","numeric-id":1072938,"id":"Q1072938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366170$F14A3F42-6AC1-4552-A3F3-2F390784CC79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c6d3a9afe28eb740c3a58f6cd6e4753cdc280a7","datavalue":{"value":{"entity-type":"item","numeric-id":4302842,"id":"Q4302842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366170$64CB6270-7159-4E37-AFBF-8C38115670B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06570c05095a8e93c71097048ea96699ab82c2f2","datavalue":{"value":{"entity-type":"item","numeric-id":3212292,"id":"Q3212292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366170$CEB8242C-F704-4059-AF17-4AFDDC68A751","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"03a31dad6f298be2eb92d6df880997f69f6949f8","datavalue":{"value":{"entity-type":"item","numeric-id":2557558,"id":"Q2557558"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366170$A5C88B93-D142-46BF-8EC9-3987DCD78A62","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a1886a0b273577e48bcd18fea441a53670e8c3e0","datavalue":{"value":"https://doi.org/10.1007/bf01272076","type":"string"},"datatype":"url"},"type":"statement","id":"Q2366170$F946D4C9-15A9-4C87-A780-AAE3B3183FA1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"08f438728094ae801ebc757ee37aab870893c560","datavalue":{"value":"W2081862234","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366170$FEC43217-9520-4EF6-8E3A-AD6708EBA646","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46705611a1cd86b61ab9398427191356f62996e0","datavalue":{"value":{"entity-type":"item","numeric-id":3212292,"id":"Q3212292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d9710a98154eaed16d69d42df03b64d641601f0","datavalue":{"value":{"amount":"+0.7282540798187256","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":"Q2366170$515CC2B0-E9E5-445A-858C-735CE67A2E4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23283602ab8fcdadd2487ce7c55825892c00dc71","datavalue":{"value":{"entity-type":"item","numeric-id":4732103,"id":"Q4732103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d8f09474cb7a20a897bf5b96fd249c5dc79404ad","datavalue":{"value":{"amount":"+0.7080331444740295","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":"Q2366170$185B4A4C-C868-4E37-A08D-A621F4DECB20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7383f723ad05101219c564a61605bd590e7c7af1","datavalue":{"value":{"entity-type":"item","numeric-id":287183,"id":"Q287183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd61b7b2a1861eea62cb434c971a59969e133189","datavalue":{"value":{"amount":"+0.7037134766578674","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":"Q2366170$DB623A82-EC4B-4EEB-B32D-AD4C43920DBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cc513a3d5af9788b790ed78df280429ccf8bd7a","datavalue":{"value":{"entity-type":"item","numeric-id":2380060,"id":"Q2380060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"108748ea5aeeecbfb74164574a918a2051a2341f","datavalue":{"value":{"amount":"+0.7032951712608337","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":"Q2366170$27ACDAF7-2885-45F8-92F3-2291987E2746","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":"bdda16b5b4ada6d3db3ce1bc8c07832eb8daca17","datavalue":{"value":{"amount":"+0.6964271664619446","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":"Q2366170$3506C5E1-78AB-43C7-B2EA-1769D8254633","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Fast exponentiation using the truncation operation","badges":[]}}}}}