00001 /**********************************************************
00002  * @file tools.c
00003  * @author Sebastien Varrette <Sebastien.Varrette@imag.fr>
00004  * @date   Mon Apr 10 2006  
00005  *
00006  * Copyright (c) 2006 Sebastien Varrette  (http://www-id.imag.fr/~svarrett/)
00007  *
00008  * @brief  
00009  *
00010  * This program is free software; you can redistribute it and/or
00011  * modify it under the terms of the GNU General Public License
00012  * as published by the Free Software Foundation; either version 2
00013  * of the License, or (at your option) any later version.
00014  *
00015  * This program is distributed in the hope that it will be useful,
00016  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00017  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018  * GNU General Public License for more details.
00019  *
00020  * You should have received a copy of the GNU General Public License
00021  * along with this program; if not, write to the Free Software
00022  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
00023  * 
00024  * Sebastien Varrette                               \n
00025  * <Sebastien.Varrette@imag.fr>                     \n
00026  * University of Luxembourg / ID-IMAG Laboratory    \n
00027  * 162-A avenue de la faiencerie                    \n
00028  * L-1511 Luxembourg, LUXEMBOURG                    \n
00029  */
00030  /********************************************************************************/
00031 
00032 #include <stdio.h>
00033 
00034 /**
00035  * Calcul du pgcd de 2 nombres par l'algorithme d'Euclide
00036  */
00037 int pgcd(int a, int b) {
00038     int e = (a < 0)?-a:a; // Pour assurer des valeurs positives
00039     int f = (b < 0)?-b:b;
00040     int tmp;
00041     if (e == 0) return f;
00042     while (f > 0) {
00043         tmp   = f;
00044         f = e % f; // Calcul de r = a % b
00045         e = tmp;
00046     }
00047     return e;
00048 }
00049 
00050 /**
00051  * Version récursive du calcul du pgcd
00052  */
00053 int pgcd_rec(int a, int b) {
00054     int e = (a < 0)?-a:a;
00055     int f = (b < 0)?-b:b;
00056     if (f == 0) return e;
00057     return pgcd_rec(f, e%f);
00058 }
00059 
00060 /**
00061  * Calcul des coefficients de Bezout tels que d = pgcd(a,b) = a.u + b.v
00062  * @return   d = pgcd(a,b)
00063  */
00064 int bezout(int a, int b, int * u, int * v) {
00065     int e = (a < 0)?-a:a;
00066     int f = (b < 0)?-b:b;
00067     *u = 1;
00068     *v = 0;
00069     int u_aux = 0, v_aux = 1;
00070     int q, r, tmp;
00071     while (f > 0) {
00072         q = e/f;
00073         r = e%f;
00074         e = f;
00075         f = r; 
00076         tmp = u_aux; u_aux = *u - q*u_aux; *u = tmp;
00077         tmp = v_aux; v_aux = *v - q*v_aux; *v = tmp;
00078     }
00079     if (a < 0) *u = -(*u);
00080     if (b < 0) *v = -(*v);
00081     return e;
00082 }
00083 /**
00084  * Calcul de l'inverse de a modulo n.
00085  * @return   0 en cas de succès, 1 en cas d'echec (si pgcd(a,n)=1)
00086  */
00087 int inv_mod(int a, int n, int * res) {
00088     int d, u, v;
00089     d = bezout(a, n, &u, &v);
00090     if (d == 1) {
00091         *res = (n + u) % n;
00092         return 0;
00093     }
00094     return 1;
00095 }