{"entities":{"Q725962":{"pageid":727811,"ns":120,"title":"Item:Q725962","lastrevid":53157578,"modified":"2026-01-24T08:34:40Z","type":"item","id":"Q725962","labels":{"en":{"language":"en","value":"\\(\\mathcal{NP}\\)-completeness of the Goppa parameterised random binary quasi-dyadic syndrome decoding problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6912656"}},"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":"Q725962$E9380BA1-DCA9-4C3F-B8AD-405C8B9FAFC2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3647b87eda5cdab91054813c20c29dd200bd1edf","datavalue":{"value":{"text":"\\(\\mathcal{NP}\\)-completeness of the Goppa parameterised random binary quasi-dyadic syndrome decoding problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q725962$A9FD5A02-78EE-45BD-8881-5F9061FD0725","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"584cac3c812a88a9db4cb6186492f048d7d403d7","datavalue":{"value":"1407.94189","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725962$B3E4A2FD-E308-46B2-A45E-0511F9308511","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2391c5c2e0a706ba8f4e7330b6d5411e3bc5923b","datavalue":{"value":"10.1504/IJICOT.2017.10005835","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725962$64BAA43F-C38D-4F03-9AED-1C6F551BE3D0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cfbae12c647a07eebb143c1044dee5d401debeb9","datavalue":{"value":{"entity-type":"item","numeric-id":247145,"id":"Q247145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725962$20F77676-7778-4404-B718-A9BB4E88F9FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ad4922b72661863906a59e2a24695117e921c812","datavalue":{"value":{"entity-type":"item","numeric-id":725960,"id":"Q725960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725962$C6B5C232-B6CA-40D6-9EFA-3E46C01A6951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b23f8096a3326bc02e7c40bc29e6cdfa9ec72994","datavalue":{"value":{"entity-type":"item","numeric-id":662142,"id":"Q662142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725962$D7BD90D3-8515-4B3A-9234-9236AD5F5E1B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3e9e59970b6096537ac135b2cc16d1c02a64695","datavalue":{"value":{"entity-type":"item","numeric-id":274526,"id":"Q274526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q725962$8A99339A-2B4E-4976-B8D5-E41A9C408D09","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a9aa22cb8a96ecb8781adebec8cb26e1601a98e8","datavalue":{"value":{"time":"+2018-08-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q725962$A35979BB-EE16-4498-A1D3-604DD69E6284","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"94a0eb6b7e0db18a4dffd85562c1dba3facba33b","datavalue":{"value":"Summary: In 1978, the syndrome decoding problem (SDP) was proven to be \\(\\mathcal{NP}\\)-complete for random binary codes. Since then, the security of several cryptographic applications relies on its hardness. In 2009, \\textit{M. Finiasz} [\\url{arxiv:0912.0453}] extended this result by demonstrating the \\(\\mathcal{NP}\\)-completeness of certain subclasses of SDP. In this paper, we prove the \\(\\mathcal{NP}\\)-completeness of the Goppa parameterised quasi-dyadic syndrome decoding problem. We use a reduction to the four-dimensional matching problem (proven \\(\\mathcal{NP}\\)-complete).","type":"string"},"datatype":"string"},"type":"statement","id":"Q725962$6ECA4AD2-573B-4E71-B2F7-FFEF2AE17980","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"4430c94528f7856126af01b3ac6ccc7f8c77602b","datavalue":{"value":"94B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725962$1504716B-13C5-41F6-BA42-92B630AA285D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"258ff1d48f764d94acd3816b91edd4e4a8ed4558","datavalue":{"value":"6912656","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q725962$CD1B7AE0-619B-494D-B8C1-972F4B544EBD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"02189bff2e1d06b152db8ce573ac16c837281636","datavalue":{"value":"four dimensional matching problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q725962$E7D59A7B-B52D-43E6-A8D7-EEE671E4E145","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3dac602fe050141e9400cadfbaa6dad484694412","datavalue":{"value":"\\(\\mathcal{NP}\\)-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q725962$FCFD9B48-B3FB-4451-A6C1-263EBAEEE6F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50137346befaa16c9370c17c5ccfd53eb811566c","datavalue":{"value":"quasi-dyadic Goppa codes","type":"string"},"datatype":"string"},"type":"statement","id":"Q725962$C7F93778-F655-4062-8826-33FEBD7690FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25d7765d2fc5023f6541a27baed9040fdfbd393e","datavalue":{"value":"syndrome decoding problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q725962$178FF270-D50B-4530-9EE2-A26E4E6A2FB6","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":"Q725962$E2D18A0D-F2BF-40AB-A9CD-C04A3D32837D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2946da6eb7236e6b38996a9ab7d7c4bf8892acef","datavalue":{"value":{"entity-type":"item","numeric-id":2965866,"id":"Q2965866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cd12e1ff5209dcd4999f96b8def864e0333354c","datavalue":{"value":{"amount":"+0.910009503364563","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":"Q725962$073955A1-F38C-4B0E-9F21-EC67A7AA1919","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d34538b39fa941a81287b07f21132c46b2069d02","datavalue":{"value":{"entity-type":"item","numeric-id":1280761,"id":"Q1280761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a232e4505adabfc2bc0fb86332f6714199daf258","datavalue":{"value":{"amount":"+0.7479385733604431","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":"Q725962$6A11285C-E175-4AF2-9338-D83822D3B184","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dfc8b03514c4c4d42e3d8ec0cdbb1e3ea0060f28","datavalue":{"value":{"entity-type":"item","numeric-id":4536280,"id":"Q4536280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a232e4505adabfc2bc0fb86332f6714199daf258","datavalue":{"value":{"amount":"+0.7479385733604431","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":"Q725962$0CF17F8D-E078-4958-B580-FDF1FE8B6AA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a192df6dc035e87b9773e43157b33e6f8bc0e26f","datavalue":{"value":{"entity-type":"item","numeric-id":5739036,"id":"Q5739036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"33ec0c70b44598c4111448fe4fc37bb4588992ba","datavalue":{"value":{"amount":"+0.7415091395378113","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":"Q725962$9178F3A1-EB97-4D79-B54E-7BFBD051F6C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"871db3fc0a25fa4e7240efd0d8a51ea2c2cc0e5d","datavalue":{"value":{"entity-type":"item","numeric-id":6112190,"id":"Q6112190"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"740befbb2ed7a6b948b0ae7f90b0f50214f53094","datavalue":{"value":{"amount":"+0.7404308915138245","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":"Q725962$721034A4-EA9E-4F25-A011-7B57CA0E4BA5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:725962","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:725962"}}}}}