potenza modulare

[volare]

Ho trovato che per risolvere
(1) r=a^n mod k
senza che il PC vada in overflow con valori di n e k significativi ottengo il risultato con il procedimento ricorsivo che segue:
(2) r=1; for i=1 to n r=r*a mod k
Non riesco a trovare sul web una dimostrazione per (1) = (2). Grazie per l'aiuto.

[bobus]

Puoi verificarlo tu con una specie di induzione su n. Verifichi che l'uguaglianza sia vera all'inizio del ciclo, la base.
Poi assumendo che valga all'inizio di un ciclo, verifichi che alla fine del ciclo sia ancora vera.