Μετάβαση στο περιεχόμενο

Αλγοριθμική θεωρία αριθμών

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια

Η αλγοριθμική θεωρία αριθμών είναι ένας κλάδος της θεωρίας αριθμών, η οποία αποτελεί από μόνη της κλάδο των μαθηματικών. Ασχολείται με το ζήτημα των αποτελεσματικών αλγοριθμικών λύσεων σε αριθμοθεωρητικά ζητήματα.[1]

Οι κύριοι τομείς της αλγοριθμικής θεωρίας αριθμών είναι οι εξής

  • Δοκιμές πρώτων αριθμών
  • διαδικασίες παραγοντοποίησης ακέραιων αριθμών
  • υπολογισμός του διακριτού λογαρίθμου.

Για να το κάνουμε αυτό, χρειαζόμαστε άλλες διαδικασίες που επίσης μελετώνται:

  • γρήγορος πολλαπλασιασμός
  • γρήγορη δύναμη
  • υπολογισμός του μεγαλύτερου κοινού διαιρέτη με τον αλγόριθμο του Ευκλείδη
  • υπολογισμός του συμβόλου Jacobi χρησιμοποιώντας το νόμο της τετραγωνικής αμοιβαιότητας
  • Παραγοντοποίηση πολυωνύμων, ιδίως επίσης γρήγορη εξαγωγή ριζών.

Νέα ερευνητικά αποτελέσματα στην αλγοριθμική θεωρία αριθμών παρουσιάζονται στο συνέδριο ANTS (Συμπόσιο για την αλγοριθμική θεωρία αριθμών), το οποίο διεξάγεται κάθε δύο χρόνια από το 1994.

Η κύρια εφαρμογή της αλγοριθμικής θεωρίας αριθμών είναι η κρυπτογραφία. Παραδείγματος χάριν, η μέθοδος RSA[2] εκμεταλλεύεται το γεγονός ότι η ιδιότητα πρώτου αριθμού μπορεί να επαληθευτεί γρήγορα, ωστόσο δεν είναι γνωστή μέχρι σήμερα μια τόσο γρήγορη μέθοδος για την παραγοντοποίηση ενός σύνθετου αριθμού (δηλαδή ενός αριθμού που δεν είναι πρώτος). Σε αυτό το γεγονός βασίζεται η ασφάλεια της μετάδοσης δεδομένων μέσω του Διαδικτύου. Έχοντας αυτό κατά νου, η RSA Security προσέφερε μεγάλα χρηματικά ποσά σε όποιον μπορούσε να παραγοντοποιήσει ορισμένους αριθμούς[3].

Πέρα της κρυπτογραφίας και της μετα-κβαντικής κρυπτογραφίας, χρησιμοποιείται επίσης για τη μελέτη εικασιών και ανοικτών προβλημάτων στη θεωρία αριθμών, συμπεριλαμβανομένης της υπόθεσης Ρίμαν, την εικασία Μπέρτς και Σουίνερτον-Ντάιερ, την εικασία ABC, την εικασία της αρθρωτότητας, την εικασία Σάτο-Τάτε και ρητές πτυχές του προγράμματος Λάνγκλαντς[3][4][5].

  1. «Computational number theory». Engati (στα Αγγλικά). Ανακτήθηκε στις 19 Ιουλίου 2023. 
  2. dotnet-bot. «RSA.Create Methode (System.Security.Cryptography)». learn.microsoft.com (στα Γερμανικά). Ανακτήθηκε στις 19 Ιουλίου 2023. 
  3. 3,0 3,1 «Carl Pomerance (2009), Timothy Gowers (ed.), "Computational Number Theory" (PDF), The Princeton Companion to Mathematics, Princeton University Press» (PDF). 
  4. Eric Bach; Jeffrey Shallit (1996). Algorithmic Number Theory, Volume 1: Efficient Algorithms. MIT Press. ISBN 0-262-02405-5.
  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.