{"entities":{"Q1898267":{"pageid":1909009,"ns":120,"title":"Item:Q1898267","lastrevid":47353645,"modified":"2026-01-01T11:55:33Z","type":"item","id":"Q1898267","labels":{"en":{"language":"en","value":"Complexity of a determinate algorithm for the discrete logarithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 796784"}},"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":"Q1898267$BE65370B-8431-4828-BFEB-94572CABB163","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2abb453af04081870ff02b1f469900b6b6e13358","datavalue":{"value":{"text":"Complexity of a determinate algorithm for the discrete logarithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1898267$0D3ED194-DC2A-41DD-92F0-541C9C3DBF72","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"911affe3b107717192fd3dd8b28d6dd8cb1ec55f","datavalue":{"value":"0831.11065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898267$10B3A4E3-CAFE-49D9-A437-8C198185C463","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b2f9fbc3e39c56295c6c064285ce9728e6358d63","datavalue":{"value":"10.1007/BF02113297","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898267$78FFD5AC-9049-4B13-97EC-AB413E06BF11","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f8bde4fc4b906a78376932397279b30c602ebc8a","datavalue":{"value":{"entity-type":"item","numeric-id":594130,"id":"Q594130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898267$A57539AA-200B-47F8-92BB-EABD66DA21C5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"00de3e6b6cfff0576fe0e1d6bc63c05579d2cb43","datavalue":{"value":{"entity-type":"item","numeric-id":173953,"id":"Q173953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898267$157E144C-CF65-43F8-B1BB-AB29474A8468","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e5f9c9b4aa626b50a4947c04949645549a257c36","datavalue":{"value":{"time":"+1995-09-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1898267$1C7C2FF3-B96A-445E-848C-2C30DFCDD9A5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bb277cdb311ec66565fc34efa184d1894554152d","datavalue":{"value":"Let \\(\\langle G,\\cdot \\rangle\\) be a finite group and \\(g, a\\in G\\). Let \\(g\\) be an element of order \\(t\\) and \\(n\\), \\(k\\), \\(m\\) be natural numbers. Consider the equation \\(g^x= a\\), \\(x\\in \\mathbb{N}\\). To determine \\(x\\), suppose \\(km\\geq t\\) and compute the products \\(a, ag, \\dots, ag^{m-1}\\) and \\(g^m, g^{2m}, \\dots, g^{km}\\). Then if, for some \\(i\\), \\(j\\), \\(g^{mi}= ag^j\\) then \\(n= mi-j\\) is a solution. This is the well known Shanks baby-step, giant-step algorithm which requires on the order of \\(2\\sqrt {t}\\) multiplications. It is established in this paper that, among a certain class of algorithms, this algorithm is optimal in a certain sense.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898267$24BF3BD8-EABD-40EB-9D77-2C075CCB7B24","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898267$CA3DAB90-9926-41AA-8E0D-53171585D5D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dcefd1e200eae54420c5080733f6b5a349da9f6a","datavalue":{"value":"11T71","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898267$7E0AA89E-B495-43D4-96CB-5500CD4ECBB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"157305dfd5c4a00203c592f58c4b16e8bc6d182b","datavalue":{"value":"11T30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898267$F96A996B-85FC-493E-81A8-2103BDD83FFD","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c4a46111ff017514711d636120b663a813ecb9d4","datavalue":{"value":"796784","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1898267$7690D834-7C97-47A4-B03B-9E69F60D2285","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e15dc5d5d8e3bb765a1ee2bbb32931074cb8b74","datavalue":{"value":"discrete logarithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898267$9163BB0E-93E5-46E0-A2F4-AEF9B6AD2969","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ac07c7d6c5cdc2dbc4590f3ecbac0ebb59196bea","datavalue":{"value":"finite fields","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898267$4BA38168-0EC8-42FD-B467-ABCBACF07EAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d54d97c9d74a7974164bd27bc3725f50a6bd71c8","datavalue":{"value":"cryptography","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898267$DB8C8117-DCD3-412E-AB29-876DC6EE57A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d68dd39e6b1463f1b0a138c7b3b44fbde3953ad","datavalue":{"value":"Shanks baby-step, giant- step algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1898267$7BC4881B-95F7-4FC1-9F1E-A98511A5BDC4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d55353e7bc3d0614b86e9af78e82c119a2d0a9e0","datavalue":{"value":{"entity-type":"item","numeric-id":677137,"id":"Q677137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898267$0AB66F35-F453-47FC-9C59-68458C0EEE81","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":"Q1898267$F1C2100F-4CAF-409E-8376-28CD29F7B212","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d2c34527c083683e608b13a190f76d58d59818e","datavalue":{"value":{"entity-type":"item","numeric-id":4746796,"id":"Q4746796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898267$762615B4-3AF4-446B-BBFF-C16D3555B7DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52fb796594aa32d99f4e818726f7bf89a9fc8d31","datavalue":{"value":{"entity-type":"item","numeric-id":3765876,"id":"Q3765876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898267$0D4B98B7-A6DC-4FC7-87BB-ABB7B07560A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a62cdec956f493e0e23da573b7623b64aa5e4b5","datavalue":{"value":{"entity-type":"item","numeric-id":4154061,"id":"Q4154061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898267$39F9E91D-22DC-40CA-A55D-5558DA734D35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f3fbc1309a974a811915b3068df7d148fb256f9","datavalue":{"value":{"entity-type":"item","numeric-id":3320493,"id":"Q3320493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898267$CC9F760D-DC4A-4004-A94C-17B7F59C8616","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d971207323fc32c252b42f869ff1c8bcd7ecda2","datavalue":{"value":{"entity-type":"item","numeric-id":3216753,"id":"Q3216753"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1898267$6BBCA6E2-57AB-4E00-82F6-2CF7A91B1376","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20f6b502d0b8c0ff06edc8d3e91dcac17892eae3","datavalue":{"value":{"entity-type":"item","numeric-id":4856880,"id":"Q4856880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31ede7a76d4473141797ffa95cfbc02fe3e43456","datavalue":{"value":{"amount":"+0.8195509314537048","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":"Q1898267$41977C95-B971-4957-BEF9-B37746A6779A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15dcd2c3fbc8f31b39da00e51ef18a99175b8be4","datavalue":{"value":{"entity-type":"item","numeric-id":3137444,"id":"Q3137444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7eceb85610f310309f499285ac2f204296d63cd4","datavalue":{"value":{"amount":"+0.8191433548927307","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":"Q1898267$F0C9DA53-DBBF-4183-B363-9A92285A66B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37e91f11a641a87e0adc20a57da6d70a024ff27b","datavalue":{"value":{"entity-type":"item","numeric-id":2765016,"id":"Q2765016"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21e17c79fa99d56da53cef015e9dc64a513dc6ee","datavalue":{"value":{"amount":"+0.8144346475601196","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":"Q1898267$F057AA27-FB7C-4693-96C6-BEAFEF9F83BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6777db9f72a883d7b92b4f0ec1ae2d318f342acf","datavalue":{"value":{"entity-type":"item","numeric-id":3360980,"id":"Q3360980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f1d555f40fc2459e6a8e4f69001d43594c3811b","datavalue":{"value":{"amount":"+0.8134928345680237","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":"Q1898267$BD86D413-B870-45A4-A049-7C02D179F163","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c662d5b4841952c7b673f6bcbe0bf71691960fcf","datavalue":{"value":{"entity-type":"item","numeric-id":2985808,"id":"Q2985808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"299d09d94b403b60a51c7ec6be06fadb5086ee6a","datavalue":{"value":{"amount":"+0.8106623291969299","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":"Q1898267$CC89F0CC-F1F6-4B28-9D57-A9580FC7BB3C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1898267","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1898267"}}}}}