{"entities":{"Q1662551":{"pageid":1673292,"ns":120,"title":"Item:Q1662551","lastrevid":56709606,"modified":"2026-03-19T02:24:31Z","type":"item","id":"Q1662551","labels":{"en":{"language":"en","value":"Segment LLL reduction of lattice bases using modular arithmetic"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6920522"}},"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":"Q1662551$3F028132-A8C8-4038-8FCC-7C0965FBD225","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c4695787ab97c3f6f47e245806813699d98d5305","datavalue":{"value":{"text":"Segment LLL reduction of lattice bases using modular arithmetic","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1662551$F221B073-28A7-45CD-A2F3-B6BEC09BB84C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"22d7d547c65c7a09148b03b98a5c8051b144a632","datavalue":{"value":"1461.11048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662551$FB4DAC56-76BC-4831-8DEF-881F6BF3E799","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0cc3cbe474fb83a006cca698eaea2c0246a45088","datavalue":{"value":{"entity-type":"item","numeric-id":173876,"id":"Q173876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$CD36BB1D-FAD8-4A46-B111-BF900537A20E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"307b632a861e177e8b5686decbad55db1af88224","datavalue":{"value":{"entity-type":"item","numeric-id":411123,"id":"Q411123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$A3A4F71A-732B-4EF2-8A42-7BD1F673D135","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$F8A275CD-7619-4E4A-B2F3-11799EE7DEAD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"431a43c637c8a2264e4d8145aa5a3c26bfb96786","datavalue":{"value":{"time":"+2018-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1662551$905BC9A4-4AD5-4A28-9156-65D97CC03976","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1142d6be156a36bb0b9cb92795166552be62bd87","datavalue":{"value":"Summary: The algorithm of Lenstra, Lenstra, and Lov\u00e1sz (LLL) transforms a given integer lattice basis into a reduced basis. Storjohann improved the worst case complexity of LLL algorithms by a factor of \\(O(n)\\) using modular arithmetic. Koy and Schnorr developed a segment-LLL basis reduction algorithm that generates lattice basis satisfying a weaker condition than the LLL reduced basis with \\(O(n)\\) improvement than the LLL algorithm. In this paper we combine Storjohann's modular arithmetic approach with the segment-LLL approach to further improve the worst case complexity of the segment-LLL algorithms by a factor of \\(n^{0.5}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662551$335B758B-EF65-4AEC-81DF-C9C559615ED2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d92207e5132f33177f4a9d633493fc0d8d742c6d","datavalue":{"value":"11C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662551$235F0428-F18E-469C-AA54-19F54BBE8A17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662551$13B87F7A-4360-4F57-95E9-DF10082C7069","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"58bd804a9b32ab16fea71636cf187b83a20de8f7","datavalue":{"value":"68P25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662551$588BD9F0-D334-4633-A373-8DAC925587B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a61c1214f17b12b67364674d8143dbdd872c34c1","datavalue":{"value":"65Y04","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662551$350FDAAA-B75D-41D9-97F3-7BE0A55263D7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"70be43faa8b83191ebf01edd895f906ccfe0b894","datavalue":{"value":"6920522","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662551$CC1E6CC7-F971-4BE1-A388-2FF5E2528B82","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f6be13cb695968c916d7350730eb53802ba046d","datavalue":{"value":"lattice","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662551$B5B829BE-8607-4FAB-882C-9AA0153DCD40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eddda49660393d1afe60a44f1a66eb1ae4d740ce","datavalue":{"value":"LLL basis reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662551$7BB83F3F-A580-4247-B8A4-5E594D6DB894","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e4efb6d5d192c6ce084f69468f330f0640a85ea","datavalue":{"value":"reduced basis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662551$F9C55678-7A66-4D9A-AE9C-CBE7B6432908","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34f12378b7ed4616c78afc0e5676cb442ccb5017","datavalue":{"value":"successive minima","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662551$CFC908AF-F48A-4657-82CE-F845C6E9433F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"98350a49bfc57cca35d54e10e3920384923dd18d","datavalue":{"value":"segments","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662551$2E081F2A-8BE0-4BC7-8C41-AF8751E5F9B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f53ca57c0d6f4612bcf8319e61973a78cc37ede1","datavalue":{"value":"modular arithmetic","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662551$8BA6D096-DBE4-4F24-AFAF-0B3F913304B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e466ddadae1b3430248f8e312b96feeca2d822f","datavalue":{"value":"fast matrix multiplication","type":"string"},"datatype":"string"},"type":"statement","id":"Q1662551$9F282C69-F8FA-4D01-BEBE-4AC5C52B6093","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":"Q1662551$16EA3D16-125B-4A48-B124-5128D215D8CE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8db88a0e6af4cd60dd1bdadb5ceaee2654b399c7","datavalue":{"value":"https://doi.org/10.3390/a3030224","type":"string"},"datatype":"url"},"type":"statement","id":"Q1662551$09BD666A-B3C5-4DB5-8BAA-6EAFB5104CBA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"07f32af77b5d616144897a83755897d9e650a0de","datavalue":{"value":"W1966632650","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662551$128B536B-FC09-4408-9ED5-30B72A51F1D5","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f7e2e97c20d2abc0f9a209eb0226efbd5e45b6d","datavalue":{"value":{"entity-type":"item","numeric-id":5611106,"id":"Q5611106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$A37FFE8C-7358-4749-9BCD-F65735916F43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ff65a2b1f8afd696edb57cf9a7986fded6fd734d","datavalue":{"value":{"entity-type":"item","numeric-id":4699284,"id":"Q4699284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$96CF137C-498D-4B11-8330-763CF03EE61D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7b369429581047e1dabd46e6eafe270ef5ac985","datavalue":{"value":{"entity-type":"item","numeric-id":3037135,"id":"Q3037135"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$B864B609-6392-4CD9-B25F-6D6D23007B76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1422fa73c563b7c939f4423cad8a509df12f0639","datavalue":{"value":{"entity-type":"item","numeric-id":4542515,"id":"Q4542515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$D551AEAB-EE7E-4BCA-BAC3-5FF6DBAEEBBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ae1859af926c68156128541f3a5648cb6e9717c","datavalue":{"value":{"entity-type":"item","numeric-id":2719121,"id":"Q2719121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$47DA8676-464E-4D9F-9B42-A72A7FE291B4","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":"Q1662551$4361C739-D978-4E99-956C-EC3AE158CD3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2c8689e414f41f7b3cec2912f4bc8526fd78bb2","datavalue":{"value":{"entity-type":"item","numeric-id":3686034,"id":"Q3686034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$B7D1D93B-A973-479D-B6D1-F0CA3DCCBA7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f45f4d7b0642c8b7f1f60bce044ccc7868c99975","datavalue":{"value":{"entity-type":"item","numeric-id":1101500,"id":"Q1101500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$F4FC368A-859B-4B4C-B3DC-2B9483975423","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc0458cd1106d03a918141a6befba7449b71760f","datavalue":{"value":{"entity-type":"item","numeric-id":4787201,"id":"Q4787201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$B66EF971-3BB5-4122-AE0D-839ECB336BC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7221643007a5bd3ad74f298b8b7b086a9451caf7","datavalue":{"value":{"entity-type":"item","numeric-id":4711415,"id":"Q4711415"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$11EF4911-6B87-4A2E-AE86-EACF4C50FFC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"00225a43b5e5bb48eef42d430db63f815da3f8ff","datavalue":{"value":{"entity-type":"item","numeric-id":5385731,"id":"Q5385731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$86E87B45-505F-4332-9CC3-7D0B40CCC7EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3189590f31eaeeb7c0b3fa1ce11027bdacbffb93","datavalue":{"value":{"entity-type":"item","numeric-id":2490117,"id":"Q2490117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$AE11418C-CAFC-4AD3-862B-E2D7D2B10735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1991dcc19ee1db2dd799bdfb61175406078f5f7","datavalue":{"value":{"entity-type":"item","numeric-id":4022031,"id":"Q4022031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$D6831B3F-7D41-4A8A-9ED4-50FED32E9D85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd976b54ba87d7509483b2d9687f21d94666ab25","datavalue":{"value":{"entity-type":"item","numeric-id":4787200,"id":"Q4787200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$7D4DEA66-469A-4CC9-9A10-002BEFD88328","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8ba154389a204d2fe13cce852c6d6422d7912c2","datavalue":{"value":{"entity-type":"item","numeric-id":4023676,"id":"Q4023676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$F853B70C-CD32-47B4-B854-2305C2274938","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"480ac560f713e57a5ee8cd072f59d2635f9c43d4","datavalue":{"value":{"entity-type":"item","numeric-id":915378,"id":"Q915378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$FFA84000-1195-4792-B281-C5540C42B600","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45efb401aa061ceb68519ea16bb3d7d1b1684ef5","datavalue":{"value":{"entity-type":"item","numeric-id":5188541,"id":"Q5188541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$8CF302D2-63FB-4B65-B611-D2515835626D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d864ecf0887e3285d5a657ecba76076407dae52","datavalue":{"value":{"entity-type":"item","numeric-id":2548172,"id":"Q2548172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$88A0B21B-914F-409A-934D-B71CF139D165","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9962df93bb36beef9582a465d73faed1d632572a","datavalue":{"value":"10.3390/A3030224","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1662551$07F4E0E0-5D10-4EA8-A05E-6A8611261D5A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"851446271a5e2a4c03a02f0771982d06a9c143c6","datavalue":{"value":{"entity-type":"item","numeric-id":4787200,"id":"Q4787200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0cb78795672023eb9553df9c2adafa0ed067b79","datavalue":{"value":{"amount":"+0.8764023780822754","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":"Q1662551$AB0EABC3-0CA2-4637-9A91-C96B8CB09398","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a40292f2c8fe8d943eb63a70a54570e55f4635f","datavalue":{"value":{"entity-type":"item","numeric-id":1093661,"id":"Q1093661"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c244e1832d1c5c890383003d043998988516b60","datavalue":{"value":{"amount":"+0.8764021992683411","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":"Q1662551$F301D2C9-1CD7-4CC0-86F6-1CA5578C10E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91fbcb4d3beb9a32d7922674b9e8aec1020ad56b","datavalue":{"value":{"entity-type":"item","numeric-id":2490117,"id":"Q2490117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"699234a98f785b8dc54dc15c58f3fbb1a3d1eb51","datavalue":{"value":{"amount":"+0.8539918661117554","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":"Q1662551$A2957B67-66BB-4F4C-A57B-E1D25F9A8448","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4d32217bc249fca04ae7b3fbc533a85dfa3d6c96","datavalue":{"value":{"entity-type":"item","numeric-id":5188540,"id":"Q5188540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a44d7e9ff353f213b5d5575f0d352b942c282035","datavalue":{"value":{"amount":"+0.8317612409591675","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":"Q1662551$1FB996BC-B151-42A0-9FC7-4027AE1B03B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"513b33885205c9019979736b3c3cf5ddbcc916d8","datavalue":{"value":{"entity-type":"item","numeric-id":2985850,"id":"Q2985850"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"17ba7fe77831498a7be9914e948b8e4460ec02cc","datavalue":{"value":{"amount":"+0.8286770582199097","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":"Q1662551$EB7ACA65-C45D-4612-85FB-395EC52DD86A","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1662551$A10C9F4F-420B-4478-8AB0-7062B9AEF76B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1662551","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1662551"}}}}}