Your browser does not support JavaScript!

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

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

Προσθήκη στο καλάθι
[Προσθήκη στο καλάθι]
Κωδικός Πόρου 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
Συλλογή   Σχολή/Τμήμα--Σχολή Θετικών και Τεχνολογικών Επιστημών--Τμήμα Μαθηματικών και Εφαρμοσμένων Μαθηματικών--Μεταπτυχιακές εργασίες ειδίκευσης
  Τύπος Εργασίας--Μεταπτυχιακές εργασίες ειδίκευσης
Εμφανίσεις 163

Ψηφιακά τεκμήρια
No preview available

Προβολή Εγγράφου
Εμφανίσεις : 5