Αναγωγή Lenstra–Lenstra–Lovász (LLL)

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Πήδηση στην πλοήγηση Πήδηση στην αναζήτηση

H αναγωγή βάσης ενός πλέγματος κατά Lenstra–Lenstra–Lovász (LLL) είναι ένας αλγόριθμος πολυωνυμικού χρόνου που επινοήθηκε από τους Arjen Lenstra, Hendrik Lenstra και László Lovász το 1982.[1] Αν μας δοθεί μία βάση με ενός πλέγματος , ο LLL αλγόριθμος υπολογίζει μία δ-LLL-ανηγμένη βάση (μικρά μήκη διανυσμάτων, σχεδόν ορθογώνια) σε πολυωνυμικό χρόνο.

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

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

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

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

και τους συντελεστές Gram–Schmidt

, για κάθε .

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

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

Στα παραπάνω, εκτιμώντας την τιμή της παραμέτρου , μπορούμε να συμπεράνουμε πόσο καλά είναι ανηγμένη η βάση. Μεγαλύτερες τιμές του οδηγούν σε ισχυρότερη αναγωγή της βάσης. Αρχικά, οι A. Lenstra, H. Lenstra και L. Lovász απέδειξαν τον αλγόριθμο LLL για . Ας σημειωθεί ότι αν και ο αλγόριθμος είναι καλά ορισμένος για , η πολυπλοκότητα πολυωνυμικού χρόνου εξασφαλίζεται μόνο για στο (0.25,1). Ο αλγόριθμος LLL υπολογίζει LLL ανηγμένες βάσεις. Δεν υπάρχει γνωστός αποδοτικός αλγόριθμος που υπολογίζει μια βάση της οποία τα διανύσματα είναι όσο το δυνατόν μικρά για πλέγματα με διάσταση μεγαλύτερη από 4. Ωστόσο, μια ανηγμένη κατά LLL βάση είναι σχεδόν όσο το δυνατόν μικρότερη, με την έννοια ότι υπάρχουν όρια τέτοια ώστε το πρώτο διάνυσμα της βάσης δεν είναι παραπάνω από φορές το μικρότερο διάνυσμα του πλέγματος, για το δεύτερο διάνυσμα υπάρχει αντίστοιχα ένα , και ούτω καθεξής.

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

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

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

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


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


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

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

Εφαρμογές του 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. Ανακτήθηκε στις 29 May 2015.