Υπολογιστής Συντελεστών Bezout

Σχετικά με αυτόν τον υπολογιστή

Η ταυτότητα του Bezout δηλώνει ότι για οποιουσδήποτε ακέραιους a και b υπάρχουν ακέραιοι x και y — οι συντελεστές Bezout — που ικανοποιούν τη σχέση ax + by = gcd(a, b). Αυτός ο υπολογιστής βρίσκει τα x, y και τον ΜΚΔ με τον εκτεταμένο αλγόριθμο του Ευκλείδη, που εκτελεί τον συνηθισμένο αλγόριθμο ΜΚΔ προς τα εμπρός ενώ παρακολουθεί τους συντελεστές προς τα πίσω σε κάθε βήμα υπολοίπου.

Πέρα από τη θεωρία αριθμών, οι συντελεστές Bezout είναι ο τυπικός τρόπος υπολογισμού ενός πολλαπλασιαστικού αντίστροφου modulo — απαραίτητου στον RSA και στη δημιουργία κλειδιών άλλων κρυπτογραφικών συστημάτων — και βρίσκονται πίσω από την επίλυση γραμμικών διοφαντικών εξισώσεων της μορφής ax + by = c.