Ελλειπτικές καμπύλες και πιστοποίηση πρώτου
Creators: name: Λαμπρόπουλος, Χαρίσιος Νικολάου
Publisher: name: Aristotle University of Thessaloniki
Year: 2008
Subjects: Ελλειπτικές καμπύλες
Πιστοποίηση πρώτου
Ελλειπτικό τεστ
Elliptic curves
Primality proving
Elliptic test

description: Η πιστοποίηση πρώτου είναι μία διαδικασία απόδειξης, αν ένας αριθμός είναι πρώτος. Υπάρχουν πολλές περιπτώσεις που κάποιος θέλει να ξέρει, αν ένας μεγάλος αριθμός 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 καταγράφονται με σειρά εξέλιξης τα ελλειπτικά τεστ πιστοποίησης πρώτου, αναλύονται οι αλγόριθμοι εκτέλεσης τους και υπολογίζεται η πολυπλοκότητα τους.
description: 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.