Adobe PDF (1.18 MB)
Title Details:
Primality Tests
Authors: Draziotis, Konstantinos
Description:
Abstract:
Σε αυτό το κεφάλαιο παρουσιάζουμε κάποιους αλγορίθμους που χρησιμοποιούμε, για να ελέγχουμε αν ένας φυσικός αριθμός είναι πρώτος. Οι αλγόριθμοι αυτοί είναι πιθανοτικοί και αποφαίνονται με κάποια πιθανότητα για το αποτέλεσμα. Αυτοί οι αλγόριθμοι είναι απαραίτητοι, γιατί πάρα πολλά κρυπτοσυστήματα δημοσίου κλειδιού απαιτούν να γνωρίζουμε μεγάλους πρώτους. Συνήθως μεγάλος πρώτος στην κρυπτογραφία θεωρείται ένας πρώτος αριθμός με τουλάχιστον 2048 δυαδικά ψηφία. Θα δούμε το τεστ του Fermat και το τεστ των Miller-Rabin. Το δεύτερο χρησιμοποιείται και σήμερα κατά την παραγωγή πρώτων αριθμών, για παράδειγμα, από το openssl. ΄Ολα τα κριτήρια που χρησιμοποιούμε στην πράξη είναι πιθανοτικά. Παρόλα αυτά, ένα πολύ ισχυρό αποτέλεσμα των Agrawal, Kayal, Saxena, λέει ότι υπάρχει ντετερμινιστικός αλγόριθμος πολυωνυμικού χρόνου, για να ελέγξουμε αν ένας φυσικός αριθμός είναι πρώτος. Στην πράξη αυτός ο αλγόριθμος είναι αρκετά αργός, παρότι είναι πολυωνυμικού χρόνου.
Linguistic Editors: Triantafyllidou, Georgia
Technical Editors: Draziotis, Konstantinos
Graphic Editors: Draziotis, Konstantinos
Type: Chapter
Creation Date: 2022
Item Details:
License: Attribution - NonCommercial - ShareAlike 4.0 International (CC BY-NC-SA 4.0)
Handle http://hdl.handle.net/11419/8190
Bibliographic Citation: Draziotis, K. (2022). Primality Tests [Chapter]. In Draziotis, K. 2022. Introduction to Cryptography [Undergraduate textbook]. Kallipos, Open Academic Editions. chapter 9. http://hdl.handle.net/11419/8190
Language: Greek
Is Part of: Introduction to Cryptography
Publication Origin: Kallipos, Open Academic Editions