{"entities":{"Q7361415":{"pageid":31519784,"ns":120,"title":"Item:Q7361415","lastrevid":105423584,"modified":"2026-10-08T13:45:26Z","type":"item","id":"Q7361415","labels":{"en":{"language":"en","value":"A verified LLL algorithm"}},"descriptions":{"en":{"language":"en","value":"AFP entry LLL_Basis_Reduction"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9c2448a619c57c4c848ffa8b8d7e753efe53e0bf","datavalue":{"value":"https://isa-afp.org/entries/LLL_Basis_Reduction.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361415$8A15BAB5-5E00-4899-A6BF-951DD16ED149","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"d6e2e06bc6d38783fcdfb6387c30d5f45465b3a1","datavalue":{"value":"Ralph Bottesch","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361415$5A24DFEB-A582-422E-BD50-DE64712BA598","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"3ac7196df7cfbb13ec1a00e4eadbe8c75213209e","datavalue":{"value":"Jose Divas\u00f3n","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361415$73BD89A6-5C50-4524-8AC0-0A457621AFAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"3e24c85cc74f22f9901f70520869c19fde2b00ac","datavalue":{"value":"Max W. Haslbeck","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361415$A8B02A1B-7966-4834-BD1F-73081702FF11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"68caf737a72c94bcb2627452f3944631c5b3bfaa","datavalue":{"value":"Sebastiaan J. C. Joosten","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361415$EF8957F1-F07C-495E-AB59-F12E8166F9CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"3e961f1f2b2e533bd88ffdbcd178bd2ef2813f73","datavalue":{"value":"Ren\u00e9 Thiemann","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361415$5B5A0404-5114-4207-867C-CD8712C5F644","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"4e646f16cde9cfa1c19d0771a8f74ba7e8c772f6","datavalue":{"value":"Akihisa Yamada","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361415$1B50C4B4-3721-41FF-9F18-22F9E780E0C9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"30ea4281b610f9d35139bee3c15bc36457150b52","datavalue":{"value":"The Lenstra-Lenstra-Lov\u00e1sz basis reduction algorithm, also known as LLL algorithm, is an algorithm to find a basis with short, nearly orthogonal vectors of an integer lattice. Thereby, it can also be seen as an approximation to solve the shortest vector problem (SVP), which is an NP-hard problem, where the approximation quality solely depends on the dimension of the lattice, but not the lattice itself. The algorithm also possesses many applications in diverse fields of computer science, from cryptanalysis to number theory, but it is specially well-known since it was used to implement the first polynomial-time algorithm to factor polynomials. In this work we present the first mechanized soundness proof of the LLL algorithm to compute short vectors in lattices. The formalization follows a textbook by von zur Gathen and Gerhard.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361415$DCA73C46-9740-4DFC-8F8C-EEDA964F6E47","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd3cb111961ea4ebcb9bb0bcdcc90cb23fa2d528","datavalue":{"value":{"entity-type":"item","numeric-id":4227353,"id":"Q4227353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$68118101-7284-4743-B0E8-DB0A3382F9A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2496d76f7d7fec9d96f39f6e3a59ed93c78d8e95","datavalue":{"value":{"entity-type":"item","numeric-id":1165896,"id":"Q1165896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$0CFA99BC-DD2B-45DD-82FF-852248D9596E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0543f1e8c81032cff0b481c190929fef1b006bd","datavalue":{"value":{"entity-type":"item","numeric-id":4406533,"id":"Q4406533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$4575881D-192F-4DD3-A91F-8910704CCF3C","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"2594c168cd7f73433095d3ad9eaea472f82c3ee0","datavalue":{"value":{"entity-type":"item","numeric-id":7361619,"id":"Q7361619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$20B19650-EF2A-4CCE-AEA9-53C11E8374F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"58b378310c3c01d83cef379d83129d9bd06f9769","datavalue":{"value":{"entity-type":"item","numeric-id":7361750,"id":"Q7361750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$A25AC997-9704-407A-9E35-4F93BD235BB1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3340cc79e75714646430612898cfc312969e0dd0","datavalue":{"value":{"time":"+2018-02-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":"Q7361415$88B2AABE-3B5D-4335-BE36-847D54E85B25","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c35fc3834fbce535836bba79b3c7fdf1be03a14d","datavalue":{"value":{"text":"A verified LLL algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361415$897A707C-8AE1-4726-BB77-99D89A0A6501","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$CA106952-BB3F-409F-98EF-F4B8254D02A5","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"8b04062afcab9da0e2966e5a07727a614a9432ac","datavalue":{"value":{"entity-type":"item","numeric-id":7360778,"id":"Q7360778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$AC56C77E-5AD1-4E3C-9843-84F61E3F1772","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$7289D395-F9C9-462C-89C6-06C2626C101A","rank":"normal"}],"P13":[{"mainsnak":{"snaktype":"value","property":"P13","hash":"d885f61fc8119904a8ac71c6434ad7c3f5fe6042","datavalue":{"value":"28661","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7361415$DF1E4BC1-1118-4528-AAF4-CCD088C8EF35","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd3cd3c8cd085ac2048034c2279872658062342d","datavalue":{"value":"11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7361415$920FF623-391C-4F8C-8725-576916A76A6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f5e0c6033338f59ef27e37d6877da0f26d9646","datavalue":{"value":"68.0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7361415$950EB007-EBEF-42E7-9635-0671F0AE6820","rank":"normal"}],"P1458":[{"mainsnak":{"snaktype":"value","property":"P1458","hash":"cc41d9364226bfa8139f8dbc43b1b77967245f13","datavalue":{"value":{"entity-type":"item","numeric-id":17631,"id":"Q17631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$BCFB3B88-ECE7-4044-B42C-82C42F6F62CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"a2a767ccd0e9bdc5b1b4a2069a6679f9340a857a","datavalue":{"value":{"entity-type":"item","numeric-id":14275,"id":"Q14275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$A3EF0420-954B-4222-8E46-4ADC3F52EDFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ecda3e6d8e971c0b93d4cf3afb41990e853f830f","datavalue":{"value":{"entity-type":"item","numeric-id":13212,"id":"Q13212"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$94207DBA-358A-4EF4-98E8-25483F916109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"7d1a8519018039436924ad678b461ed447b5bd71","datavalue":{"value":{"entity-type":"item","numeric-id":40310,"id":"Q40310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$C81A3E54-EE48-45C3-98E2-4AA850DC26C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"b05ebaa65438167fd8c160361611fffcc4886639","datavalue":{"value":{"entity-type":"item","numeric-id":40374,"id":"Q40374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$345DA0C1-2A0B-441D-A85E-092CF5D36E21","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"c7cf914fa2ed02c8c123a4c265842a9ab4be0800","datavalue":{"value":{"entity-type":"item","numeric-id":25403,"id":"Q25403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$EA3A0894-6087-43B2-B517-02FAE42FCE9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ed15eb8701a335444fde1bcc3327d1067ce64751","datavalue":{"value":{"entity-type":"item","numeric-id":24376,"id":"Q24376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$04E24E9A-DFFB-4D28-B7E7-7F1A62C70936","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"868d665ea0607bf8bd28ea3e3872eb2ea87bd3d3","datavalue":{"value":{"entity-type":"item","numeric-id":40371,"id":"Q40371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$265B2B22-A2C8-4B5A-95CC-B3B44A6046CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"bb05cb23794774f62a8e4aa4de610af231973a1d","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$07D25F0C-D8EE-4E2D-BE0C-E04A20FB5ED7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"61d0c0612cc30c9c51b93ddaf1f78ee1ae75f9fe","datavalue":{"value":{"entity-type":"item","numeric-id":18676,"id":"Q18676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$8C2C35CB-A426-4A64-8AE8-A2411B33755B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"9eb436930ab1f6d235b354c651322b547341064b","datavalue":{"value":{"entity-type":"item","numeric-id":13309,"id":"Q13309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$CB48C309-7B07-4D18-85DE-122B1DEEB313","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"03281999c3208b8f3a62eaceadadf1ce834fe219","datavalue":{"value":{"entity-type":"item","numeric-id":12929,"id":"Q12929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$F4134974-BA3A-4744-959C-8989255C9D9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"8d55daeff7c4288ce44d22059c68add0e43c0b42","datavalue":{"value":{"entity-type":"item","numeric-id":40280,"id":"Q40280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$371ABC10-BF74-415E-9A2B-051B6D864F82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"140c4614c583c2ec7c147606c5e04e1104ea1634","datavalue":{"value":{"entity-type":"item","numeric-id":40376,"id":"Q40376"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$77A8DC57-F126-4470-AE13-7117E675D8BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"b82152c1528c5be7e2040d1abd74977f4fe51817","datavalue":{"value":{"entity-type":"item","numeric-id":18672,"id":"Q18672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361415$69D768E4-7DAE-4A9B-BF72-73E4076B68C6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A verified LLL algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_verified_LLL_algorithm"}}}}}