{"entities":{"Q1898116":{"pageid":1908858,"ns":120,"title":"Item:Q1898116","lastrevid":74249706,"modified":"2026-04-14T19:11:04Z","type":"item","id":"Q1898116","labels":{"en":{"language":"en","value":"Efficient checkers for number-theoretic computations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 799032"}},"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":"Q1898116$FBDDA1C7-96F8-4A84-9388-5952C155A972","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"23314e0317bc76c02552ec16b8b8de028c257210","datavalue":{"value":{"text":"Efficient checkers for number-theoretic computations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1898116$DBA99358-E4B7-4487-81EA-D0F4820EA071","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4a0e865afc664038cea590a835051b337dd0f334","datavalue":{"value":"0840.11053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898116$224E0B87-1EE6-4C45-98F4-0C4A98901309","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"31c79abbc7ed3d5d95d01b51efb598bc0bd07ef4","datavalue":{"value":{"entity-type":"item","numeric-id":207153,"id":"Q207153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898116$C900D01E-97FF-4B4F-B3B3-E91C3AA6D4B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3998c2440cb0250af00ba4710923a28084d2922b","datavalue":{"value":{"entity-type":"item","numeric-id":1082811,"id":"Q1082811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898116$97B3790D-93A1-4894-ADBA-7FF6C13B5AAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b59278e4cd513aeb5196a0ab981c20a062f91a71","datavalue":{"value":{"entity-type":"item","numeric-id":1898115,"id":"Q1898115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898116$F50B77AA-B893-4532-B10F-E454AFA92225","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898116$00002EFF-CD64-4232-A187-BCFE693FCDAF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"b3795412637b3de2331b3ff6904fdddc88e823af","datavalue":{"value":{"time":"+1996-07-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1898116$49CDFABD-12AA-4458-B4F1-C339A83F3187","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2b04a53f7c089d6eead9f7e63639ecfddec25d35","datavalue":{"value":"Program checkers, as proposed by \\textit{M. Blum} [Designing programs to check their work (Tech. Rep., ICSI, UC Berkeley) (1988)], embody a probabilistic approach to the problem of program correctness. Let \\(P\\) be a given program that purports to compute a function \\(\\pi\\). Each time \\(P\\) is run on an input \\(d\\), the checker for \\(\\pi\\) is also run. It interrogates \\(P\\) with inputs that may differ from \\(d\\), and produces a decision on the correctness of the result of the call \\(P(d)\\) that is guaranteed within a small probability of error. The complexity of a checker is a bound for the number of calls to \\(P\\) it engenders and for the time complexity of the rest of its computation, as a function of the input size \\(n\\).   The present paper describes an efficient checker for the greatest common divisor problem of complexity \\(O(1)\\), and one for modular exponentiation of complexity \\(O(\\log n)\\). The latter operation is an important one in the RSA cryptosystem. It is also shown that, under a certain hypothesis whose validity is an open problem, an \\(O(1)\\)-checker for modular exponentiation exists.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898116$5AB7B011-EB2D-4B37-B65C-6694F6E87EE6","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"da821cffe7e96269025b8e6783fb2f14735ef92b","datavalue":{"value":{"entity-type":"item","numeric-id":685523,"id":"Q685523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898116$1F326069-B81F-4C62-97B8-2B435F990D0A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"17e0a295200b605f2e49c5f6e8394a8f386cbcf7","datavalue":{"value":"11Y99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898116$BC4F23A8-4BE4-4628-BBCD-8D2FBCFD2B5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898116$19A58E16-663D-49F6-AA90-3B8E20CFE0B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898116$A7872F1E-EC40-4634-84AF-223AAA6EF77D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5f6f2e73ebe360c69b5f99d6be8e06f538650497","datavalue":{"value":"11A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898116$81B43BAB-6C49-4001-B1A7-D669D42FF2E5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dee046794cdc8265e3d8daba7ee7d6e743437f53","datavalue":{"value":"799032","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898116$4CAFADAA-0FA9-4CC5-8711-B865A8286AD5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0858f73514b172b106fa6a1a3d159d0f24057ff","datavalue":{"value":"program checkers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898116$F8D78407-3A1E-4751-BC7D-4DB84270B4F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898116$6FE59CE9-6639-47A3-B7E7-57C9BE3B634B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac88c7c4ceb79c868083defb73e33bb7e3d89ba0","datavalue":{"value":"greatest common divisor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898116$87A4E4E8-1BBC-491F-85F7-D5AB45D048DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8386d80d4ac63103a55c28ce581850c79d5a9342","datavalue":{"value":"modular exponentiation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898116$24CD8234-BCF1-4322-9B05-C4083F1E890B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a7495423acd742d23f5e6c277ddc702efc21d98","datavalue":{"value":"RSA cryptosystem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898116$83F81EC2-6D6D-477F-B402-25AA8A1F80E7","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":"Q1898116$24952F61-D134-4260-8AFA-A8A34E0FEA2C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"453422af50de041f43dbf4dbf5eb887cf24e056c","datavalue":{"value":"https://doi.org/10.1006/inco.1995.1125","type":"string"},"datatype":"url"},"type":"statement","id":"Q1898116$1DCEF518-6D1D-41C7-BD72-FF72BD2C05DB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"5b06c060a7bae34270d7dd4600204d46f15bed1f","datavalue":{"value":"W1968223186","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898116$83C4F595-612A-4406-B624-5CDFE37403B8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0dc6301988ceb5029e55109cf2dc9ad9bfd64ed1","datavalue":{"value":"10.1006/INCO.1995.1125","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898116$E19A5601-8C80-4A29-B5D9-1589EE4FB8CD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da961021e47af7ab534ac9970550e8d9619c41f5","datavalue":{"value":{"entity-type":"item","numeric-id":4369864,"id":"Q4369864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30f9a07053f1b9aa7a39ef8fc1a4f95b656f2b18","datavalue":{"value":{"amount":"+0.8493439555168152","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":"Q1898116$C75108D3-F23D-497C-8692-AD2B0E420660","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8cf8ab86bdcc14941d203a39051cd32c6d702bc7","datavalue":{"value":{"entity-type":"item","numeric-id":1911462,"id":"Q1911462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30f9a07053f1b9aa7a39ef8fc1a4f95b656f2b18","datavalue":{"value":{"amount":"+0.8493439555168152","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":"Q1898116$BAEBE122-3577-4830-847D-AD88FD4762CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d2a8ef194b4e6ba8da60b91b2212de9b57f439f","datavalue":{"value":{"entity-type":"item","numeric-id":3212297,"id":"Q3212297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9066fc18bff59bd84f3dae790fb602b823b90acf","datavalue":{"value":{"amount":"+0.8034396171569824","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":"Q1898116$84EF5F01-53A8-4255-AEA5-50DB47360954","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d8b7bcb6089ce4741916f7b6f079b879f25f1670","datavalue":{"value":{"entity-type":"item","numeric-id":4036561,"id":"Q4036561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bfd5ea7b06de1dab8453dcc940ee002d752e10cd","datavalue":{"value":{"amount":"+0.7553601861000061","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":"Q1898116$57170ADA-1833-4C28-8F22-FF1D83E405FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2c3f657ec332cd0b898aa0402731014466714d0","datavalue":{"value":{"entity-type":"item","numeric-id":1317490,"id":"Q1317490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a960020347aa0050ac52da247453307f5dcded3","datavalue":{"value":{"amount":"+0.7553540468215942","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":"Q1898116$87FBB738-6223-416E-BE83-B44B359E9B9B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficient checkers for number-theoretic computations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficient_checkers_for_number-theoretic_computations"}}}}}