1. Γραμμική Εξίσωση Ισοτιμίας ax ≡ b (mod m):
- Ύπαρξη Λύσεων:Η εξίσωση έχει λύση αν και μόνο αν ο gcd(a, m) διαιρεί το b (δηλ. το b διαιρείται από τον gcd(a, m))
- Αριθμός Λύσεων:Αν υπάρχουν λύσεις, υπάρχουν d = gcd(a, m) διακριτές λύσεις modulo m
- Μέθοδος Λύσης:
- Υπολογισμός d = gcd(a, m)
- Έλεγχος αν ο d διαιρεί το b· αν όχι, δεν υπάρχει λύση
- Διαίρεση και των δύο πλευρών με d: (a/d)x ≡ (b/d) (mod m/d)
- Χρήση του Εκτεταμένου Ευκλείδειου Αλγορίθμου για εύρεση του αντιστρόφου του a/d modulo m/d
- Υπολογισμός x₀ = a' × (b/d) mod (m/d)
- Γενική λύση: x = x₀ + k(m/d), όπου k = 0, 1, ..., d-1
2. Εκθετική εξίσωση ισοτιμίας a^x ≡ b (mod m) (Πρόβλημα Διακριτού Λογαρίθμου):
- Περιγραφή προβλήματος:Δοθέντων a, b, m, βρείτε τον μικρότερο μη αρνητικό ακέραιο x τέτοιο ώστε a^x ≡ b (mod m)
- Ύπαρξη Λύσεων:
- Αν gcd(a, m) = 1 και το b είναι στοιχείο της κυκλικής ομάδας που παράγεται από το a modulo m, τότε υπάρχει λύση
- Μέθοδος επαλήθευσης: απαρίθμηση δυνάμεων του a μέχρι να βρεθεί το b ή να ολοκληρωθεί ένας πλήρης κύκλος
- Μέθοδος Λύσης:
- Αναζήτηση ωμής βίας σε μικρό εύρος:Απαρίθμηση x = 0, 1, 2, ... μέχρι να βρεθεί λύση ή να φτάσει το όριο αναζήτησης
- Αλγόριθμος Baby-step Giant-step:Χρονική πολυπλοκότητα O(√m), κατάλληλο για προβλήματα μεσαίου μεγέθους
- Αλγόριθμος του Pollard rho:Εφαρμόσιμο για μεγάλους πρώτους συντελεστές
- Περιοδικότητα:Αν x₀ είναι λύση, τότε x = x₀ + kφ(m) είναι επίσης λύση (όπου φ(m) είναι η συνάρτηση Euler)
3. Σενάρια εφαρμογής:
- Κρυπτογραφία:RSA, Diffie-Hellman ανταλλαγή κλειδιών, κρυπτογράφηση ElGamal
- Έρευνα θεωρίας αριθμών:Πρωτογενείς Ρίζες, Τετραγωνικά Υπόλοιπα, Κινεζικό Θεώρημα Υπολοίπων
- Δημιουργία Τυχαίων Αριθμών:Γραμμική Γεννήτρια Ισοτιμίας (LCG)
- Συναρτήσεις Κατακερματισμού:Εφαρμογή Αριθμητικής Υπολοίπων σε Πίνακες Κατακερματισμού
- Ανταγωνιστικός Προγραμματισμός:Ταχεία Εκθετοποίηση, Αντίστροφο Υπολοίπου, Προβλήματα Θεωρίας Αριθμών
Πολυπλοκότητα Αλγορίθμου:
- Γραμμικές Εξισώσεις Ισοτιμίας:O(log m) (Πολυπλοκότητα Εκτεταμένου Ευκλείδειου Αλγορίθμου)
- Εκθετικές Εξισώσεις Ισοτιμίας (Ωμή Βία):O(n), όπου n είναι το όριο αναζήτησης
- Εκθετικές Εξισώσεις Ισοτιμίας (BSGS):O(√m), απαιτεί επιπλέον χώρο
Σημαντικά Θεωρήματα:
- Θεώρημα Bézout:Η εξίσωση ax + my = gcd(a, m) έχει πάντα ακέραιες λύσεις
- Μικρό Θεώρημα Fermat:Αν p είναι πρώτος και gcd(a, p) = 1, τότε a^(p-1) ≡ 1 (mod p)
- Θεώρημα Euler:Αν gcd(a, m) = 1, τότε a^φ(m) ≡ 1 (mod m)
- Κινεζικό Θεώρημα Υπολοίπων:Μπορεί να λύσει συστήματα ισοτιμιών