Τεστ Πιστοποίησης πρώτων αριθμών
Σε αυτό το κεφάλαιο παρουσιάζουμε κάποιους αλγορίθμους που χρησιμοποιούμε, για να ελέγχουμε αν ένας φυσικός αριθμός είναι πρώτος. Οι αλγόριθμοι αυτοί είναι πιθανοτικοί και αποφαίνονται με κάποια πιθανότητα για το αποτέλεσμα. Αυτοί οι αλγόριθμοι είναι απαραίτητοι, γιατί πάρα πολλά κρυπτοσυστήματα δημ...
| Κύριοι συγγραφείς: | , |
|---|---|
| Μορφή: | 7 |
| Γλώσσα: | Greek |
| Έκδοση: |
2022
|
| Διαθέσιμο Online: | http://repository.kallipos.gr/handle/11419/8190 |
| id |
kallipos-11419-8190 |
|---|---|
| record_format |
dspace |
| spelling |
kallipos-11419-81902022-03-16T15:57:53Z Τεστ Πιστοποίησης πρώτων αριθμών Primality Tests Δραζιώτης, Κωνσταντίνος Draziotis, Konstantinos Σε αυτό το κεφάλαιο παρουσιάζουμε κάποιους αλγορίθμους που χρησιμοποιούμε, για να ελέγχουμε αν ένας φυσικός αριθμός είναι πρώτος. Οι αλγόριθμοι αυτοί είναι πιθανοτικοί και αποφαίνονται με κάποια πιθανότητα για το αποτέλεσμα. Αυτοί οι αλγόριθμοι είναι απαραίτητοι, γιατί πάρα πολλά κρυπτοσυστήματα δημοσίου κλειδιού απαιτούν να γνωρίζουμε μεγάλους πρώτους. Συνήθως μεγάλος πρώτος στην κρυπτογραφία θεωρείται ένας πρώτος αριθμός με τουλάχιστον 2048 δυαδικά ψηφία. Θα δούμε το τεστ του Fermat και το τεστ των Miller-Rabin. Το δεύτερο χρησιμοποιείται και σήμερα κατά την παραγωγή πρώτων αριθμών, για παράδειγμα, από το openssl. ΄Ολα τα κριτήρια που χρησιμοποιούμε στην πράξη είναι πιθανοτικά. Παρόλα αυτά, ένα πολύ ισχυρό αποτέλεσμα των Agrawal, Kayal, Saxena, λέει ότι υπάρχει ντετερμινιστικός αλγόριθμος πολυωνυμικού χρόνου, για να ελέγξουμε αν ένας φυσικός αριθμός είναι πρώτος. Στην πράξη αυτός ο αλγόριθμος είναι αρκετά αργός, παρότι είναι πολυωνυμικού χρόνου. Σε αυτό το κεφάλαιο παρουσιάζουμε κάποιους αλγορίθμους που χρησιμοποιούμε, για να ελέγχουμε αν ένας φυσικός αριθμός είναι πρώτος. Οι αλγόριθμοι αυτοί είναι πιθανοτικοί και αποφαίνονται με κάποια πιθανότητα για το αποτέλεσμα. Αυτοί οι αλγόριθμοι είναι απαραίτητοι, γιατί πάρα πολλά κρυπτοσυστήματα δημοσίου κλειδιού απαιτούν να γνωρίζουμε μεγάλους πρώτους. Συνήθως μεγάλος πρώτος στην κρυπτογραφία θεωρείται ένας πρώτος αριθμός με τουλάχιστον 2048 δυαδικά ψηφία. Θα δούμε το τεστ του Fermat και το τεστ των Miller-Rabin. Το δεύτερο χρησιμοποιείται και σήμερα κατά την παραγωγή πρώτων αριθμών, για παράδειγμα, από το openssl. ΄Ολα τα κριτήρια που χρησιμοποιούμε στην πράξη είναι πιθανοτικά. Παρόλα αυτά, ένα πολύ ισχυρό αποτέλεσμα των Agrawal, Kayal, Saxena, λέει ότι υπάρχει ντετερμινιστικός αλγόριθμος πολυωνυμικού χρόνου, για να ελέγξουμε αν ένας φυσικός αριθμός είναι πρώτος. Στην πράξη αυτός ο αλγόριθμος είναι αρκετά αργός, παρότι είναι πολυωνυμικού χρόνου. 2022-03-16T14:57:15Z 2022-03-16T14:57:15Z 7 http://repository.kallipos.gr/handle/11419/8190 el 1 application/pdf |
| institution |
Kallipos |
| collection |
DSpace |
| language |
Greek |
| description |
Σε αυτό το κεφάλαιο παρουσιάζουμε κάποιους αλγορίθμους που χρησιμοποιούμε, για να ελέγχουμε αν ένας φυσικός αριθμός είναι πρώτος. Οι αλγόριθμοι αυτοί είναι πιθανοτικοί και αποφαίνονται με κάποια πιθανότητα για το αποτέλεσμα. Αυτοί οι αλγόριθμοι είναι απαραίτητοι, γιατί πάρα πολλά κρυπτοσυστήματα δημοσίου κλειδιού απαιτούν να γνωρίζουμε μεγάλους πρώτους. Συνήθως μεγάλος πρώτος στην κρυπτογραφία θεωρείται ένας πρώτος αριθμός με τουλάχιστον 2048 δυαδικά ψηφία. Θα δούμε το τεστ του Fermat και το τεστ των Miller-Rabin. Το δεύτερο χρησιμοποιείται και σήμερα κατά την παραγωγή πρώτων αριθμών, για παράδειγμα, από το openssl. ΄Ολα τα κριτήρια που χρησιμοποιούμε στην πράξη είναι πιθανοτικά. Παρόλα αυτά, ένα πολύ ισχυρό αποτέλεσμα των Agrawal, Kayal, Saxena, λέει ότι υπάρχει ντετερμινιστικός αλγόριθμος πολυωνυμικού χρόνου, για να ελέγξουμε αν ένας φυσικός αριθμός είναι πρώτος. Στην πράξη αυτός ο αλγόριθμος είναι αρκετά αργός, παρότι είναι πολυωνυμικού χρόνου. |
| format |
7 |
| author |
Δραζιώτης, Κωνσταντίνος Draziotis, Konstantinos |
| spellingShingle |
Δραζιώτης, Κωνσταντίνος Draziotis, Konstantinos Τεστ Πιστοποίησης πρώτων αριθμών |
| author_facet |
Δραζιώτης, Κωνσταντίνος Draziotis, Konstantinos |
| author_sort |
Δραζιώτης, Κωνσταντίνος |
| title |
Τεστ Πιστοποίησης πρώτων αριθμών |
| title_short |
Τεστ Πιστοποίησης πρώτων αριθμών |
| title_full |
Τεστ Πιστοποίησης πρώτων αριθμών |
| title_fullStr |
Τεστ Πιστοποίησης πρώτων αριθμών |
| title_full_unstemmed |
Τεστ Πιστοποίησης πρώτων αριθμών |
| title_sort |
τεστ πιστοποίησης πρώτων αριθμών |
| publishDate |
2022 |
| url |
http://repository.kallipos.gr/handle/11419/8190 |
| work_keys_str_mv |
AT draziōtēskōnstantinos testpistopoiēsēsprōtōnarithmōn AT draziotiskonstantinos testpistopoiēsēsprōtōnarithmōn AT draziōtēskōnstantinos primalitytests AT draziotiskonstantinos primalitytests |
| _version_ |
1771301275136163840 |
