| Περίληψη: | Σε αυτό το κεφάλαιο παρουσιάζουμε αλγορίθμους παραγοντοποίησης και εύρεσης διακριτού λογάριθμου. ΄Οσον αφορά την παραγοντοποίηση, ξεκινάμε με τον απλό αλγόριθμο της δοκιμαστικής διαίρεσης (trial division), συνεχίζουμε με τον αλγόριθμο παραγοντοποίησης του Fermat όπου θέτουμε τις βάσεις για τον υποεκθετικό αλγόριθμο Quadratic Sieve. Αναλύουμε εκτενώς τον αλγόριθμο αυτόν, διότι είναι αρκετά σημαντικός μέχρι σήμερα. Είναι ο καλύτερος αλγόριθμος παραγοντοποίησης για ακεραίους από 50 μέχρι 100 δεκαδικά ψηφία. Επίσης, είναι απλούστερος από τον Number field sieve που είναι ο καλύτερος αλγόριθμος παραγοντοποίησης που έχουμε μέχρι σήμερα. ΄Οσον αφορά τον διακριτό λογάριθμο, παρουσιάζουμε τον αλγόριθμο του Shanks και τον Polard-ρ. Ο δεύτερος αποτελεί μια βελτίωση του πρώτου όσον αφορά τη μνήμη. Επίσης, στην παρουσίαση του αλγορίθμου του Pollard στην άσκηση 10.21 δίνουμε και την παραλλαγή του αλγορίθμου για παραγοντοποίηση.
|
|---|
