Αλγοριθμική θεωρία αριθμών
Η αλγοριθμική θεωρία αριθμών είναι ένας κλάδος της θεωρίας αριθμών, η οποία αποτελεί από μόνη της κλάδο των μαθηματικών. Ασχολείται με το ζήτημα των αποτελεσματικών αλγοριθμικών λύσεων σε αριθμοθεωρητικά ζητήματα.[1]
Οι κύριοι τομείς της αλγοριθμικής θεωρίας αριθμών είναι οι εξής
- Δοκιμές πρώτων αριθμών
- διαδικασίες παραγοντοποίησης ακέραιων αριθμών
- υπολογισμός του διακριτού λογαρίθμου.
Για να το κάνουμε αυτό, χρειαζόμαστε άλλες διαδικασίες που επίσης μελετώνται:
- γρήγορος πολλαπλασιασμός
- γρήγορη δύναμη
- υπολογισμός του μεγαλύτερου κοινού διαιρέτη με τον αλγόριθμο του Ευκλείδη
- υπολογισμός του συμβόλου Jacobi χρησιμοποιώντας το νόμο της τετραγωνικής αμοιβαιότητας
- Παραγοντοποίηση πολυωνύμων, ιδίως επίσης γρήγορη εξαγωγή ριζών.
Νέα ερευνητικά αποτελέσματα στην αλγοριθμική θεωρία αριθμών παρουσιάζονται στο συνέδριο ANTS (Συμπόσιο για την αλγοριθμική θεωρία αριθμών), το οποίο διεξάγεται κάθε δύο χρόνια από το 1994.
Εφαρμογές
[Επεξεργασία | επεξεργασία κώδικα]Η κύρια εφαρμογή της αλγοριθμικής θεωρίας αριθμών είναι η κρυπτογραφία. Παραδείγματος χάριν, η μέθοδος RSA[2] εκμεταλλεύεται το γεγονός ότι η ιδιότητα πρώτου αριθμού μπορεί να επαληθευτεί γρήγορα, ωστόσο δεν είναι γνωστή μέχρι σήμερα μια τόσο γρήγορη μέθοδος για την παραγοντοποίηση ενός σύνθετου αριθμού (δηλαδή ενός αριθμού που δεν είναι πρώτος). Σε αυτό το γεγονός βασίζεται η ασφάλεια της μετάδοσης δεδομένων μέσω του Διαδικτύου. Έχοντας αυτό κατά νου, η RSA Security προσέφερε μεγάλα χρηματικά ποσά σε όποιον μπορούσε να παραγοντοποιήσει ορισμένους αριθμούς[3].
Πέρα της κρυπτογραφίας και της μετα-κβαντικής κρυπτογραφίας, χρησιμοποιείται επίσης για τη μελέτη εικασιών και ανοικτών προβλημάτων στη θεωρία αριθμών, συμπεριλαμβανομένης της υπόθεσης Ρίμαν, την εικασία Μπέρτς και Σουίνερτον-Ντάιερ, την εικασία ABC, την εικασία της αρθρωτότητας, την εικασία Σάτο-Τάτε και ρητές πτυχές του προγράμματος Λάνγκλαντς[3][4][5].
Δημοσιεύσεις
[Επεξεργασία | επεξεργασία κώδικα]- Eric Bach· Jeffrey Shallit (1996). Algorithmic Number Theory, Volume 1: Efficient Algorithms. MIT Press. ISBN 0-262-02405-5.
- David M. Bressoud (1989). Factorisation and Primality Testing
. Springer-Verlag. ISBN 0-387-97040-1.
- Joe P. Buhler· Peter Stevenhagen, επιμ. (2008). Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography. MSRI Publications. 44. Cambridge University Press. ISBN 978-0-521-20833-8. Zbl 1154.11002.
- Henri Cohen (1993). A Course In Computational Algebraic Number Theory. Graduate Texts in Mathematics. 138. Springer-Verlag. doi:10.1007/978-3-662-02945-9. ISBN 0-387-55640-0.
- Henri Cohen (2000). Advanced Topics in Computational Number Theory. Graduate Texts in Mathematics. 193. Springer-Verlag. doi:10.1007/978-1-4419-8489-0. ISBN 0-387-98727-4.
- Henri Cohen (2007). Number Theory – Volume I: Tools and Diophantine Equations. Graduate Texts in Mathematics. 239. [Springer-Verlag. doi:10.1007/978-0-387-49923-9. ISBN 978-0-387-49922-2.
- Henri Cohen (2007). Number Theory – Volume II: Analytic and Modern Tools. Graduate Texts in Mathematics. 240. Springer-Verlag. doi:10.1007/978-0-387-49894-2. ISBN 978-0-387-49893-5.
- Richard Crandall· Carl Pomerance (2001). Prime Numbers: A Computational Perspective. Springer-Verlag. doi:10.1007/978-1-4684-9316-0. ISBN 0-387-94777-9.
- Hans Riesel (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics. 126 (second έκδοση). Birkhäuser. ISBN 0-8176-3743-5. Zbl 0821.11001.
- Victor Shoup (2012). A Computational Introduction to Number Theory and Algebra. Cambridge University Press. doi:10.1017/CBO9781139165464. ISBN 9781139165464.
- Samuel S. Wagstaff, Jr. (2013). The Joy of Factoring. American Mathematical Society. ISBN 978-1-4704-1048-3.
Παραπομπές
[Επεξεργασία | επεξεργασία κώδικα]- ↑ «Computational number theory». Engati (στα Αγγλικά). Ανακτήθηκε στις 19 Ιουλίου 2023.
- ↑ dotnet-bot. «RSA.Create Methode (System.Security.Cryptography)». learn.microsoft.com (στα Γερμανικά). Ανακτήθηκε στις 19 Ιουλίου 2023.
- ↑ 3,0 3,1 «Carl Pomerance (2009), Timothy Gowers (ed.), "Computational Number Theory" (PDF), The Princeton Companion to Mathematics, Princeton University Press» (PDF).
- ↑ Eric Bach; Jeffrey Shallit (1996). Algorithmic Number Theory, Volume 1: Efficient Algorithms. MIT Press. ISBN 0-262-02405-5.
- ↑ Henri Cohen (1993). A Course In Computational Algebraic Number Theory. Graduate Texts in Mathematics. Vol. 138. Springer-Verlag. doi:10.1007/978-3-662-02945-9. ISBN 0-387-55640-0.
