è impossibile. Eppure ecco il risultato: 2515. Per ottenerlo, occorre implementare un algoritmo che sfrutta la proprietà sul resto di un quadrato, ma procediamo con ordine.

Illustrerò allora come si giunge al risultato 2515 dell'esempio sopra riportato, ma la procedura è del tutto generalizzabile ed implementabile, anche quando l'esponente della potenza e il modulo hanno un numero di cifre superiore.

Si inizia effettuando la decomposizione binaria dell'esponente della potenza: alla potenza di 2, più vicina da sinistra all'esponente della potenza, si aggiungono, a decrescere, le successive potenze di 2, escludendo quelle che conducono ad un risultato maggiore dell'esponente della potenza, e arrestandosi quando, viceversa, il risultato è esattamente pari a quest'ultimo.

Nel nostro caso è:

Applichiamo ora la proprietà sul resto di un prodotto, scrivendo:

Se applichiamo ora la proprietà sul resto di un quadrato, è possibile determinare i singoli resti. E' infatti:

In conclusione sarà: