{"entities":{"Q1364066":{"pageid":1374805,"ns":120,"title":"Item:Q1364066","lastrevid":43065936,"modified":"2025-07-17T09:42:31Z","type":"item","id":"Q1364066","labels":{"en":{"language":"en","value":"Efficient algorithms for remainder computation and exponentiation of long numbers"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1051104"}},"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":"Q1364066$226A7CCB-8DC0-47BA-BBCA-9E879EDBADE8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"27880963ab273879010aae22185acc12e6b3f5ec","datavalue":{"value":{"text":"Efficient algorithms for remainder computation and exponentiation of long numbers","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1364066$70805D0C-0447-43EA-A0F6-827AD0096742","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0460eec6f16f0e3514688643656cf1caab635937","datavalue":{"value":"0902.11054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364066$707856E6-829E-416A-92D3-FC7AD293AC07","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"135d8a966f73b720fd66819bb3232d63ee72d1b5","datavalue":{"value":"10.1007/BF02366510","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364066$2E2790E5-CA06-4F57-B2DA-59F47C4E24A2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5da5f54b4b947cf2ed2e7ecaa7370631a45f4fce","datavalue":{"value":{"entity-type":"item","numeric-id":1183749,"id":"Q1183749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364066$28E05923-D78E-405C-B697-DFFA5EFBBAFC","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1b023419c56b9969f2d98b08637e9b0af86a936b","datavalue":{"value":{"entity-type":"item","numeric-id":199816,"id":"Q199816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364066$B69F0778-3997-4669-9C70-052B1092F11A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"14701bb5591a3900212a7a439a0ba9af8910872a","datavalue":{"value":{"time":"+1998-12-13T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1364066$D60DEC6A-F08A-4BE4-B4A4-3F35D3199F78","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"09eaf5d469df09c9da98833f032a13ed8e983fa1","datavalue":{"value":"The author discusses three different algorithms for computing the remainder \\(W \\bmod M\\), where \\(W\\) is a \\(2n\\)-word integer and \\(M\\) is an \\(n\\)-word integer. (Words consist of a number of \\(p\\) bits dependent on the configuration of the CPU). The complexity of the three algorithms is estimated in terms of \\(T_a\\) the execution time for addition of two \\(n\\)-word integers, \\(T_m\\) the execution time for multiplication of two \\(n\\)-word integers into a \\(2n\\)-word integer and \\(T_d\\) the execution time for dividing a \\(2n\\)-word integer by an \\(n\\)-word integer, producing an \\(n\\)-word quotient.   The author claims to have studied the exponentiation of long numbers and refers to \\textit{D. Knuth}'s book [The art of computer programming. Vol. 1 (1968; Zbl 0191.17903)]. He gives a table with the number of computations to be made for different lengths of the exponents when the methods of Knuth are used. He fails to explain what the real strength of the Montgomery method is. For exponentiation of long numbers, there exist faster methods (e.g., using addition chains that can be found in an impressive number of publications) than those described by Knuth.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364066$8A9EFFAD-E535-4237-84D8-F0B74C99A7A8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364066$B0168D73-8457-4124-A9D2-DB8EECF915FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364066$31DA301C-A486-42FA-B7F3-3F6811376A84","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c77ed3f34abe9499449d02b38019891593763a2d","datavalue":{"value":"1051104","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1364066$0A5CF70F-324D-427E-A4F1-24AEBC6F1D1E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f261a5537251f4e785b0915247747a8b15afa26c","datavalue":{"value":"remainder computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364066$C2E6FC83-3E45-4738-A931-CF7E7854C001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d607627523840bd0bf4407097f29a3a99ef4a0a8","datavalue":{"value":"algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364066$F168553F-BE23-49E6-BA02-758A705C8FD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364066$205C992F-9F26-4E78-B103-BA1C8735B011","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dd226b47f85f7ad71dc0eb6328d188968b938bca","datavalue":{"value":"exponentiation of long numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1364066$CB962CA8-CC29-40F0-B037-4A31ED9B55E0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"82ee0e57d3fff232270389401ab1bbddfcf580b6","datavalue":{"value":{"entity-type":"item","numeric-id":592369,"id":"Q592369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364066$4932829E-8EF7-4421-BBAD-FA50C0E14043","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":"Q1364066$865831CB-F297-4BF3-AE2A-D315E61236FC","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"11ea612ae481e43acf6a3216a115f3a445b5f63b","datavalue":{"value":{"entity-type":"item","numeric-id":1918742,"id":"Q1918742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364066$0A0AD736-2631-4DCB-AC9D-303C845F3ADE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87cca460a73f7229e48092669139813276dc6a27","datavalue":{"value":{"entity-type":"item","numeric-id":3208051,"id":"Q3208051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364066$52FA1003-CDF7-4A2A-98F6-BD4BF39D6E73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2654d5ff3827fcd8097156ceeea53d97ceca9c2","datavalue":{"value":{"entity-type":"item","numeric-id":3347947,"id":"Q3347947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1364066$2729CD1F-33DE-4E7F-B0FB-A2086AB6708E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8c5b0cf4b92dff6a3e15126061dc7c30ba9dc4e","datavalue":{"value":{"entity-type":"item","numeric-id":4341745,"id":"Q4341745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f993c1bd8a92b1e25fbbbd4c699afda1909badd5","datavalue":{"value":{"amount":"+0.81664854","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":"Q1364066$85B823DD-EB9A-4230-9F7E-EAD80EDB4FF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6f1b5e50bfe32a5bf9f5f5e105faab5e245d4eb3","datavalue":{"value":{"entity-type":"item","numeric-id":4452169,"id":"Q4452169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea56c4d0dde2b5a36781c5f35e0e76aaa89d91ef","datavalue":{"value":{"amount":"+0.8023937","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":"Q1364066$98BB93A9-19FC-483B-AA13-6E0BF4542796","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"071d22670c7b8789879a89f1d3e6f08aa0cc1096","datavalue":{"value":{"entity-type":"item","numeric-id":1770035,"id":"Q1770035"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59efed6405b2967f54fed0f89b3378c9a99b3c21","datavalue":{"value":{"amount":"+0.79541117","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":"Q1364066$489212A2-75D5-4719-80E6-C39359162996","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5609068dd3404047c17f2914cdc6e83e23de355f","datavalue":{"value":{"entity-type":"item","numeric-id":4322313,"id":"Q4322313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"da789691659bd2fa22ccc5825f8c89b30f4c144e","datavalue":{"value":{"amount":"+0.7951019","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":"Q1364066$6342B734-9EFE-4BAA-A89F-93B00B6EE85D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44a39d2810a6a6ad80a1fe6abffbdd2be3f1e829","datavalue":{"value":{"entity-type":"item","numeric-id":3728972,"id":"Q3728972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"94c84204964d869cbe943361a7e2e512c67c9994","datavalue":{"value":{"amount":"+0.79354125","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":"Q1364066$8BB1EFB4-C59A-45DB-B797-D6E3BA6EAFD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42b15e72a144064115f6112133cbe424d413ccc1","datavalue":{"value":{"entity-type":"item","numeric-id":2745059,"id":"Q2745059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b43864f533577ca68d1d25cbdbdcd6fa7aa978f","datavalue":{"value":{"amount":"+0.79185367","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":"Q1364066$1BD2614A-AC44-46B1-ADFD-C13D05EE7BDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d06616c6e3b1b593efa6071a9274a2a2e3d28bcc","datavalue":{"value":{"entity-type":"item","numeric-id":3979695,"id":"Q3979695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79481e46bcd7e1fc8d16843dd3a29baa35231807","datavalue":{"value":{"amount":"+0.7888308","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":"Q1364066$B7D0769C-E588-40EF-BFD9-3B36CAAADDC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32c6468dc27cb60140a8bd9aa9d963a4fd0e7f28","datavalue":{"value":{"entity-type":"item","numeric-id":4411009,"id":"Q4411009"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4524e2cf4690b44e23a3bb12e797d8635506a2d0","datavalue":{"value":{"amount":"+0.78545624","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":"Q1364066$AAD4A8A6-0B5D-4297-80EF-16819B3D2220","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d37ff7514b577ef034bf9ab3405468f8d70c301","datavalue":{"value":{"entity-type":"item","numeric-id":3991119,"id":"Q3991119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1535be8747e12166b3dc6330660e06b0f7a78caf","datavalue":{"value":{"amount":"+0.78071517","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":"Q1364066$6C3A6E00-2BC8-4DF3-B061-0F65424C0764","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1364066","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1364066"}}}}}