Τεστ Πιστοποίησης πρώτων αριθμών

Abstract

Σε αυτό το κεφάλαιο παρουσιάζουμε κάποιους αλγορίθμους που χρησιμοποιούμε, για να ελέγχουμε αν ένας φυσικός αριθμός είναι πρώτος. Οι αλγόριθμοι αυτοί είναι πιθανοτικοί και αποφαίνονται με κάποια πιθανότητα για το αποτέλεσμα. Αυτοί οι αλγόριθμοι είναι απαραίτητοι, γιατί πάρα πολλά κρυπτοσυστήματα δημοσίου κλειδιού απαιτούν να γνωρίζουμε μεγάλους πρώτους. Συνήθως μεγάλος πρώτος στην κρυπτογραφία θεωρείται ένας πρώτος αριθμός με τουλάχιστον 2048 δυαδικά ψηφία. Θα δούμε το τεστ του Fermat και το τεστ των Miller-Rabin. Το δεύτερο χρησιμοποιείται και σήμερα κατά την παραγωγή πρώτων αριθμών, για παράδειγμα, από το openssl. ΄Ολα τα κριτήρια που χρησιμοποιούμε στην πράξη είναι πιθανοτικά. Παρόλα αυτά, ένα πολύ ισχυρό αποτέλεσμα των Agrawal, Kayal, Saxena, λέει ότι υπάρχει ντετερμινιστικός αλγόριθμος πολυωνυμικού χρόνου, για να ελέγξουμε αν ένας φυσικός αριθμός είναι πρώτος. Στην πράξη αυτός ο αλγόριθμος είναι αρκετά αργός, παρότι είναι πολυωνυμικού χρόνου.

Σε αυτό το κεφάλαιο παρουσιάζουμε κάποιους αλγορίθμους που χρησιμοποιούμε, για να ελέγχουμε αν ένας φυσικός αριθμός είναι πρώτος. Οι αλγόριθμοι αυτοί είναι πιθανοτικοί και αποφαίνονται με κάποια πιθανότητα για το αποτέλεσμα. Αυτοί οι αλγόριθμοι είναι απαραίτητοι, γιατί πάρα πολλά κρυπτοσυστήματα δημοσίου κλειδιού απαιτούν να γνωρίζουμε μεγάλους πρώτους. Συνήθως μεγάλος πρώτος στην κρυπτογραφία θεωρείται ένας πρώτος αριθμός με τουλάχιστον 2048 δυαδικά ψηφία. Θα δούμε το τεστ του Fermat και το τεστ των Miller-Rabin. Το δεύτερο χρησιμοποιείται και σήμερα κατά την παραγωγή πρώτων αριθμών, για παράδειγμα, από το openssl. ΄Ολα τα κριτήρια που χρησιμοποιούμε στην πράξη είναι πιθανοτικά. Παρόλα αυτά, ένα πολύ ισχυρό αποτέλεσμα των Agrawal, Kayal, Saxena, λέει ότι υπάρχει ντετερμινιστικός αλγόριθμος πολυωνυμικού χρόνου, για να ελέγξουμε αν ένας φυσικός αριθμός είναι πρώτος. Στην πράξη αυτός ο αλγόριθμος είναι αρκετά αργός, παρότι είναι πολυωνυμικού χρόνου.