{"entities":{"Q2730746":{"pageid":2741485,"ns":120,"title":"Item:Q2730746","lastrevid":41940996,"modified":"2025-05-16T18:57:37Z","type":"item","id":"Q2730746","labels":{"en":{"language":"en","value":"Polynomial representations of the Diffie-Hellman mapping"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1624941"}},"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":"Q2730746$FEA80EBA-83E7-4242-8A0F-72B525E600CF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"10ab381336e077c152329682f94baa48d0ba60cf","datavalue":{"value":{"text":"Polynomial representations of the Diffie-Hellman mapping","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2730746$34D641CD-864C-4505-A233-7F8F2703FCB7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3862235c31222a65a75b2e284d7c26032f3fc730","datavalue":{"value":"0974.11040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2730746$050B5730-31DE-4D52-B9D9-53F7A4BFAC2B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ab65bf3dd9e2b665fe3a38c01f451ab58b1f4338","datavalue":{"value":"10.1017/S0004972700019547","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2730746$2899A114-8651-40CF-9530-78E6CF68EDB2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e37c008e3c89b503a5cd9e8fbce961cf3e951113","datavalue":{"value":{"entity-type":"item","numeric-id":949061,"id":"Q949061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2730746$1B44DB9C-C5C6-4FAA-A1CB-48DA03CAD814","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"165c8921a441245575fe00da025ab28703ff633a","datavalue":{"value":{"entity-type":"item","numeric-id":240100,"id":"Q240100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2730746$4C8C702E-B2ED-4FAB-9A61-81676D948D1A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6b34985c280ac92a95e78ca54439c7119e4907e7","datavalue":{"value":{"entity-type":"item","numeric-id":2716953,"id":"Q2716953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2730746$2DB24520-7AFD-4D1E-8F4D-D785BB2951DF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cff48275765814590658d506aafb5ce41ac2a492","datavalue":{"value":{"time":"+2001-12-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2730746$1EC665B0-A615-44C2-99E3-38DD918D685E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5005488ac12471348bfecb95099a57fd4da722ac","datavalue":{"value":"11T06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2730746$D57E26DB-34CF-43BD-8D95-DB47F33A3E4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"dcefd1e200eae54420c5080733f6b5a349da9f6a","datavalue":{"value":"11T71","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2730746$703A6EA5-1204-4A80-BA23-04C8F6857107","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2730746$0F2423DD-D1E5-48BE-8E49-60A8B4134F63","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5cadb25f04a66a053f247d4112583ddc16569e69","datavalue":{"value":"1624941","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2730746$4948E133-9AA2-4AA1-B528-7EAF3ECE3BB1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d54d97c9d74a7974164bd27bc3725f50a6bd71c8","datavalue":{"value":"cryptography","type":"string"},"datatype":"string"},"type":"statement","id":"Q2730746$A59B1254-FEF3-4568-8A59-EB8083421C1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7dcd7e259b40e667d7b72e1cb4911314d111dce1","datavalue":{"value":"Diffie-Hellman key exchange","type":"string"},"datatype":"string"},"type":"statement","id":"Q2730746$D5112E33-FF04-45A7-BDA7-4847A1938769","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d2d0efcf778ef7426ebb4ec2bff58367598cf33e","datavalue":{"value":"Diffie-Hellman decision problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q2730746$72CE8616-0D04-49CF-B9A3-4BE3AE5B94FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d12c3f3bd0bfd35dcf35835c7c8fa1eed01a43f","datavalue":{"value":"complexity lower bounds","type":"string"},"datatype":"string"},"type":"statement","id":"Q2730746$9C53B417-885B-40E7-AA7D-C84D139E1A27","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":"Q2730746$50B86624-6C83-4949-9775-5EBA5EB7C1D6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6652403293c6654d588a742655f16bc1d60a01d","datavalue":{"value":{"entity-type":"item","numeric-id":1573770,"id":"Q1573770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2730746$C547135F-0F9E-4AE0-B15B-71A4CF6716B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a90446824978e237bf1b1d3f3cba3d9863c5009","datavalue":{"value":{"entity-type":"item","numeric-id":2770462,"id":"Q2770462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2730746$49330BB0-5D93-49A6-BE90-A601B6B918E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b32ea21029cd9f47fd951ad3b69342c8e712c0ac","datavalue":{"value":{"entity-type":"item","numeric-id":1976038,"id":"Q1976038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2730746$175A91BA-5194-40E8-826F-2CA23C5AD6E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14e02e09e800ac4f5ffdea3daa03eb47261bc455","datavalue":{"value":{"entity-type":"item","numeric-id":4268814,"id":"Q4268814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2730746$4608D6C3-C906-4CF0-9A97-B13EFBD7920F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"737d0e769bc06912eb5b7c81a62e7bbb676b4bc4","datavalue":{"value":{"entity-type":"item","numeric-id":1276548,"id":"Q1276548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2730746$C5A83ECD-EF21-4131-9249-6D9C6B6B0508","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7ef81db7bcc8e593c419a126422ae8731f8ce5c2","datavalue":{"value":{"entity-type":"item","numeric-id":2777722,"id":"Q2777722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d4b3ed6bab82746f61accea5c3fef33dae9d7f3","datavalue":{"value":{"amount":"+0.82950485","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":"Q2730746$BD4B7CAB-A00A-4809-83F7-7CE80FD840DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07a544e58b9fc7b8256a20f8befbb045ea831c78","datavalue":{"value":{"entity-type":"item","numeric-id":4824817,"id":"Q4824817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7c59b4e7db2d9d3502e602486f33627dd50039a","datavalue":{"value":{"amount":"+0.7792332","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":"Q2730746$C39403B5-6004-475E-924D-ECB1027205AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09b4403f7db788907457d05cba64fb099413a436","datavalue":{"value":{"entity-type":"item","numeric-id":1755993,"id":"Q1755993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1922e32763009e263e4a3dceff3d96e4e4aff827","datavalue":{"value":{"amount":"+0.74025786","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":"Q2730746$6025458C-3D1E-4596-BB52-5216C227D5EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22839b168abc2b5d2f169eef84b0fb7116321820","datavalue":{"value":{"entity-type":"item","numeric-id":4552260,"id":"Q4552260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b50465760395263df4e4a7576405402eb214a71d","datavalue":{"value":{"amount":"+0.7173355","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":"Q2730746$6484D1A6-9DC2-4F9F-B928-F46A6A990C10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fb4c2e14c6cc374344c471381a9b81d009194dc2","datavalue":{"value":{"entity-type":"item","numeric-id":4426684,"id":"Q4426684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"93642beb764f02976256b25f07fea2b028d34ba1","datavalue":{"value":{"amount":"+0.71715176","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":"Q2730746$F9D5F8EB-6453-4B85-BADC-4A1B884DDF86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"563c9ec3167c030a6319b9c840fadc38eb9cf5db","datavalue":{"value":{"entity-type":"item","numeric-id":1861170,"id":"Q1861170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d450e975682c36d85a210ae5222e581671f97d65","datavalue":{"value":{"amount":"+0.7059207","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":"Q2730746$45E1ADB1-F1B4-413C-9B28-B552600EAE5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8518ceb326edaa165fc127eeb96f5e4895694b7","datavalue":{"value":{"entity-type":"item","numeric-id":4250165,"id":"Q4250165"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2c00b6c941f0b9a2e2080e851617b4a4a4001c4","datavalue":{"value":{"amount":"+0.70333004","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":"Q2730746$D66874AF-DC82-400D-919B-7DAE71AA2F84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0964a1372e04086390f6a81c0c49e67f7206993","datavalue":{"value":{"entity-type":"item","numeric-id":3769011,"id":"Q3769011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0319fadae354fbdc221981a1f63c1cbe10d14751","datavalue":{"value":{"amount":"+0.6982679","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":"Q2730746$44B585A4-0466-42BF-897F-1942062E0E7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eb6b88207bbcc7701b065dccff95ff585b111b3e","datavalue":{"value":{"entity-type":"item","numeric-id":1573770,"id":"Q1573770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee4f956e58fd3f91d761105b17c7d708eba4afc3","datavalue":{"value":{"amount":"+0.6924323","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":"Q2730746$A1629F62-8F6A-405A-A10B-5DAC48E324AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7185a038fd756c2a80db07821edf42bdcf7caed","datavalue":{"value":{"entity-type":"item","numeric-id":4941862,"id":"Q4941862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02df8f5f5335e281e9a8efa9a3878c6977fe6357","datavalue":{"value":{"amount":"+0.6897097","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":"Q2730746$01F5DA84-78EF-4FE6-ADBF-BCD456D019FE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"baab2e59591ab753eafe15a240c5c335f9189efb","datavalue":{"value":"Let \\(q\\) be a prime power, \\(\\mathbb{F}_q\\) be the finite field of order \\(q\\), and \\(g\\) be primitive element of \\(\\mathbb{F}_q\\). The Diffie-Hellman key exchange is based on the fact that no easy representation of the Diffie-Hellman mapping NEWLINE\\[NEWLINEf(g^x,g^y)=g^{xy} \\quad \\text{ for }1\\leq x,y\\leq q-1NEWLINE\\]NEWLINE is known. For breaking the Diffie-Hellman cryptosystem it would be sufficient to have an easy polynomial satisfying \\(f(g^x,g^y)=g^{xy}\\) for all pairs \\((x,y)\\in {\\mathcal W}\\) of a large subset \\({\\mathcal W}\\subseteq [1,q-1]^2\\). NEWLINENEWLINENEWLINEThe authors obtain the following result extending the technique in \\textit{D. Coppersmith} and \\textit{I. Shparlinski} [J. Cryptology 13, 339-360 (2000; Zbl 1038.94007)]: NEWLINENEWLINENEWLINELet \\({\\mathcal W}\\subseteq [N+1,N+H]^2\\) with \\(2\\leq H\\leq q-1\\) and let \\(f(X,Y)\\in \\mathbb{F}_q[X,Y]\\) be a polynomial such that NEWLINE\\[NEWLINEf(g^x,g^y)=g^{xy} \\quad \\text{ for all } (x,y)\\in {\\mathcal W}.NEWLINE\\]NEWLINE If \\(|{\\mathcal W}|\\geq 10 H^{8/5}\\) then we have NEWLINE\\[NEWLINE\\deg(f)\\geq \\frac{|{\\mathcal W}|^2}{128H^3}.NEWLINE\\]NEWLINE They obtain also results on the degree of polynomials \\(F(X,Y,Z)\\) over \\(\\mathbb{F}_q\\) satisfying \\(F(g^x,g^y,g^{xy})=0\\), where \\((x,y)\\) runs through a certain subset of \\([1,q-1]^2\\).NEWLINENEWLINENEWLINEReviewer's remark: The authors' first result and the reviewer's result in [Bull. Aust. Math. Soc. 64, 475-477 (2001)] complement each other. In particular, the latter paper contains nontrivial results for certain subsets \\({\\mathcal W}\\) of cardinality smaller than \\(10H^{8/5}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2730746$5FFAABFB-66A3-401D-9CCD-9E58278C33F1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"89409f7728d198a35866d69fd5f11282a2236b52","datavalue":{"value":{"entity-type":"item","numeric-id":171423,"id":"Q171423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2730746$FA97DFEB-F3C9-4BDF-A4C3-976529C0BD8B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2730746","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2730746"}}}}}