{"entities":{"Q4254898":{"pageid":6284499,"ns":120,"title":"Item:Q4254898","lastrevid":108474785,"modified":"2026-11-06T14:58:02Z","type":"item","id":"Q4254898","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1313325"}},"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":"Q4254898$44C6D1BA-7CD3-489D-83DF-DE4289FE66ED","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1f230b449e3e913db99b42df7940e0997cd5f3ce","datavalue":{"value":"0921.68040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4254898$CE27E862-7839-4849-A66E-3EE670DA7313","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"55fa8df650447363f9384003d99a15e9e7ac7f61","datavalue":{"value":{"entity-type":"item","numeric-id":4254897,"id":"Q4254897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4254898$56F11B06-0CCA-429C-8AC8-14F9CD154DDD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"818c8da732f8e84e40ec58932e1237ded2f4a717","datavalue":{"value":{"time":"+1999-07-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4254898$8C881AD0-0EE3-4044-AB9A-EE09EF462B94","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4254898$02D76FA6-CDE9-465E-930F-0EF1BB8680D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"24aafcf24a21bd70cd3b62d3f5f72a6d0d82d816","datavalue":{"value":"68-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4254898$499ED715-36CF-4D69-AD17-DB254CC73EA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4254898$10FB99F8-27B1-4DFE-B114-63A42447ECBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"732c2501ca31f5ceeef797f80b885d9dde0d046f","datavalue":{"value":"11H06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4254898$BBE53011-3F33-4068-89E9-3296E8826999","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"993aa69259ba7f271f114261991fbd43d0612080","datavalue":{"value":"1313325","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4254898$C6993C20-19C5-4168-AB47-3DB02671AF7E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9213ab772920d30b527d70467148382020755fa1","datavalue":{"value":"knapsack problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q4254898$BE16C101-1B6E-4B30-8159-D63DD5728D34","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":"Q4254898$ABE7900A-1617-43B5-BC97-A12965FA5F33","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a76bdc13e375fd20228163f5af2116cbb9db201","datavalue":{"value":{"entity-type":"item","numeric-id":3220657,"id":"Q3220657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6de9355c03aa71ee1175a03e1604276597c34fde","datavalue":{"value":{"amount":"+0.8048250079154968","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":"Q4254898$DFEB6697-803C-431E-9FD0-B9C95DADA677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31b233cac5d42ee31e4891bd61ac90d97e5b7e17","datavalue":{"value":{"entity-type":"item","numeric-id":5176018,"id":"Q5176018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e8149d54e8c67019dabb8e581a9cde1a23c3061","datavalue":{"value":{"amount":"+0.7859269976615906","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":"Q4254898$8E83B3A0-0607-4889-888D-64526C4847D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53fbce4eaf82d29d035f0f7a31f5ad837e3931a6","datavalue":{"value":{"entity-type":"item","numeric-id":5465355,"id":"Q5465355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e396100784ebaaa5d346b329b3fdea84f655765e","datavalue":{"value":{"amount":"+0.779098391532898","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":"Q4254898$AAF396A1-C756-432B-8555-EDF16FE1F6ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d4742d2a22ea78ca227e82d1e675315ade3a67c4","datavalue":{"value":{"entity-type":"item","numeric-id":3739233,"id":"Q3739233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8c1e8546ccdff9a4b6c482e8d76486333dce1b7b","datavalue":{"value":{"amount":"+0.7768518924713135","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":"Q4254898$49043C95-2DEC-443C-8FDC-F63ED82197B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4512e26aa0f7ac17f8ebfea5122739f9045cf47","datavalue":{"value":{"entity-type":"item","numeric-id":1014636,"id":"Q1014636"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb08caad8dcacc728f48d9438efdcc943da143c8","datavalue":{"value":{"amount":"+0.7751161456108093","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":"Q4254898$8AED6266-C0E1-4E5C-9F74-25F642C5AAE3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8550077685f9d800b2ea93a86c1d99547cb78d9e","datavalue":{"value":"Unter einem Gitter vestehen wir eine (durch eine Gitterbasis erzeugte) diskrete, additive Untergruppe des \\(\\mathbb{R}^n\\). Wir entwickeln Aufz\u00e4hlungsverfahren zur Bestimmung eines (bez\u00fcglich einer beliebig vorgegebenen Norm) nachweislich k\u00fcrzesten, von Null verschiedenen Gittervektors, die in m\u00f6glichst hohen Dimensionen vertretbare Rechenzeiten besitzen. Wir l\u00f6sen Rucksackprobleme durch Reduktion auf die Suche nach einem Gittervektor mit \\(\\ell_\\infty\\)-Norm 1. Mit unserem Aufz\u00e4hlungsverfahren bez\u00fcglich der \\(\\ell_\\infty\\)-Norm gelingt es, alle Rucksackprobleme bis Dimension 66 effizient zu l\u00f6sen. Wir brechen mit diesem Verfahren Kryptosysteme, die auf dem Rucksackproblem basieren. Der Aufwand zur Bestimmung eines k\u00fcrzesten, von Null verschiedenen Gittervektors h\u00e4ngt entscheidend von der Wahl der Basis des jeweiligen Gitters ab. Er wird umso geringer, je besser die Basisvektoren die k\u00fcrzesten Gittervektoren approximieren. Wir untersuchen daher verschiedene Reduktionsbegriffe. Wir zeigen Schranken f\u00fcr die G\u00fcte der Approximation und entwickeln Algorithmen zur Bestimmung von reduzierten Gitterbasen. F\u00fcr gro\u00dfe Dimensionen reichen selbst ``gut vorreduzierte'' Gitterbasen nicht mehr aus, um einen k\u00fcrzesten Gittervektor effizient zu bestimmen. Wir entwickeln ein probabilistisches Aufz\u00e4hlungsverfahren, das f\u00fcr zuf\u00e4llige Eingaben eine fest vorgegebene Erfolgswahrscheinlichkeit beweisbar nicht unterschreitet.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4254898$FE912A23-D6CB-4AF8-849B-08DA76922BED","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4254898","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4254898"}}}}}