Кіріспе
Есептеулік сандар теориясындағы алгоритм. Ленстра–Ленстра–Ловас (LLL) решеткалық негізді азайту алгоритмі – 1982 жылы Арьен Ленстра, Хендрик Ленстра және Ласло Ловас тапқан полиномиалдық уақытта жұмыс істейтін решетканы азайту алгоритмі. n өлшемді бүтін сандық координаттары бар негізді алғанда, L решеткасы (Rn дискретті кіші тобы) үшін, LLL алгоритмі LLL азайтылған (қысқа, дерлік ортогональды) решеткалық негізін уақыттың ішінде есептейді, мұнда – Евклид нормасы бойынша ең үлкен ұзындығы, яғни. Алғашқы қолданыстары рационалдық коэффициенттері бар полиномдарды есептеу үшін полиномиалдық уақыт алгоритмдерін беру, нақты сандарға бірдей рационалдық жуықтамаларды табу және белгілі өлшемдердегі бүтін сандық сызықтық бағдарламалау мәселесін шешу болды.
The Lenstra–Lenstra–Lovász (LLL) lattice basis reduction algorithm is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982. Given a basis with n dimensional integer coordinates, for a lattice L (a discrete subgroup of Rn) with , the LLL algorithm calculates an LLL reduced (short, nearly orthogonal) lattice basis in time where is the largest length of under the Euclidean norm, that is,
The original applications were to give polynomial time algorithms for factorizing polynomials with rational coefficients, for finding simultaneous rational approximations to real numbers, and for solving the integer linear programming problem in fixed dimensions.
Қолданбалар
LLL алгоритмінің алғашқы сәтті қолданылуы Эндрю Одлицко мен Герман те Риле Мертенс болжамын жоққа шығаруда қолданған. LLL алгоритмі MIMO детекция алгоритмдерінде және ашық кілт шифрлау схемаларының криптоанализінде көптеген басқа қолданыстар тапты: рюкзак криптожүйелері, нақты параметрлері бар RSA, NTRUEncrypt және т.б. Алгоритм көптеген мәселелердің бүтін сандық шешімдерін табу үшін қолданылуы мүмкін. Атап айтқанда, LLL алгоритмі бүтін сандар қатынасын анықтау алгоритмдерінің бірінің негізгі бөлігін құрайды. Мысалы, егер r=1.618034 – бүтін сандық коэффициенттері бар белгісіз квадрат теңдеудің (сәл дөңгеленген) түбірі деп есептелсе, LLL қысқартуын ені бойынша және төмендегі негіздегі бірінші вектор осы үшеудің бүтін сандық сызықтық комбинациясы болады, сондықтан міндетті түрде формасы ; бірақ мұндай вектор "қысқа" болса ғана a, b, c кіші болады және одан да кіші. Осылайша, осы қысқа вектордың алғашқы үш мүшесі r түбірі бар интегралды квадраттық көпмүшенің коэффициенттері болуы мүмкін. Бұл мысалда LLL алгоритмі ең қысқа векторды [1, 1, 1, 0.00025] деп табады және ол алтын қатынасқа тең түбірге ие, 1.6180339887.
LLL-ке төмендетілген негіздің қасиеттері
LLL қысқартылған негізін анықтауынан біз негіздегі бірінші вектор ең қысқа нөлдік емес вектордан әлдеқайда үлкен бола алмайды деген бірнеше басқа пайдалы қасиеттерді шығара аламыз: атап айтқанда, үшін , бұл келесіні береді. Негіздегі бірінші вектор сонымен қатар тордың детерминантымен шектеледі: атап айтқанда, үшін , бұл келесіні береді. Негіздегі векторлардың нормаларының көбейтіндісі тордың детерминантынан әлдеқайда үлкен бола алмайды: егер онда , онда .
The first vector in the basis cannot be much larger than the shortest non zero vector: In particular, for , this gives The first vector in the basis is also bounded by the determinant of the lattice: In particular, for , this gives The product of the norms of the vectors in the basis cannot be much larger than the determinant of the lattice: let , then .