Αλγοριθμική πιστοποίηση πρώτων αριθμών
Loading...
Date
2022-07-21
Authors
Σταμάτης, Βασίλειος
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Το πρόβλημα της πιστοποίησης πρωτείας
(πιστοποίηση ενός φυσικού αριθμού ως πρώτου) είναι ένα αντικείμενο το οποίο απασχολούσε τους μαθηματικούς, από τα αρχαία χρόνια. Με την «γέννηση» της επιστήμης των υπολογιστών, τον προηγούμενο αιώνα, δόθηκε έναυσμα στους επιστήμονες, να ερευνήσουν και να κατασκευάσουν «γρήγορους» αλγορίθμους που πιστοποιούν πρώτους. Στην διπλωματική εργασία αυτή, παρουσιάζονται διάφοροι αλγόριθμοι πιστοποίησης πρωτείας ή συνθετότητας. Οι αλγόριθμοι αυτοί συγκρίνονται ως προς την ταχύτητα τους, τον χώρο που απαιτούν υπολογιστικά και την πιθανότητα σφάλματος τους. Παρουσιάζονται και αποδεικνύονται θεωρήματα και διάφορα λήμματα της θεωρίας αριθμών που απαιτούνται, κατά κύριο λόγο, στην απόδειξη ορθότητας των αλγορίθμων.
Description
Keywords
Αλγοριθμητική πιστοποίηση πρώτων αριθμών