Υπολογιστής Modular Ύψωσης σε Δύναμη

Τύπος

How this is calculated

Εισαγάγετε τρεις ακέραιους: τη βάση b, έναν μη αρνητικό εκθέτη e, και ένα θετικό μέτρο m. Ο υπολογιστής επιστρέφει το υπόλοιπο του b υψωμένου στο e όταν διαιρείται με m. Ο αφελής υπολογισμός του b^e πρώτα θα υπερχείλιζε για μεγάλους εκθέτες, οπότε αυτό το εργαλείο χρησιμοποιεί ύψωση σε δύναμη με τετραγωνισμό (που ονομάζεται επίσης δυαδική ύψωση σε δύναμη).

Ο αλγόριθμος ξεκινά με result = 1 και μειώνει τη βάση modulo m. Στη συνέχεια διατρέχει τα bit του εκθέτη από το λιγότερο προς το πιο σημαντικό: όποτε το τρέχον bit είναι 1 πολλαπλασιάζει το τρέχον αποτέλεσμα με την τρέχουσα βάση (mod m), και σε κάθε βήμα τετραγωνίζει τη βάση (mod m) και ολισθαίνει τον εκθέτη δεξιά κατά ένα bit. Επειδή κάθε ενδιάμεσο γινόμενο μειώνεται modulo m, οι αριθμοί παραμένουν μικροί και η εργασία είναι ανάλογη με log2(e) πολλαπλασιασμούς αντί για e από αυτούς. Όλη η αριθμητική εκτελείται με JavaScript BigInt ώστε τα αποτελέσματα να είναι ακριβή ανεξάρτητα από το μέγεθος.

Παραδοχές και ακραίες περιπτώσεις: ο εκθέτης πρέπει να είναι ακέραιος e >= 0 και το μέτρο πρέπει να είναι θετικός ακέραιος m > 0 (mod 0 είναι απροσδιόριστο). Η βάση μπορεί να είναι αρνητική· κανονικοποιείται πρώτα στο εύρος 0..m-1 χρησιμοποιώντας ((b mod m) + m) mod m, οπότε το επιστρεφόμενο υπόλοιπο είναι πάντα μη αρνητικό. Όταν e = 0 το αποτέλεσμα είναι 1 mod m. Όταν m = 1 το αποτέλεσμα είναι πάντα 0.