{"entities":{"Q1126836":{"pageid":1137585,"ns":120,"title":"Item:Q1126836","lastrevid":66188301,"modified":"2026-04-12T08:08:26Z","type":"item","id":"Q1126836","labels":{"en":{"language":"en","value":"Worst-case complexity, average-case complexity and lattice problems"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1184380"}},"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":"Q1126836$E5AA7C1D-6701-4B4D-BFEB-0D15902BFDAA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"92f642e41173170468d223d9e34f91c6592fbe3b","datavalue":{"value":{"text":"Worst-case complexity, average-case complexity and lattice problems","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1126836$83FF08EA-BC7D-4AE5-915A-112D7DEBDD6F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ec7faedfe23e1fff6f959a0859abcfc84351f520","datavalue":{"value":"0922.11111","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126836$65A34E82-53DB-4A5B-88F1-EDE1A7E17F10","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4add3c5163a5eee9bbe20dc8a36386ab43b68fd6","datavalue":{"value":{"entity-type":"item","numeric-id":168490,"id":"Q168490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1126836$F3B53933-B2F4-48C2-8B9F-11FB2FC47E01","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0213be50779ba5bffb4613228959545da04beaec","datavalue":{"value":{"time":"+1998-08-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1126836$72D12749-758D-482C-9D9F-D064085B4AF0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"84fa8a9b079783d78c9d275bd9a07cc2524d570d","datavalue":{"value":"https://eudml.org/doc/227634","type":"string"},"datatype":"url"},"type":"statement","id":"Q1126836$BF89FD8C-C123-4DB5-9DEF-FCD506716D17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"e9670f5d440f029bad54f72fb03ba109455f9379","datavalue":{"value":"http://www.emis.de/journals/DMJDMV/xvol-icm/14/Ajtai.MAN.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1126836$246C6262-9ED5-4242-B725-AA77A0DB7E44","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"dbe33783806a967258d3410b1a92e13d6bc5395c","datavalue":{"value":"The author presents a public-key cryptosystem based on the difficulty of a problem essentially similar to finding the shortest vector in a lattice. As part of the introduction, the author discusses the need for a problem that is hard in the average case; traditional complexity theory has focused on the worst-case complexity of problems.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126836$B3FD1F49-4CDE-4A5F-8D93-1CE09F626C61","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126836$10DCF947-99DC-4CD2-A79A-7AAACCAA1E94","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b3f5570531d36cdad95fcc8cba24a2dabc5fbbbf","datavalue":{"value":"94A60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126836$A411831D-6730-4177-ABCB-5E427F9DA1A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126836$3DA47620-3E55-4A33-8706-80536F194172","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126836$94368483-4B22-48B9-9E48-BC21A7427F3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9f3a770aca53115fb3ca1a8111091a579be311da","datavalue":{"value":"11H55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126836$C4EE456E-1D81-485D-8615-38A1E5E313DC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cd77531c7baccc0e3f237b4c303c582c75671caa","datavalue":{"value":"1184380","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126836$CEC3077C-AC77-4520-A197-88E794385971","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f6be13cb695968c916d7350730eb53802ba046d","datavalue":{"value":"lattice","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126836$4F8DEC22-F151-489F-B351-6E1AD4CE1F96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d042f17b2aaf215eddc1e37e7ef0c1f1818cd452","datavalue":{"value":"worst-case","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126836$31AD9C77-5498-4736-9254-0E86E1C7612C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7246f1957450cb18a2818ed41ce9c05cef8480ba","datavalue":{"value":"average-case","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126836$53D46182-8522-488B-BAE5-58714487BB93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126836$066B68CD-B565-41FA-A30B-35C047E1A6A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1c5511b15959f2cf7295ca726ed02ea08c4f84f","datavalue":{"value":"basis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126836$2FE2FFC1-5D25-4E88-B67A-EDE80F0FDD0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0050bc514b328d684778704e85c367292be0a033","datavalue":{"value":"shortest vector","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126836$F39E8FC0-114D-4617-AC90-E77F9692F08D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc54f86db2df612fae670d8a8a4d6c7276f41205","datavalue":{"value":"public-key cryptosystem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1126836$B53A1633-141B-47EF-B30A-C39022B16B49","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0148865fab0c03358d2bdbf45e3f52d46a798048","datavalue":{"value":{"entity-type":"item","numeric-id":684397,"id":"Q684397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1126836$074D84AC-C8DE-4480-989C-57B65395D92C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"8e97fd9a96db029bc62d9cd0c08c3d9657420966","datavalue":{"value":{"entity-type":"item","numeric-id":991751,"id":"Q991751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1126836$A9D0FBB4-DAC6-4C46-96B7-2BB13257A1AE","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":"Q1126836$486EEEAD-1069-4DBC-A36E-7E838D9A5FE9","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"3b09dd0b3d042a5617311634022684bcd87ba832","datavalue":{"value":"bafkreiblproz2p2ck4bwtmnc45q4ebo5sq6tq32dxxudatauebzwic3bwm","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1126836$5990DEAB-A579-4214-A3AB-B1D623B7FF4A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78e657979366f1e79d81113984c118a7ab57e7b4","datavalue":{"value":{"entity-type":"item","numeric-id":4526993,"id":"Q4526993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6356070744694c0a75933e7c01ee0726018ce2d0","datavalue":{"value":{"amount":"+0.8758307099342346","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":"Q1126836$3101B83A-B82F-4365-A079-70410F1FB236","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5418e6a410461f15a128f56c72b20a2bfdc86276","datavalue":{"value":{"entity-type":"item","numeric-id":2739433,"id":"Q2739433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"661c1983bcfc6a8f48cd202285dba6f2955b4972","datavalue":{"value":{"amount":"+0.8531248569488525","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":"Q1126836$25DB6581-71D0-4A67-9877-0C10A60B5430","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"964b88f49f9b98b02d10c86bb9779d2043a24916","datavalue":{"value":{"entity-type":"item","numeric-id":4250819,"id":"Q4250819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a8f8568fdb9668be4e4cbbe052fe8ca6c56347c","datavalue":{"value":{"amount":"+0.8097355365753174","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":"Q1126836$8D57F8F5-40D9-40C3-8305-977735EDA21C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56814a06c4187adb332ea96a83986aced19ca57c","datavalue":{"value":{"entity-type":"item","numeric-id":1854277,"id":"Q1854277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56439352241cce2e905c9ebeea3da9baf6f34720","datavalue":{"value":{"amount":"+0.809735119342804","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":"Q1126836$F391A1DF-6876-46CD-8153-8E08066135A4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Worst-case complexity, average-case complexity and lattice problems","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Worst-case_complexity,_average-case_complexity_and_lattice_problems"}}}}}