{"entities":{"Q40375":{"pageid":40431,"ns":120,"title":"Item:Q40375","lastrevid":105426389,"modified":"2026-10-09T10:05:19Z","type":"item","id":"Q40375","labels":{"en":{"language":"en","value":"Verified LLL"}},"descriptions":{"en":{"language":"en","value":"AFP entry LLL_Basis_Reduction"}},"aliases":{},"claims":{"P13":[{"mainsnak":{"snaktype":"value","property":"P13","hash":"d885f61fc8119904a8ac71c6434ad7c3f5fe6042","datavalue":{"value":"28661","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40375$9E75A958-2148-4C1F-92DD-E07016AC4532","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":"Q40375$838C2198-482F-41BB-B1C4-6FBE1F7AB3CD","rank":"normal"}],"P29":[{"mainsnak":{"snaktype":"value","property":"P29","hash":"0b64eb03d9d38b489347758827b061902870e99c","datavalue":{"value":"https://www.isa-afp.org/entries/LLL_Basis_Reduction.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q40375$51851F85-00B8-430C-92F4-350B9142C989","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd3cd3c8cd085ac2048034c2279872658062342d","datavalue":{"value":"11","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40375$6C730C1C-C0E7-4B7D-A564-A856F6379A8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"acf10290b955a69659a681d98822944f91bbad9e","datavalue":{"value":"68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40375$2324D933-CE11-4B6B-8FAA-E03FE722FBE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"09f5e0c6033338f59ef27e37d6877da0f26d9646","datavalue":{"value":"68.0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40375$DF244283-8C1C-4380-AA2B-ADA815B1D97F","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":"Q40375$C7E62B58-52C3-4B24-9C63-C86CBE8E6CA6","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":"Q40375$4FEC08B2-901B-4542-A4D3-2A6C411D6D39","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":"Q40375$F55D5722-3E98-4387-8AE9-064ED29CC608","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":"Q40375$5023D2E5-9754-40F5-87C2-B7A75BDE3F01","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":"Q40375$A0E260D3-F4A7-427E-BB12-F9D22A60B6DC","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":"Q40375$24C90D53-50EE-47C0-B3F2-479E35C6BFEC","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":"Q40375$BE8C613C-8F20-40C0-8E43-8E14C26DD083","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":"Q40375$30A57C5B-277C-4D5B-AA40-8D2AD930333E","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":"Q40375$61E74067-92C3-4EDA-8FD8-BE227534F09C","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":"Q40375$395507FE-1454-4113-8E24-59025AF59ADE","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":"Q40375$6BBD7A8A-A690-46A6-8527-2576ACCB3BE0","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":"Q40375$FD671078-8295-4BBA-AEAD-477E6EE41773","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":"Q40375$ADD83E21-54BE-47AD-82BA-056991EECA53","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":"Q40375$461D12CD-347E-411D-921F-79E558844874","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":"Q40375$008DE42D-B613-48EA-AD91-AD9DE5A3FFA9","rank":"normal"}],"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":"Q40375$16AA3BED-347E-4B9C-B162-2196315CCF54","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"d6e2e06bc6d38783fcdfb6387c30d5f45465b3a1","datavalue":{"value":"Ralph Bottesch","type":"string"},"datatype":"string"},"type":"statement","id":"Q40375$CD85BCA7-CC7A-45B4-9714-8CEE31844B9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"3ac7196df7cfbb13ec1a00e4eadbe8c75213209e","datavalue":{"value":"Jose Divas\u00f3n","type":"string"},"datatype":"string"},"type":"statement","id":"Q40375$14B4B84F-70D7-4AE2-9168-E0FE7A253E70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"3e24c85cc74f22f9901f70520869c19fde2b00ac","datavalue":{"value":"Max W. Haslbeck","type":"string"},"datatype":"string"},"type":"statement","id":"Q40375$4691DCEA-7C6B-4F79-B481-198774127902","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"68caf737a72c94bcb2627452f3944631c5b3bfaa","datavalue":{"value":"Sebastiaan J. C. Joosten","type":"string"},"datatype":"string"},"type":"statement","id":"Q40375$8B32E644-610B-49A6-960E-AD15C3DB60AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"3e961f1f2b2e533bd88ffdbcd178bd2ef2813f73","datavalue":{"value":"Ren\u00e9 Thiemann","type":"string"},"datatype":"string"},"type":"statement","id":"Q40375$2516054D-320E-47A7-9CC7-E89F6FEF392C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"4e646f16cde9cfa1c19d0771a8f74ba7e8c772f6","datavalue":{"value":"Akihisa Yamada","type":"string"},"datatype":"string"},"type":"statement","id":"Q40375$0F4663B1-0717-44F5-9977-163A8C0BD676","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":"Q40375$F31F2669-5F9B-400B-BD5F-EDDA0AB34ABB","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":"Q40375$4C64FB3D-5C62-4319-81C3-FA0295232674","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":"Q40375$C14BE3A0-9F5B-40C9-86BC-2DF6C4CD5417","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":"Q40375$6B65F953-6F44-4F74-BA0F-EAF3DF312BFF","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":"Q40375$E0B3EBCD-2420-490B-A169-BFF51998F30D","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":"Q40375$9EBB5310-C256-44DF-BB58-8E811B3635DB","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":"Q40375$9CFCEA3D-4493-4E77-BDCD-11BB7FDAC157","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":"Q40375$E96C53A2-730F-495A-ABFA-A21A33963EB2","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":"Q40375$0D0AE073-410A-4629-9D80-26D2028E0F78","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":"Q40375$62E032AD-C311-428E-A083-05DEA934DC94","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Verified LLL","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Verified_LLL"}}}}}