Τα προβλήματα του μικρότερου και εγγυτέρου διανύσματος στα δικτυωτά:
Creators: name: Αδαμούδης, Μάριος Αγγελου
Publisher: name: Aristotle University of Thessaloniki
Year: 2014
Subjects: Δικυτωτά και αλγόριθμοι
Vovoroicell algorithm
Closest vector problem
shortest vector problem

description: Το κύριο θέμα αυτής της διπλωματικής εργασίας είναι η έννοια των δικτυωτών και η επίλυση δύο θεμελιωδών προβλημάτων που αφορούν αυτά. Συγκεκριμένα μελετάται το πρόβλημα εύρεσης του μικρότερου μη μηδενικού στοιχείου ενός δικτυωτού (το οποίο ονομάζεται SVP) και το πρόβλημα εύρεσης του πλησιέστερου στοιχείου του δικτυωτού σε κάποιο δοθέν στοιχείο t (το οποίο ονομάζεται CVP). Τα προβλήματα αυτά βρίσκουν αρκετές εφαρμογές στα θεωρητικά αλλά και στα εφαρμοσμένα μαθηματικά. Κάποιες από αυτές είναι οι εξής: ακέραιος προγραμματισμός [15,16], παραγοντοποίηση πολυωνύμων με συντελεστές από το σύνολο των ρητών [17], έλεγχος επιλυσημότητας με ριζικά [18], όπως και στην εισβολή κρυπτοσυστημάτων [19,20]. Υπάρχουν προσεγγιστικές και ακριβείς λύσεις αυτών των προβλημάτων. Εμείς εδώ θα ασχοληθούμε με ακριβείς λύσεις διότι είναι εξίσου σημαντικές. Και τα δύο προβλήματα θεωρούνται δύσκολα και ανήκουν στην κλάση NP [8]. Ο καλύτερος αλγόριθμος που υπήρχε για να λύσει αυτά τα προβλήματα είχε βρεθεί από τον Kannan το 1983 [16]. Αυτός ο αλγόριθμος χρειαζόταν χρόνο n^(Ο(n) ) όπου n είναι η διάσταση του δικτυωτού. Έπειτα έγιναν κάποιες βελτιώσεις οι οποίες μείωσαν το άνω φράγμα του χρόνου σε n^0.184n για το SVP και σε n^0.5n για το CVP [21,22]. Στη συνέχεια έγινε μία σημαντική βελτίωση για το SVP από τους Atjai, Kumar και Sivakumar οι οποίοι βρήκαν αλγόριθμο που έλυνε το πρόβλημα σε χρόνο 2^(Ο(n) ) [23]. Στην εργασία παρουσιάζονται οι αλγόριθμοι VoronoiCell και ImprovedVoronoiCell οι οποίοι οφείλονται στους D. Minccianco και Π. Βούλγαρη, και λύνουν τα προβλήματα σε χρόνους O ̃(2^3.5n ) και O ̃(2^2.5n ) αντίστοιχα [3]. Ας σημειωθεί ότι ο χρόνος του ImprovedVoronoiCell μπορεί να μειωθεί σε O ̃(2^2n ) αντικαθιστώτας τον αλγόριθμο LLL που χρησιμοποιούμε στο αρχικό βήμα με τον OptPrerocessing [3]. Πιο συγκεκριμένα η εργασία περιέχει τα εξής: Στο κεφάλαιο 1 εισάγεται η έννοια των δικτυωτών και αποδεικνύονται κάποια κλασσικά θεωρήματα. Στο κεφάλαιο 2 παρουσιάζεται και αποδεικνύεται ο αλγόριθμος LLL, ο οποίος και από μόνος του λύνει προσεγγιστικά τα SVP και CVP. Στο κεφάλαιο 3 εισάγεται η έννοια του Voronoi κελιού ενός δικτυωτού και αναλύεται ο αλγόριθμος VoronoiCell. Στο κεφάλαιο 4 εισάγεται ο αλγόριθμος ENUM_2V ο οποίος είναι απαραίτητος στην ανάπτυξη του ImprovedVoronoiCell. Έπειτα παρουσίαζεται ο ImprovedVoronoiCell.
description: Our main goal is to present the concept of lattices and to investigate two fundamental problems. These problems are called shortest vector problem (SVP) and closest vector problem (CVP). These problems play an important role in many computer science and communication theory applications. Some of these applications are integer programming [15,16], factoring polynomials over rationals [17], checking the solvability by radicals [18], and finally in cryptanalysis [19,20]. There are approximate and exact solutions to these problems. We are focus on the complexity of finding exact solutions. These problems are difficult and they belong to NP class [8]. The best deterministic algorithm any of these lattice problems was essential the one discovered by Kannan in 1983 running in time n^(Ο(n) ), where n is the dimrnsion of the lattice [16]. Subsequent work led to improvements in the constant in the exponent, mostly through a better analysis, reducing the upper bound on the running time down to n^0.184n for SVP and n^0.5n for CVP [21,22]. Later Atjai, Kumar and Sivakumar discover an algorithm for SVP running in time〖 2〗^(Ο(n) ) [23]. Here we present the algorithms VoronoiCell and ImprovedVoronoiCell discovered by D. Minccianco and P.Voulgari and solve both problems in time O ̃(2^3.5n ) and O ̃(2^2.5n ) respectively [3]. We mention here that the time of ImprovedVoronoiCell can be reduced to O ̃(2^2n ) if we replace LLL algorithm that we use in first pace with OptPrerocessing [3]. More precisely we have In chapter 1 we introduce the concept of lattices and prove some classic theorems. In chapter 2 we introduce and prove LLL algorithm which can be solve SVP and CVP approximately In chapter 3 we introduce the concept of Voronoi cell of a lattice and analyse the VoronoiCell algorithm In chapter 4 we analyse the ENUM_2V algorithm which is very important. Then we analyse ImprovedVoronoiCell