E-Locus - Ιδρυματικό Καταθετήριο Πανεπιστημίου Κρήτης - Έλεγχος πρώτων αριθμών : πιθανοθεωρητικοί και ντετερμινιστικοί αλγόριθμοι

Αρχική Έλεγχος πρώτων αριθμών : πιθανοθεωρητικοί και ντετερμινιστικοί αλγόριθμοι

Αποτελέσματα - Λεπτομέρειες

[Προσθήκη στο καλάθι]

Κωδικός Πόρου

000415082

Τίτλος

Έλεγχος πρώτων αριθμών : πιθανοθεωρητικοί και ντετερμινιστικοί αλγόριθμοι

Άλλος τίτλος

Primality testing

Συγγραφέας

Μανιού, Δήμητρα

Σύμβουλος διατριβής

Κολουντζάκης, Μιχάλης

Μέλος κριτικής επιτροπής

Τζανάκης, Νικόλαος
Γαρεφαλάκης, Θεόδουλος

Περίληψη

Το αντικείμενο της εργασίας είναι ο έλεγχος πρώτων αριθμών. Ειδικότερα, θα ασχοληθούμε με πιθανοθεωρητικούς και ντετερμινιστικούς αλγορίθμους, οι οποίοι εξετάζουν αν ένας ακέραιος p είναι πρώτος, απαιτώντας πολυωνυμικό χρόνο ως προς το μέγεθος γραφής του p, δηλ. ως προς το log p. Αρχικά αναφερόμαστε στο θεώρημα του Pratt ότι υπάρχει πολυωνυμικός αλγόριθμος πιστοποίησης για πρώτους αριθμούς. Υπάρχει δηλ. αλγόριθμος πολυωνυμικού χρόνου ως προς το log p που, δοθέντος του p και κάποιας επιπλέον πληροφορίας (το «πιστοποιητικό»), μπορεί να επαληθεύσει ότι ο p όντως είναι πρώτος αριθμός. Στη συνέχεια, περιγράφουμε τρεις πιθανοθεωρητικούς αλγορίθμους, τον έλεγχο Fermat, τον έλεγχο Miller-Rabin, καθώς και τον έλεγχο Solovay-Strassen. Οι αλγόριθμοι αυτοί, με είσοδο έναν πρώτο αριθμό n, επιστρέφουν την έξοδο «πρώτος», ενώ με είσοδο έναν σύνθετο αριθμό n επιστρέφουν την σωστή απάντηση «σύνθετος» με πιθανότητα μεγαλύτερη του 12 . Τέλος, παρουσιάζουμε τον ντετερμινιστικό αλγόριθμο πολυωνυμικού χρόνου των Agrawal, Kayal και Saxena για τον έλεγχο πρώτων αριθμών, καθώς και την απόδειξη της ορθότητάς του.

Φυσική περιγραφή

47 σ. ; : ; 30 εκ.

Γλώσσα

Ελληνικά

Θέμα

Fermat test

Miller-Rabin test

Prime number

Έλεγχος Fermat

Ημερομηνία έκδοσης

2018-3-23

Συλλογή