Αναγωγή Λένστρα–Λένστρα–Λοβάς

Η αναγωγή βάσης ενός πλέγματος κατά Lenstra–Lenstra–Lovasz (LLL) είναι ένας αλγόριθμος πολυωνυμικού χρόνου που επινοήθηκε από τους Άριεν Λένστρα, Χέντρικ Λένστρα και Λάσλο Λοβάς το 1982. Αν μας δοθεί μία βάση $\mathbf {B} =\{\mathbf {b} _{1},\mathbf {b} _{2},\dots ,\mathbf {b} _{d}\}$ με $\mathbf {b} _{j}\in {\mathbb {Z} ^{n}}$ ενός πλέγματος $\Lambda$, ο LLL αλγόριθμος υπολογίζει μία δ-ΛΛΛ-ανηγμένη βάση (μικρά μήκη διανυσμάτων, σχεδόν ορθογώνια) σε πολυωνυμικό χρόνο.

Ορισμός δ-LLL ανηγμένης βάσης ενός πλέγματος

Ο ακριβής ορισμός της ανηγμένης βάσης στον LLL είναι ο ακόλουθος:

Δεδομένης μιας βάσης

$\mathbf {B} =\{\mathbf {b} _{1},\dots ,\mathbf {b} _{n}\},$

ορίζουμε τη διαδικασία Gram-Schimdt για ορθογώνια βάση

$\mathbf {B} ^{*}=\{\mathbf {b} _{1}^{*},\dots ,\mathbf {b} _{n}^{*}\},$

και τους συντελεστές Gram-Schimdt

$\mu _{i,j}={\frac {\langle \mathbf {b} _{i},\mathbf {b} _{j}^{*}\rangle }{\langle \mathbf {b} _{j}^{*},\mathbf {b} _{j}^{*}\rangle }}$, για κάθε $1\leq j<i\leq n$.

Η βάση $B$ είναι ανηγμένη κατά LLL αν υπάρχει μια παράμετρος $\delta$ στο (0.25,1] τέτοια ώστε να ισχύει το εξής:

1. Για $1\leq j<i\leq n\colon \left|\mu _{i,j}\right|\leq 0.5$. Εξ ορισμού, αυτή η ιδιότητα εξασφαλίζει τη μείωση του μήκους της διατεταγμένης βάσης (size-reduced) .
2. Για k = 1,2,..,n $\colon \delta \Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}\leq \Vert \mathbf {b} _{k}^{*}\Vert ^{2}+\mu _{k,k-1}^{2}\Vert \mathbf {b} _{k-1}^{*}\Vert ^{2}$ (συνθήκη Λοβάς) .

Στα παραπάνω, εκτιμώντας την τιμή της παραμέτρου $\delta$, μπορούμε να συμπεράνουμε πόσο καλά είναι ανηγμένη η βάση. Μεγαλύτερες τιμές του $\delta$ οδηγούν σε ισχυρότερη αναγωγή της βάσης.

Αρχικά, οι Α. Λένστρα, Χ. Λένστρα και Λ. Λοβάς απέδειξαν τον αλγόριθμο LLL για $\delta ={\frac {3}{4}}$. Ας σημειωθεί ότι αν και ο αλγόριθμος είναι καλά ορισμένος για $\delta =1$, η πολυπλοκότητα πολυωνυμικού χρόνου εξασφαλίζεται μόνο για $\delta$ στο (0.25,1). Ο αλγόριθμος LLL υπολογίζει LLL ανηγμένες βάσεις. Δεν υπάρχει γνωστός αποδοτικός αλγόριθμος που υπολογίζει μια βάση της οποία τα διανύσματα είναι όσο το δυνατόν μικρά για πλέγματα με διάσταση μεγαλύτερη από 4. Ωστόσο, μια ανηγμένη κατά LLL βάση είναι σχεδόν όσο το δυνατόν μικρότερη, με την έννοια ότι υπάρχουν όρια $c_{i}>1$ τέτοια ώστε το πρώτο διάνυσμα της βάσης δεν είναι παραπάνω από $c_{1}$ φορές το μικρότερο διάνυσμα του πλέγματος, για το δεύτερο διάνυσμα υπάρχει αντίστοιχα ένα $c_{2}$, και ούτω καθεξής.

Αλγόριθμος αναγωγής κατά LLL με χρήση Ευκλείδειας νόρμας

Η ακόλουθη περιγραφή βασίζεται στον Γκαλμπρέιθ .

ΔΕΔΟΜΕΝΑ: ${\vec {b}}_{1},{\vec {b}}_{2},\dots ,{\vec {b}}_{n}\in {\mathbb {Z} ^{n}}$ (μια βάση του πλέγματος), παράμετρος ${\frac {1}{4}}<\delta <1$,  τυπική τιμή $\delta ={\frac {3}{4}}$
ΑΠΟΤΕΛΕΣΜΑΤΑ: Βάση ανηγμένη κατά LLL: ${\vec {b}}_{1}',{\vec {b}}_{2}',\dots ,{\vec {b}}_{n}'$

ΑΛΓΟΡΙΘΜΟΣ:
Υπολόγισε την Gram-Schmidt βάση $\{{\vec {b}}_{1}^{*},\dots ,{\vec {b}}_{n}^{*}\}$ και τους συντελεστές $\mu _{i,j}:={\frac {\langle {\vec {b}}_{i},{\vec {b}}_{j}^{*}\rangle }{\langle {\vec {b}}_{j}^{*},{\vec {b}}_{j}^{*}\rangle }}$, για $1\leq j<i\leq n$.
Υπολόγισε $B_{i}=\langle {\vec {b}}_{i}^{*},{\vec {b}}_{i}^{*}\rangle =\parallel {\vec {b}}_{i}^{*}\parallel ^{2}$ για $1\leq i\leq n$.
$k=2$

Όσο $k\leq n$ επανάλαβε
{
    Για $j=(k-1)$ μέχρι $1$ με βήμα $-1$ επανάλαβε
    {
        $q_{j}\gets \lfloor \mu _{k,j}\rceil$
        ${\vec {b}}_{k}\gets {\vec {b}}_{k}-{q_{j}}{\vec {b}}_{j}$
        Επανυπολόγισε τα $\mu _{k,j}$ για $1\leq j<k$
    }
    Αν $B_{k}\geq (\delta -\mu _{k,k-1}^{2})B_{k-1}$ τότε
        $k\gets k+1$
    Αλλιώς
    {
        Εναλλαγή ${\vec {b}}_{k}$ με ${\vec {b}}_{k-1}$
        Επανυπολόγισε τα ${\vec {b}}_{k}^{*},{\vec {b}}_{k-1}^{*},B_{k},B_{k-1},\mu _{k-1,j}$ και $\mu _{k,j}$ για $1\leq j<k$, και $\mu _{i,k},\mu _{i,k-1}$ για $k<i\leq n$
        $k\gets max\{2,k-1\}$
    }
}