De ce contează?
Trebuie să calculezi „ultima cifră" a unui număr uriaș, de exemplu restul lui 3 ridicat la puterea 1000000000 împărțit la 7. Dacă încerci să scrii numărul întreg, ai nevoie de sute de milioane de cifre — nu încape în niciun fel de memorie. Dar pe tine nu te interesează tot numărul, ci doar restul. Trucul e că poți păstra doar restul pe tot parcursul calculului, iar puterea o construiești ridicând la pătrat, nu înmulțind de un miliard de ori.
Intuiția
Două idei se combină aici. Prima: ca să afli a la puterea n modulo m, nu ai
nevoie de numărul mare — îi păstrezi tot timpul doar restul împărțirii la m,
fiindcă restul unui produs depinde doar de resturile factorilor. A doua: nu înmulțești
de n ori, ci te folosești de faptul că ridicarea la pătrat dublează exponentul.
Dintr-o singură valoare a poți urca rapid prin a², a⁴, a⁸, a¹⁶... iar pe n
îl scrii ca sumă de astfel de puteri ale lui 2. Așa ajungi din n pași în doar
log₂(n) pași.