{"entities":{"Q1766871":{"pageid":1777613,"ns":120,"title":"Item:Q1766871","lastrevid":43314239,"modified":"2025-07-24T15:30:55Z","type":"item","id":"Q1766871","labels":{"en":{"language":"en","value":"MOV attack in various subgroups on elliptic curves"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2140265"}},"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":"Q1766871$425CA6A8-79EB-4611-B7A0-B5E47357446F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"72ef68ab3d9084f46a54d5aa7a5215db7f5fbf92","datavalue":{"value":{"text":"MOV attack in various subgroups on elliptic curves","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1766871$5117AE04-03DD-4F9E-A95D-812D8FF8134F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"32a6b36137ac2f6fa59f21d28a44440095ea0cd9","datavalue":{"value":"1072.11094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1766871$5E1951CD-4212-4E4F-8597-CA49CC618B01","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e5a736319355d31e13239bc37a3f0fcf5a6f069f","datavalue":{"value":{"entity-type":"item","numeric-id":168881,"id":"Q168881"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766871$3801C5F5-FCA8-46D3-B3C0-AB50FC589F9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eea13ea148be03d88ede354d4d7f6c2d4d5793b9","datavalue":{"value":{"entity-type":"item","numeric-id":1766870,"id":"Q1766870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766871$F888F886-93AF-4959-B291-07F8DD17DF08","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":"Q1766871$5D9669B7-0853-4B90-9D22-4395A58483B8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2b9e892f1ffa11a66ee26af1e2c8bc1a173eacc","datavalue":{"value":{"entity-type":"item","numeric-id":226831,"id":"Q226831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766871$DF0264B2-CFB2-44B5-B721-9B8A5CD41765","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"98babedc0aaf742c2c52517bbf9b1598ad1f8c08","datavalue":{"value":{"time":"+2005-03-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":"Q1766871$13799F4D-B741-4B98-A31C-D4D434F40B62","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"18cd5d39fd25c449f62865617b7fec54099e78e5","datavalue":{"value":"\\textit{A. J. Menezes, T. Okamoto} and \\textit{S. A. Vanstone} [IEEE Trans. Inf. Theory 39, No. 5, 1639--1646 (1993; Zbl 0801.94011)] showed how to use the Weil pairing to map discrete logarithms in the group of points on an elliptic curve over \\(F_p\\) to discrete logarithms in the multiplicative group of \\(F_{p^k}\\) where \\(k\\) is minimal such that the group order \\(\\#E(F_p)\\) divides \\(p^k-1\\). Clearly, \\(k\\) depends on the curve and in particular it is always less than or equal to 6 for supersingular curves. This result is interesting for cryptographic applications as the DLP in finite fields can be solved with subexponential algorithms. \\textit{R. Balasubramanian} and \\textit{N. Koblitz} [J. Cryptology 11, No. 2, 141--145 (1998; Zbl 0978.94038)] showed that for randomly chosen curves of prime order (in particular not supersingular ones) over prime fields the probability of having a small embedding degree \\(k\\) is exponentially small.  The present paper extends this result to deal with more general elliptic curves over prime fields \\(F_p\\) by not restricting the considerations to prime group orders. This is of practical relevance since usually small cofactors are allowed. They estimate the probability that \\(k\\) is smaller than a certain \\(K=O(\\log p)\\) for the following cases: the full order \\(N=\\#E(F_p)\\) divides \\(p^k-1\\), the order of the maximal cyclic subgroup divides \\(p^k-1\\), the order of the maximal prime order subgroup divides \\(p^k-1\\) and finally that for all prime order subgroups the corresponding necessary \\(k\\)'s are simultaneously smaller than \\(K\\). The latter corresponds to the approach of solving the DLP separately in the subgroups and then combining the result via the Chinese Remainder Theorem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1766871$9F442662-F032-4747-B6D7-B9A4DF9D4988","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"05d313fafb9c8d843f17d1fd39b688f4cfaf3dbe","datavalue":{"value":{"entity-type":"item","numeric-id":701119,"id":"Q701119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1766871$FEB8E855-7BFC-4EBC-8E1C-B4A2631EE252","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"dcefd1e200eae54420c5080733f6b5a349da9f6a","datavalue":{"value":"11T71","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1766871$2F459B72-99F2-43BC-9C61-9B6931823D73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7c2eb42a01c6d1209538ab1ef910c81f1a87b7ac","datavalue":{"value":"11N25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1766871$BEFA2791-05B2-4C15-862C-5BCDED20FBA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f00aec7b2c940e365c27808f50e4aeed90366677","datavalue":{"value":"14H52","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1766871$38F3ED56-A8CC-41A7-BB2E-5F0643E0117B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8db1d472c2697ed395af803fe864b68589ebbbda","datavalue":{"value":"2140265","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1766871$44BAE2E2-736A-4FDC-835B-83857B8F3C41","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb5f428237574c728e27af587accf727feffc0a7","datavalue":{"value":"MOV attack","type":"string"},"datatype":"string"},"type":"statement","id":"Q1766871$B9BAE328-19EB-447D-930A-2336D3AFAC14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da1fcf8634dffbef5ab53f82304a07bf90038678","datavalue":{"value":"elliptic curves","type":"string"},"datatype":"string"},"type":"statement","id":"Q1766871$1056ECDD-8619-4E98-A7C3-4F581FDE65FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c4634d327f33fde156fde3d8ac03e8efeff1340f","datavalue":{"value":"embedding degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1766871$AF600AE5-5ADE-469D-902A-946DD4A73F25","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":"Q1766871$5B8308D1-E053-4583-8AEE-9D22FB4E8169","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ca703e3f42ae3d7bcc4f6235edf2f516cde9ed6","datavalue":{"value":{"entity-type":"item","numeric-id":3149772,"id":"Q3149772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c137976ebb7ce81a7eda5a57fac0acc3dbfd496","datavalue":{"value":{"amount":"+0.74652374","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":"Q1766871$8818071F-5AA3-4C68-B924-BE9976D1F3C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"646c8378671dcf8064596a04687221e9a972dc38","datavalue":{"value":{"entity-type":"item","numeric-id":5429245,"id":"Q5429245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"00235e9a2d75b59bc7d614c725dcc0edb387b9d7","datavalue":{"value":{"amount":"+0.74529296","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":"Q1766871$FD0332BB-4078-4B90-819D-27EAF0336EA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e657f2a0b168885c90c24fc57fa5cfb508ac6ce","datavalue":{"value":{"entity-type":"item","numeric-id":4250762,"id":"Q4250762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61f646f99310fa48e852aa8c204d18d0d54bfb64","datavalue":{"value":{"amount":"+0.74402934","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":"Q1766871$1B3B525F-FA36-4194-9E3B-B0F45D3E6EC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6f7ff51567c6bd8911a93cad4cf30c4b5b38b32","datavalue":{"value":{"entity-type":"item","numeric-id":1126894,"id":"Q1126894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0cb856beaf4c84076a3c208458f4d8d691b0534","datavalue":{"value":{"amount":"+0.74256545","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":"Q1766871$11473460-86D6-4CE5-AAC4-E0BBBCEEDD2B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2ffb6cdd7185c7a336033687aca41b2d3cc7647a","datavalue":{"value":{"entity-type":"item","numeric-id":4314052,"id":"Q4314052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"440469cb1d24c822d5714505054430b18361b041","datavalue":{"value":{"amount":"+0.72528416","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":"Q1766871$9ACDB637-4248-4A7F-BA28-EEAA102E80E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60ee8b8c6f8d3eb3420679b28e786d5c753fbbb4","datavalue":{"value":{"entity-type":"item","numeric-id":3044320,"id":"Q3044320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3061a1b4f6ef73069848c14c0efe343dd656bc3c","datavalue":{"value":{"amount":"+0.72023493","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":"Q1766871$7449DDE1-DFA9-480C-AFCB-F4A621475018","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5040b859bab5e81a610c5048d236a2fc2ec044d","datavalue":{"value":{"entity-type":"item","numeric-id":4372702,"id":"Q4372702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79f8434c983f0cd28a212740e3dd3a7933c5fef5","datavalue":{"value":{"amount":"+0.7160357","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":"Q1766871$D74002AC-469A-47AF-91AD-0F41C9FFDF69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ca8be9b1b0eea1d085db5f5d83b08fdc2543c60","datavalue":{"value":{"entity-type":"item","numeric-id":5451062,"id":"Q5451062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18b12c34e7bb2c2de214fcec3b1e72c2e4346ed2","datavalue":{"value":{"amount":"+0.7125834","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":"Q1766871$29A0B548-D8EC-40E9-A6B9-992E97666695","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b89249edaf0e7b7000334429fdfcadcdce3c7340","datavalue":{"value":{"entity-type":"item","numeric-id":4037476,"id":"Q4037476"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45f133e26d4a44316bf55ce2a59c6324720b0415","datavalue":{"value":{"amount":"+0.7084227","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":"Q1766871$46369631-0E68-4CCC-B2E4-D2BCCCBE842C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b058eb999e8b2c6365a428611587babe35ca5ea","datavalue":{"value":{"entity-type":"item","numeric-id":5426200,"id":"Q5426200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86c8a81248511f37b56b1a48c2383dca8de6649c","datavalue":{"value":{"amount":"+0.7071469","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":"Q1766871$16F13B26-3640-41C3-9DBB-5950480B5F2D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1766871","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1766871"}}}}}