δείτε την πρωτότυπη σελίδα τεκμηρίου
στον ιστότοπο του αποθετηρίου του φορέα για περισσότερες πληροφορίες και για να δείτε όλα τα ψηφιακά αρχεία του τεκμηρίου*
κοινοποιήστε το τεκμήριο




2008 (EL)
Ελλειπτικές καμπύλες και πιστοποίηση πρώτου
Elliptic curves and primality proving

Λαμπρόπουλος, Χαρίσιος Νικολάου

We describe two primality testing algorithms due to Goldwasser-Kilian that uses ellipticcurves over finite fields and due to Atkin-Morain that uses uses elliptic curves over finitefields and the theory of complex multiplication. In particular we explain how the use ofclass fields and genus theory can improve the running time of the first elliptic primalitytest. We sketch the actual implementation of this test on testing large prime numbers andwe provide a certificate of primality for them. Finally, we present fastECPP primalitytest, which is a variant of ECPP primality test and is the cutting edge of its kind.
Η πιστοποίηση πρώτου είναι μία διαδικασία απόδειξης, αν ένας αριθμός είναι πρώτος. Υπάρχουν πολλές περιπτώσεις που κάποιος θέλει να ξέρει, αν ένας μεγάλος αριθμός n είναι πρώτος. Π.χ. στο κρυπτοσύστημα δημοσίου κλειδιού RSA και σε διάφορα κρυπτοσυστήματα που βασίζονται στο πρόβλημα του διακριτού λογαρίθμου σε πεπερασμένα σώματα, απαιτείται η εύρεση ενός μεγάλου πρώτου αριθμού. Έτσι, αν θέλουμε να κατασκευάσουμε έναν οποιοδήποτε πρώτο αριθμό με συγκεκριμένο πλήθος ψηφίων, δεν έχουμε παρά να διαλέξουμε έναν μεγάλο ακέραιο n0 και να ελέγξουμε τους αριθμούς n0 , n0 + 1, n0 + 2 ,…, αν είναι πρώτοι με ένα τεστ πιστοποίησης πρώτου. Η πιστοποίηση πρώτου αποτελεί μέχρι σήμερα ένα από τα πιο ενδιαφέροντα προβλήματα της αλγοριθμικής θεωρίας αριθμών. Σήμερα, ο πιο γρήγορος ντετερμινιστικός αλγόριθμος πιστοποίησης πρώτου είναι ο AKS, o οποίος πραγματώνει τον έλεγχο ενός υποψήφιου πρώτου n με πολυπλοκότητα O(log6+ε n) . Εν τούτοις, υπάρχουν αρκετοί αλγόριθμοι ελέγχου πρώτων αριθμών που εκτελούνται σε μικρότερο χρόνο από τον AKS, αλλά δεν είναι αξιόπιστοι για το αποτέλεσμα τους. Δύο τέτοιοι μη ντετερμινιστικοί αλγόριθμοι είναι ο αλγόριθμος των Miller-Rabin και ο αλγόριθμος των Solovay–Strassen με πολυπλοκότητα O(k ⋅ log3n) , όπου k ο αριθμός των επαναλήψεων για την εύρεση αυστηρής απόδειξης με πιθανότητα επιτυχίας ≤ 1 - 1/nk . Αξίζει να σημειώσουμε, ότι υπάρχει μία παραλλαγή του αλγορίθμου Miller-Rabin που καθιστά τον νέο αλγόριθμο ντετερμινιστικό και πραγματώνει τον έλεγχο ενός υποψήφιου πρώτου n με πολυπλοκότητα O(log4n) , αλλά βασίζεται στην αναπόδεικτη γενικευμένη εικασία του Riemann. Εκτός από την κατηγορία αυτών των ντετερμινιστικών και μη-ντετερμινιστικών τεστ πιστοποίησης πρώτου, υπάρχει και ένα άλλο είδος τεστ που εφαρμόζεται πολύ καλά στην πράξη. Πρόκειται για την πιστοποίηση πρώτου με ελλειπτικές καμπύλες. Αυτό το είδος πιστοποίησης υλοποιείται σε πολυωνυμικό κατά μέσο όρο χρόνο και επιστρέφει πάντα σωστό αποτέλεσμα. Συγκεκριμένα δύο τεστ πιστοποίησης πρώτου με ελλειπτικές καμπύλες είναι το τεστ των Goldwasser-Kilian και Atkin-Morain, με πολυπλοκότητα O(log11n) και O(log6n) αντίστοιχα. Αυτός είναι ένας από τους δύο κύριους σκοπούς αυτής της διπλωματικής εργασίας. Ο δεύτερος κατά επέκταση σκοπός αφορά την ανάλυση του βέλτιστου μέχρι σήμερα αλγορίθμου γι’ αυτή τη διαδικασία. Στο πρώτο κεφάλαιο της παρούσης εργασίας γίνεται μελέτη των αλγεβρικών καμπύλων, ενώ στο δεύτερο ορίζονται οι ελλειπτικές καμπύλες και αναλύονται οι ιδιότητες τους. Στο τρίτο κεφάλαιο εισάγονται η έννοια της ελλειπτικής καμπύλης με μιγαδικό πολλαπλασιασμό, αλλά και προκαταρκτικές έννοιες από τη θεωρία αριθμών και την αλγεβρική θεωρία αριθμών, ώστε να επεκτείνουμε τις ιδιότητες των ελλειπτικών καμπύλων. Το κεφάλαιο 4 παρουσιάζει το μοντέλο πιστοποίησης πρώτου με ελλειπτικές καμπύλες και περιλαμβάνει την κατασκευή πιστοποιητικών για τον υποψήφιο πρώτο που ελέγχεται. Τέλος στο κεφάλαιο 5 καταγράφονται με σειρά εξέλιξης τα ελλειπτικά τεστ πιστοποίησης πρώτου, αναλύονται οι αλγόριθμοι εκτέλεσης τους και υπολογίζεται η πολυπλοκότητα τους.

info:eu-repo/semantics/masterThesis
Postgraduate Thesis / Μεταπτυχιακή Εργασία

Ελλειπτικό τεστ
Primality proving
Elliptic curves
Ελλειπτικές καμπύλες
Πιστοποίηση πρώτου
Elliptic test

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

Ελληνική γλώσσα
Αγγλική γλώσσα

2008
2009-06-21T21:00:00Z


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

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



*Η εύρυθμη και αδιάλειπτη λειτουργία των διαδικτυακών διευθύνσεων των συλλογών (ψηφιακό αρχείο, καρτέλα τεκμηρίου στο αποθετήριο) είναι αποκλειστική ευθύνη των αντίστοιχων Φορέων περιεχομένου.