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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
(Ανακατεύθυνση από Αναγωγή Lenstra–Lenstra–Lovász (LLL))
Μετάβαση στην πλοήγηση Πήδηση στην αναζήτηση

Η αναγωγή βάσης ενός πλέγματος κατά Λένστρα–Λένστρα–Λοβάς (ΛΛΛ) είναι ένας αλγόριθμος πολυωνυμικού χρόνου που επινοήθηκε από τους Άριεν Λένστρα, Χέντρικ Λένστρα και Λάσλο Λοβάς το 1982.[1] Αν μας δοθεί μία βάση με ενός πλέγματος , ο ΛΛΛ αλγόριθμος υπολογίζει μία δ-ΛΛΛ-ανηγμένη βάση (μικρά μήκη διανυσμάτων, σχεδόν ορθογώνια) σε πολυωνυμικό χρόνο.

Ορισμός δ-ΛΛΛ ανηγμένης βάσης ενός πλέγματος[Επεξεργασία | επεξεργασία κώδικα]

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

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

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

και τους συντελεστές Γκραμ-Σμιτ

, για κάθε .

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

  1. Για . Εξ ορισμού, αυτή η ιδιότητα εξασφαλίζει τη μείωση του μήκους της διατεταγμένης βάσης (size-reduced) .
  2. Για k = 1,2,..,n (συνθήκη Λοβάς) .

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

Αρχικά, οι Α. Λένστρα, Χ. Λένστρα και Λ. Λοβάς απέδειξαν τον αλγόριθμο ΛΛΛ για . Ας σημειωθεί ότι αν και ο αλγόριθμος είναι καλά ορισμένος για , η πολυπλοκότητα πολυωνυμικού χρόνου εξασφαλίζεται μόνο για στο (0.25,1). Ο αλγόριθμος ΛΛΛ υπολογίζει ΛΛΛ ανηγμένες βάσεις. Δεν υπάρχει γνωστός αποδοτικός αλγόριθμος που υπολογίζει μια βάση της οποία τα διανύσματα είναι όσο το δυνατόν μικρά για πλέγματα με διάσταση μεγαλύτερη από 4. Ωστόσο, μια ανηγμένη κατά ΛΛΛ βάση είναι σχεδόν όσο το δυνατόν μικρότερη, με την έννοια ότι υπάρχουν όρια τέτοια ώστε το πρώτο διάνυσμα της βάσης δεν είναι παραπάνω από φορές το μικρότερο διάνυσμα του πλέγματος, για το δεύτερο διάνυσμα υπάρχει αντίστοιχα ένα , και ούτω καθεξής.

Αλγόριθμος αναγωγής κατά ΛΛΛ με χρήση Ευκλείδειας νόρμας[Επεξεργασία | επεξεργασία κώδικα]

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

ΔΕΔΟΜΕΝΑ:  (μια βάση του πλέγματος), παράμετρος ,  τυπική τιμή 
ΑΠΟΤΕΛΕΣΜΑΤΑ: Βάση ανηγμένη κατά LLL: 

ΑΛΓΟΡΙΘΜΟΣ:
Υπολόγισε την Γκραμ-Σμιτ βάση  και τους συντελεστές , για .
Υπολόγισε  για .


Όσο  επανάλαβε
{
    Για  μέχρι  με βήμα  επανάλαβε
    {
        
        
        Επανυπολόγισε τα  για 
    }
    Αν  τότε
        
    Αλλιώς
    {
        Εναλλαγή  με 
        Επανυπολόγισε τα  και  για , και  για 
        
    }
}


Παραδείγματα ανηγμένων κατά ΛΛΛ βάσεων[Επεξεργασία | επεξεργασία κώδικα]

Χρονική πολυπλοκότητα του αλγορίθμου ΛΛΛ[Επεξεργασία | επεξεργασία κώδικα]

Εφαρμογές του ΛΛΛ[Επεξεργασία | επεξεργασία κώδικα]

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. Lenstra, A. K.; Lenstra, H. W., Jr.; Lovász, L. (1982). «Factoring polynomials with rational coefficients». Mathematische Annalen 261 (4): 515–534. doi:10.1007/BF01457454. Πρότυπο:Hdl. MR 0682664. 
  2. Galbraith, Steven. «Mathematics of Public Key Cryptography». University of Auckland Mathematics Dept. Αρχειοθετήθηκε από το πρωτότυπο στις 20 Σεπτεμβρίου 2015. Ανακτήθηκε στις 29 Μαΐου 2015.