Αλγοριθμική επίλυση δύσκολων προβλημάτων Knapsack

 
see the original item page
in the repository's web site and access all digital files if the item*
share




2016 (EN)
Αλγοριθμική επίλυση δύσκολων προβλημάτων Knapsack

Δαραβίγκας, Ευάγγελος

Η συγκεκριμένη εργασία αποτελεί μια πρακτική εφαρμογή της αλγοριθμικής τυχαιοποιημένης μεθόδου εφαρμογής του BKZ, που αναπτύχθηκε από τους Schnorr και Shevchenko για την επίλυση του Προβλήματος του Σακιδίου (Subset Sum Problem). Αρχικά, περιγράφονται οι απαραίτητες μαθηματικές έννοιες και στοιχεία που χρειάζονται για την ανάλυση του προβλήματος και την ανάπτυξη του αλγορίθμου. Στη συνέχεια γίνεται συσχέτιση με το πεδίο της Κρυπτογραφίας. Ακολουθεί η ανάπτυξη του αλγορίθμου με χρήση τoυ αλγεβρικού υπολογιστικού συστήματος SageMath και παρουσιάζονται τα αποτελέσματα που προέκυψαν. Κατόπιν, αναπτύσσεται ο αλγορίθμος στη γλώσσα προγραμματισμού C/C++, με χρήση της βιβλιοθήκης fpLLL, με στόχο την αποδοτικότερη εκτέλεσή του. Όπως και προηγουμένος, δίνουμε και τα αποτελέσματα των πειραμάτων που εκτελέστηκαν με την τελευταία υλοποίηση σε C/C++ . Τέλος, προτείνονται πιθανές μελλοντικές επεκτάσεις που θα μπορούσε να έχει αυτή η εργασία.
The project is the practical implementation of the "randomized" BKZ algorithm as described by Schnorr and Shevchenko in order to solve the Problem of Knapsack (Subset Sum Problem). Initially, are described the required mathematical preliminaries for the problem analysis and the deployment of the algorithm. Following that, there is the correlation with the field of Cryptography. Afterwards, the algorithm is developed with the use of the algebraic computational system SageMath and the generated results are presented. Next, the algorithm is developed with the use of the programming language C/C++ and the fpLLL library, by aiming to a more efficient execution. As before, the generated results are presented. Finally, there are suggested some possible future expansions that this project may have.

info:eu-repo/semantics/bachelorThesis
Graduate Thesis / Πτυχιακή Εργασία

Knapsack Problem
Πλέγμα
Πρόβλημα του Σακιδίου
Cryptography
Κρυπτογραφία
Lattice

Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης (EL)
Aristotle University of Thessaloniki (EN)

Greek

2016-11-08T09:06:16Z
2016


Αριστοτέλειο Πανεπιστήμιο Θεσσαλονίκης, Σχολή Θετικών Επιστημών, Τμήμα Πληροφορικής

This record is part of 'IKEE', the Institutional Repository of Aristotle University of Thessaloniki's Library and Information Centre found at http://ikee.lib.auth.gr. Unless otherwise stated above, the record metadata were created by and belong to Aristotle University of Thessaloniki Library, Greece and are made available to the public under Creative Commons Attribution-ShareAlike 4.0 International license (http://creativecommons.org/licenses/by-sa/4.0). Unless otherwise stated in the record, the content and copyright of files and fulltext documents belong to their respective authors. Out-of-copyright content that was digitized, converted, processed, modified, etc by AUTh Library, is made available to the public under Creative Commons Attribution-ShareAlike 4.0 International license (http://creativecommons.org/licenses/by-sa/4.0). You are kindly requested to make a reference to AUTh Library and the URL of the record containing the resource whenever you make use of this material.
info:eu-repo/semantics/openAccess



*Institutions are responsible for keeping their URLs functional (digital file, item page in repository site)