{"entities":{"Q1640702":{"pageid":1651443,"ns":120,"title":"Item:Q1640702","lastrevid":71039322,"modified":"2026-04-13T19:05:09Z","type":"item","id":"Q1640702","labels":{"en":{"language":"en","value":"Generating pairing-friendly elliptic curve parameters using sparse families"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6889364"}},"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":"Q1640702$4AD4B884-FA94-4E5D-8367-1A7ED895DE63","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1a3265fa299d2d36008cf8b5bc7142ab20e9e1c8","datavalue":{"value":{"text":"Generating pairing-friendly elliptic curve parameters using sparse families","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1640702$0EE9ED71-DF0B-414E-8B12-02EE4A4C809B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ddb2e54ab56b2353fbb25854818a2b1cf146f38a","datavalue":{"value":"1496.94043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640702$9B729720-0CCC-46FF-BAB0-1693378C657A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"be8223d990d464c7f399efa94452f98c151451a0","datavalue":{"value":{"entity-type":"item","numeric-id":1640701,"id":"Q1640701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$01A3E48B-185A-48B0-8961-18E9C5A270D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b74a1f369afc75b4a589630fdf4792b7416540a2","datavalue":{"value":{"entity-type":"item","numeric-id":244218,"id":"Q244218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$6301B694-1774-4598-BA02-B00B37CCB5B6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52d43017492cad5b25a46de83afd30a61ffd99d6","datavalue":{"value":{"entity-type":"item","numeric-id":269100,"id":"Q269100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$A9AE5292-35D4-4900-B07C-13E959C0DB0B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8b559bb800700d5ba2a45f57085de6ba33131f78","datavalue":{"value":{"time":"+2018-06-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1640702$EA1AA76B-8D99-499E-B6F7-43FA3B71E4FE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"484b72ede08a6710ff2b2a574a4d04bced5ffe86","datavalue":{"value":"http://orbilu.uni.lu/handle/10993/39267","type":"string"},"datatype":"url"},"type":"statement","id":"Q1640702$3D9ACB17-8C97-48AA-B359-2C5BE1A5E5CE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"44bfe83f735852d98c5c825dba62de495afe42a0","datavalue":{"value":"Let \\(E/\\mathbb{F}_q\\) be an ordinary elliptic curve with Frobenius trace \\(t = q+1 - \\# E(\\mathbb{F}_q)\\) such that \\(\\# E(\\mathbb{F}_q) = hr\\) for some large prime \\(r\\). \\(E\\) is said to be pairing friendly if \\(\\log q \\approx \\log r\\) (measured by the \\(\\rho\\) value \\(\\rho = \\log q / \\log r\\)) and there exists a bilinear pairing \\(\\hat{e}: G_1 \\times G_2 \\mapsto G_T\\) where \\(G_1, G_2 \\leq E(\\mathbb{F}_q)\\), \\(G_T \\leq \\mathbb{F}^\\ast_{q^k}\\) and \\(\\# G_1 = \\# G_2 = \\# G_T = r\\) such that the discrete logarithm problem in all three groups is believed to be hard. The integer \\(k\\), called the embedding degree, should also be sufficiently small that arithmetic in \\(G_T\\) is efficient.  One method to construct pairing-friendly curves involves parameterizing the values of \\(q\\), \\(t\\), \\(r\\) via polynomial families, triples of polynomials \\((q(x),t(x),r(x))\\) in \\(\\mathbb{Q}[x].\\) Sparse polynomial families are those satisfying \\(4 q(x) - t(x)^2 = g(x) y(x)^2\\) with \\(g(x)\\) quadratic with positive leading coefficient; these are attractive because the resulting curves have large CM discriminants, providing some resistance against certain attacks on the discrete logarithm problem.  In this paper, the authors propose a novel method for constructing sparse polynomial families that combines methods of \\textit{H.-S. Lee} and \\textit{C.-M. Park} [Lect. Notes Comput. Sci. 5671, 66--77 (2009; Zbl 1250.14017)] and \\textit{R. Dry\u0142o} [ibid. 7107, 310--319 (2011; Zbl 1291.94075)]. The construction is used to produce new sparse families with \\(\\rho \\leq 2\\) and the same embedding degrees as those appearing in the literature, as well as first examples for several other embedding degrees. These families were used to produce numerical examples of pairing-friendly curves with parameters of cryptographically-relevant size, considering recent progress on the tower number field sieve algorithm for solving the discrete logarithm problem in \\(G_T\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1640702$1998E86F-2F94-429D-BEAF-096B16561FA7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2069cd334809e6c3da111c1e3f3a4186e7e970b8","datavalue":{"value":{"entity-type":"item","numeric-id":593179,"id":"Q593179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$FEAECC2B-D25F-42CC-A813-36B9556B4A7C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640702$D5EE7935-132E-4F66-9379-260531014EEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ccf6cf9514426243b160a3a06e070c16a64dbff","datavalue":{"value":"11G20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640702$F7D61B05-2D2F-4376-B21A-AB3214F21DFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"332a7ca0fc2503044cbe5299ecaa975484163791","datavalue":{"value":"14G50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640702$5CC3C3C3-E688-476F-BB27-E08EFEF316DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f00aec7b2c940e365c27808f50e4aeed90366677","datavalue":{"value":"14H52","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640702$B1C7ECE6-4201-4D2B-AB03-D0F655631FEF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"94d03ddef959979af3ea2a49e4b84c7d2f8180c8","datavalue":{"value":"6889364","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640702$77FE279E-3E56-44BD-ADBA-280D7D9B567F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b45e48c7a96fead9e75785ddc8730e431cc95dc3","datavalue":{"value":"pairing-based cryptography","type":"string"},"datatype":"string"},"type":"statement","id":"Q1640702$608F2CCE-D1DE-4F2F-8E4E-ADF3443DCFBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"658bdfbbbc7950993f0aa3d5030275200d399c43","datavalue":{"value":"pairing-friendly elliptic curves","type":"string"},"datatype":"string"},"type":"statement","id":"Q1640702$078472A6-4017-4446-AD61-C53C97ED8D5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e1625e901865382af822b1fb34ec0928933d2ce1","datavalue":{"value":"sparse families","type":"string"},"datatype":"string"},"type":"statement","id":"Q1640702$CE031DE6-E8AA-4AB1-BF72-4A26EF55D169","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"49b5234b6c5544dc8d193425e33d7d21358eb398","datavalue":{"value":"Pell equation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1640702$BB100372-D668-47F1-A66F-A1A3A8813A47","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":"Q1640702$CB8D85E0-84A2-481C-AB78-216DC883FF11","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"f03cc93bfc31e95e210dcafa31cda9b1d2a65876","datavalue":{"value":"W2789331349","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640702$8220B959-DF5C-4EAD-80AA-D6B242CAE679","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9a75847d64769d6bbafd7e17b43d562ab63b496","datavalue":{"value":{"entity-type":"item","numeric-id":5426200,"id":"Q5426200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$C20B5A4A-6491-4093-A6B4-92AF82A30386","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"728df4772915c71a20c9fd6837f07cf70a8daf28","datavalue":{"value":{"entity-type":"item","numeric-id":2572982,"id":"Q2572982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$19789643-6BA7-4B67-BFB7-2ABCD868DDB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"275a5a0a195259d45ff991e95d44301349e4cc0d","datavalue":{"value":{"entity-type":"item","numeric-id":3104749,"id":"Q3104749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$561437FA-E746-4E61-B4D3-B83FA2D41EFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"304d1bb2d6cbfa9519de2c0fe4a0e4c1f7fdcb44","datavalue":{"value":{"entity-type":"item","numeric-id":814847,"id":"Q814847"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$76E7FC72-B55B-4182-A08D-A1684842A9CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a276b57799ab29456f50bd51b0a1ab82694acb8","datavalue":{"value":{"entity-type":"item","numeric-id":2832131,"id":"Q2832131"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$FDE3148B-FE37-467F-BADD-57B62B27D89F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05fc36ac948d3a04eefce879c8dc8a587634eddc","datavalue":{"value":{"entity-type":"item","numeric-id":2850011,"id":"Q2850011"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$4EFDBB6A-C2C8-4E30-8400-4E6D340132A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb8b64d9baba0f8443178ff6e0945ad8570a2ab7","datavalue":{"value":{"entity-type":"item","numeric-id":5899268,"id":"Q5899268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$5CF23AB7-B7A7-4DE7-BC34-C8EFB38BA2DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2dc0547078e3053c4bfa5847d24a9cfb99742007","datavalue":{"value":{"entity-type":"item","numeric-id":2267367,"id":"Q2267367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$3D232F49-32BD-46F2-B4C3-20B7692217AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"13444a4425a7e7eccbc47b7b039478c984574ae8","datavalue":{"value":{"entity-type":"item","numeric-id":2467316,"id":"Q2467316"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$FB6A350D-06B5-4A08-A0D8-4F06CB68BCAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d36c5a45c36f6ef795125c0e8211b859e3f1234","datavalue":{"value":{"entity-type":"item","numeric-id":3600498,"id":"Q3600498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$3A11A7F5-70D8-4F84-AD7F-089E23F320F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"97a6b2bcc973b18f7a4add66c12c0158a9d64be1","datavalue":{"value":{"entity-type":"item","numeric-id":2835600,"id":"Q2835600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$9A32E758-91DC-4CF8-94D4-73590F821821","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef10b927323a8519921e39d5abb61a6fc04757ff","datavalue":{"value":{"entity-type":"item","numeric-id":3392903,"id":"Q3392903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$7C555993-389E-413B-A06C-8C4E2522C95F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcc371e9057f289bb2f26745b96135bab4962244","datavalue":{"value":{"entity-type":"item","numeric-id":3224984,"id":"Q3224984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$382D445C-73BA-40E3-B28A-CF1ECE4CD0DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf57b4f6586f6467c66f668bb8f70a30fd9a9dd2","datavalue":{"value":{"entity-type":"item","numeric-id":5937437,"id":"Q5937437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$F9047178-8948-4EAC-99D6-40209E0E9868","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4b639f23bb3fb1e17a3d0ac783ce908a6bd536e","datavalue":{"value":{"entity-type":"item","numeric-id":2491266,"id":"Q2491266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$7ECDCBCC-D5C9-4C0D-8374-FA8E8E642A47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0c75a6e737afa243daca278ed7cfe6484130eb2","datavalue":{"value":{"entity-type":"item","numeric-id":3081296,"id":"Q3081296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$E3746092-EC32-4821-BEDC-A626CAA1C013","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92d61ee0a95f44184912ad06638faa86dc1158eb","datavalue":{"value":{"entity-type":"item","numeric-id":3600499,"id":"Q3600499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$F7A65F33-3151-42FA-AE69-E8D4E6D98818","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6101f4eb8ca5686b820761b83a5e25fbedaca9c7","datavalue":{"value":{"entity-type":"item","numeric-id":2260508,"id":"Q2260508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$1C779716-BB2F-4384-A160-E456905DBD6F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"780cf73dbe54e0a6348c758129fe000d06542b04","datavalue":{"value":"10.1515/JMC-2017-0024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1640702$0C69205A-F234-4EB7-BDD3-5509E499FBE4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f968f64027c9284a1fe4a2927b294b94fdb21e1d","datavalue":{"value":{"entity-type":"item","numeric-id":2980869,"id":"Q2980869"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"706d930cabf971574cc2881364657fdd5e58c829","datavalue":{"value":{"amount":"+0.8185392618179321","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":"Q1640702$88D027A2-1599-4C00-AA99-809AD2AF5D94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82627731a89575950543534fdc0e9c70be56b55b","datavalue":{"value":{"entity-type":"item","numeric-id":5448547,"id":"Q5448547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9c817e19fb06d301a62a23a225854fdb5e6b78d","datavalue":{"value":{"amount":"+0.81252121925354","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":"Q1640702$04B19264-5A92-4B97-AFA7-5D95CF247F7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"25f74c37523d0308a304178d5a68b19fd5f73afa","datavalue":{"value":{"entity-type":"item","numeric-id":3104749,"id":"Q3104749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03e56ed31fba72f24c3456779802467c15737f77","datavalue":{"value":{"amount":"+0.807067334651947","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":"Q1640702$FAC58C79-9ABB-4994-A432-B5E66112379B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efa2a9f38c9c1136e0686e29946eb845b9afa6ce","datavalue":{"value":{"entity-type":"item","numeric-id":3600499,"id":"Q3600499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17725c7a13ef691545dc9c684ed1fbdbbaab4e74","datavalue":{"value":{"amount":"+0.7989180684089661","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":"Q1640702$80C2B1E9-9A46-4486-8383-E9C51C9E8A6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9154b4aa7c34a59142343cd99ac0ca6c65e02c50","datavalue":{"value":{"entity-type":"item","numeric-id":1949237,"id":"Q1949237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"24c04259629c664ef84b8b04dc18b44f1ac4e33b","datavalue":{"value":{"amount":"+0.7965472936630249","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":"Q1640702$A91BA73D-F98B-4D87-82DA-80B6EBB02174","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"bee1ddd2bb542a0e64ca96574e4fab1bba361385","datavalue":{"value":{"entity-type":"item","numeric-id":57074,"id":"Q57074"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1640702$897DEEDD-8B8F-430E-A405-FAF2CFFE2D80","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Generating pairing-friendly elliptic curve parameters using sparse families","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Generating_pairing-friendly_elliptic_curve_parameters_using_sparse_families"}}}}}