/*********************************************************
*   Euclide Esteso
*     
*   Languasco & Zaccagnini, Introduzione alla Crittografia, Hoepli.
*   Capitolo 2.2 pag. 35-36  
*   Capitolo 6.2 pag. 163-165 
*********************************************************/  

/* input: n,m - numeri di cui si ricerca un il massimo
 * comun divisore, m>n. Se m<n i due numeri vengono scambiati.
 * output: d=(m,n) e due interi lambda, mi tali che d=(lambda)m+(mi)n
 */

{EuclideEsteso(m,n) = local (M,N,q,r,a,b,a0,b0,A,B,lambda,mi,app,iterazioni); 
		/* se n=m il risultato e' banale  */
		
		if(((n <= 0) | (m<=0)), error("I due numeri in input devono essere entrambi positivi !!"));
		
		if(n == m, d=n; a=1;b=0;
		          print("I due numeri sono uguali");
		          print("d=",d, " a=",a, " b=",b);
		          return;
		);
		/* se m<n scambio i due numeri  */
		
		if(m < n, app=m; m=n; n=app);
		
		/* Inizializzazione delle successioni a_k e b_k
		A=a_{-1} = 1, B= b_{-1} = 0, 
        a_0 = 0,  b_0 = 1.  
        */
        
		A=1; a0=0;
		B=0; b0=1;
		
		/* Inizializzazione delle altre variabili  */
		iterazioni=0;
		M=m;  /* serve solo a ricordare il valore di m */
		N=n;  /* serve solo a ricordare il valore di n */
		
		while (n!=0, 
		         r= m %n ;     /* resto della divisione intera di m per n */
		         q= m \ n;     /* quoziente della divisione intera di m per n */
		         a=A-q*a0;     /* a_k = a_{k-2} - q_k a_{k-1} */
		         b=B-q*b0;     /* b_k = b_{k-2} - q_k b_{k-1} */
		         m=n;          /* scambio il ruolo di m e n, e di n e r per */
		         n=r;          /* fare al passo successivo la divisione di n per r */
		         A=a0;         /* per il passo successivo serve a_{k-1} va in a_{k-2} */
		         a0=a;         /* per il passo successivo serve a_{k} va in a_{k-1} */
		         B=b0;         /* per il passo successivo serve b_{k-1} va in b_{k-2} */
		         b0=b;         /* per il passo successivo serve b_{k-1} va in b_{k-2} */
		         iterazioni=iterazioni+1      /*conto il numero di iterazioni*/
		);
		
		/* alla fine del while si ha r_(K+1)=0; allora d e' il resto del passo
		 * precedente che e' immaganizzato in m; i moltiplicatori sono anch'essi
		 * quelli del passo precedente e sono rispettivamente immagazzinati in
		 * A e B
		 */
		d=m;
		lambda=A;
		mi=B;
		
		/* Output dei risultati */
		print("Il massimo comun divisore di m=",M, " e n=", N, " e'");
		print("d=",d);
		print("I moltiplicatori sono rispettivamente lambda=",lambda, " e mi=",mi);
		print("Il numero totale di iterazioni e` ", iterazioni);
		return;
}