/*********************************************************
*   Quadrati Ripetuti modulo n
*
*   Languasco & Zaccagnini, Introduzione alla Crittografia, Hoepli.
*   Capitolo 6.9.2 pag. 195-196 
*********************************************************/  

/* input: a,m,n - a intero, m  naturale >=1, n  naturale >=2  
 * output: a^m mod n .
 */

{RepeatedSquares(a,m,n) = local (P, A, L, i);

/**   Test sull'input  *******/
     if (((m<=0) || (n<=1)), print("input non valido"));
     
/***   Inizializzazioni  *****/

     P=1;      /* conterra' il risultato parziale  */
     A=a;      /* conterra' i vari quadrati  */  
     i=0;
		
/*** calcolo del numero di bit dell'espansione binaria di m ****/

     L=floor((log(m)/log(2)))+1;   
		
/*** Ciclo di calcolo		****/
		
     for (i=0, L-1,
          r= bittest(m, i);   /* r= coefficiente di  2^i 
                              nell'espansione binaria di m */
          if(r == 1,    /* se il resto e' 1 moltiplico per 
                              il risultato parziale del passo 
                              precedente  */ 
               P=lift(Mod(P*A,n)); 
          );
          A=lift(Mod(A^2,n));  /* calcolo  il quadrato successivo */ 
          );	 
        
/*** Stampa del risultato	****/
         
     print("a=", a," alla m=", m," modulo n=", n, " e` uguale a ",P); 
}