Αλγόριθμος του Ευκλείδη: Διαφορά μεταξύ των αναθεωρήσεων

Ένα [[πεπερασμένο πεδίο ]] είναι ένα σύνολο αριθμών με τέσσερις γενικευμένες πράξεις. Οι πράξεις ονομάζονται πρόσθεση, αφαίρεση, πολλαπλασιασμός και διαίρεση και έχουν τις συνήθεις ιδιότητές τους, όπως [[ commutativity]], ,[[ συσχέτιση]] και [[distributivity]] . Ένα παράδειγμα ενός πεπερασμένου πεδίου είναι το σύνολο από 13 αριθμούς {0,&nbsp;1,&nbsp;2,&nbsp;…,&nbsp;12} με [[modular αριθμητική]] . Στον τομέα αυτό, τα αποτελέσματα από κάθε μαθηματική πράξη (πρόσθεση / αφαίρεση / πολλαπλασιασμός / διαίρεση) μειώνονται στο [[modulo]] 13. Έτσι, πολλαπλάσια του 13, προστίθενται ή αφαιρούνται έως ότου το αποτέλεσμα γίνει μέσα στο εύρος 0-12. Για παράδειγμα, αποτέλεσμα του 5&nbsp;×&nbsp;7&nbsp;=&nbsp;35&nbsp;mod&nbsp;13&nbsp;=&nbsp;9 . Τέτοια πεπερασμένα πεδία μπορούν να εφαρμοστούν για κάθε πρώτο αριθμό p.Χρησιμοποιώντας πιο εξελιγμένε ερμηνείες, μπορούν επίσης να εφαρμοστούν για δύναμη m ενός πρώτου αριθμού ''p'' . Τα πεπερασμένα πεδία συχνά αποκαλούνται τομείς [[Galois]] και σε συντομογραφία γράφονται ως GF(''p'') ή GF(''p''^&nbsp;''m''). Σε ένα τέτοιο πεδίο με m αριθμούς, κάθε μη μηδενικό στοιχείο a έχει ένα μοναδικό [[αντίστροφο πολλαπλασιαστικό modular]],''a''⁻¹ τέτοιο ώστε ''aa''⁻¹&nbsp;=&nbsp;''a''⁻¹''a''&nbsp;≡&nbsp;1&nbsp;mod&nbsp;''m'' . Αυτό το αντίστροφο μπορεί να βρεθεί λύνοντας αντίστοιχα την εξίσωση ''ax''&nbsp;≡&nbsp;1&nbsp;mod&nbsp;''m'' , <ref> Schroeder 2005 , σελ. 107-109 </ref> , ή την ισοδύναμη Διοφαντική εξίσωση <ref>Stillwell 1997 , σελ. 186-187 </ref>

Αυτή η εξίσωση μπορεί να λυθεί από τον Ευκλείδειο αλγόριθμο, όπως περιγράφηκε [[παραπάνω]] .Βρίσκοντας πολλαπλασιαστικά αντίστροφα είναι ένα ουσιαστικό βήμα στον [[RSA αλγόριθμο]] , ο οποίος χρησιμοποιείται ευρέως στο [[ηλεκτρονικό εμπόριο]] .Συγκεκριμένα, η εξίσωση που καθορίζει τον ακέραιο χρησιμοποιείται για να αποκρυπτογραφήσει το μήνυμα. <ref> Schroeder 2005 , p. 134 </ref> Σημειώστε ότι αν και ο αλγόριθμος RSA χρησιμοποιεί [[δαχτυλίδια]] αντί για πεδία, ο Ευκλείδειος αλγόριθμος μπορεί ακόμη να χρησιμοποιηθεί για να βρει ένα πολλαπλασιαστικό αντίστροφο, αν υπάρχει. Ο Ευκλείδειος αλγόριθμος έχει και άλλες εφαρμογές σε [[κώδικες διόρθωσης σφαλμάτων]] .Για παράδειγμα, μπορεί να χρησιμοποιηθεί ως εναλλακτική λύση για τον [[αλγόριθμο Berlekamp-Massey]] για την αποκωδικοποίηση κωδίκων [[BCH]] και [[ Reed-Solomon]] ,οι οποίοι βασίζονται στους Galois τομείς. <ref> "κωδικοποίηση διόρθωσης σφάλματος: μαθηματικές μέθοδοι και αλγόριθμοι", σελ. 266, Todd Κ. Moon, John Wiley and Sons, 2005, ISBN 0-471-64800-0 </ref>