| Περίληψη: | Το πρόβλημα της πιστοποίησης πρωτείας
(πιστοποίηση ενός φυσικού αριθμού ως πρώτου) είναι ένα αντικείμενο το οποίο απασχολούσε τους μαθηματικούς, από τα αρχαία χρόνια. Με την «γέννηση» της επιστήμης των υπολογιστών, τον προηγούμενο αιώνα, δόθηκε έναυσμα στους επιστήμονες, να ερευνήσουν και να κατασκευάσουν «γρήγορους» αλγορίθμους που πιστοποιούν πρώτους. Στην διπλωματική εργασία αυτή, παρουσιάζονται διάφοροι αλγόριθμοι πιστοποίησης πρωτείας ή συνθετότητας. Οι αλγόριθμοι αυτοί συγκρίνονται ως προς την ταχύτητα τους, τον χώρο που απαιτούν υπολογιστικά και την πιθανότητα σφάλματος τους. Παρουσιάζονται και αποδεικνύονται θεωρήματα και διάφορα λήμματα της θεωρίας αριθμών που απαιτούνται, κατά κύριο λόγο, στην απόδειξη ορθότητας των αλγορίθμων.
|
|---|
