X-Git-Url: http://git.silcnet.org/gitweb/?p=silc.git;a=blobdiff_plain;f=lib%2Fsilcmath%2Fmodinv.c;h=dec30326546f4422779e855bf0d6d163bbecce86;hp=c41dab0022835db0122f9844ac5445f9783eaf30;hb=40f8443d8d3a6577336ee66d18e04d9ac4d956bb;hpb=48d89bc2868ec49c2ab9aa74efe9ac703eee8f29 diff --git a/lib/silcmath/modinv.c b/lib/silcmath/modinv.c index c41dab00..dec30326 100644 --- a/lib/silcmath/modinv.c +++ b/lib/silcmath/modinv.c @@ -2,15 +2,14 @@ modinv.h - Author: Pekka Riikonen + Author: Pekka Riikonen - Copyright (C) 1997 - 2000 Pekka Riikonen + Copyright (C) 1997 - 2005 Pekka Riikonen This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by - the Free Software Foundation; either version 2 of the License, or - (at your option) any later version. - + the Free Software Foundation; version 2 of the License. + This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the @@ -19,53 +18,57 @@ */ /* $Id$ */ -#include "silcincludes.h" +#include "silc.h" /* Table for finding multiplicative inverse */ typedef struct { - SilcInt x; + SilcMPInt x; } ModInv; #define plus1 (i == 2 ? 0 : i + 1) #define minus1 (i == 0 ? 2 : i - 1) -/* Find multiplicative inverse using Euclid's extended algorithm. - Computes inverse such that a * inv mod n = 1, where 0 < a < n. +/* Find multiplicative inverse using Euclid's extended algorithm. + Computes inverse such that a * inv mod n = 1, where 0 < a < n. Algorithm goes like this: - + g(0) = n v(0) = 0 g(1) = a v(1) = 1 - + y = g(i-1) / g(i) g(i+1) = g(i-1) - y * g(i) = g(i)-1 mod g(i) v(i+1) = v(i-1) - y * v(i) - - do until g(i) = 0, then inverse = v(i-1). If inverse is negative then n, - is added to inverse making it positive again. (Sometimes the algorithm - has a variable u defined too and it behaves just like v, except that - initalize values are swapped (i.e. u(0) = 1, u(1) = 0). However, u is + + do until g(i) = 0, then inverse = v(i-1). If inverse is negative then n, + is added to inverse making it positive again. (Sometimes the algorithm + has a variable u defined too and it behaves just like v, except that + initalize values are swapped (i.e. u(0) = 1, u(1) = 0). However, u is not needed by the algorithm so it does not have to be included.) */ -void silc_mp_modinv(SilcInt *inv, SilcInt *a, SilcInt *n) +void silc_mp_modinv(SilcMPInt *inv, SilcMPInt *a, SilcMPInt *n) { int i; - SilcInt y; - SilcInt x; - + SilcMPInt y; + SilcMPInt x; + ModInv g[3]; ModInv v[3]; - + /* init MP vars */ silc_mp_init(&y); silc_mp_init(&x); - silc_mp_init_set_ui(&v[0].x, 0L); /* v(0) = 0 */ - silc_mp_init_set_ui(&v[1].x, 1L); /* v(1) = 1 */ + silc_mp_init(&v[0].x); + silc_mp_init(&v[1].x); + silc_mp_set_ui(&v[0].x, 0L); /* v(0) = 0 */ + silc_mp_set_ui(&v[1].x, 1L); /* v(1) = 1 */ silc_mp_init(&v[2].x); - silc_mp_init_set(&g[0].x, n); /* g(0) = n */ - silc_mp_init_set(&g[1].x, a); /* g(1) = a */ + silc_mp_init(&g[0].x); + silc_mp_init(&g[1].x); + silc_mp_set(&g[0].x, n); /* g(0) = n */ + silc_mp_set(&g[1].x, a); /* g(1) = a */ silc_mp_init(&g[2].x); - + i = 1; while(silc_mp_cmp_ui(&g[i].x, 0) != 0) { silc_mp_div(&y, &g[minus1].x, &g[i].x); /* y = n / a */ @@ -75,23 +78,23 @@ void silc_mp_modinv(SilcInt *inv, SilcInt *a, SilcInt *n) silc_mp_sub(&v[plus1].x, &v[plus1].x, &x); i = plus1; } - + /* set the inverse */ silc_mp_set(inv, &v[minus1].x); - + /* if inverse is negative, add n to inverse */ if (silc_mp_cmp_ui(inv, 0) < 0) silc_mp_add(inv, inv, n); - + /* clear the vars */ memset(&g, 0, sizeof(g)); memset(&v, 0, sizeof(v)); - silc_mp_clear(&y); - silc_mp_clear(&x); - silc_mp_clear(&g[0].x); - silc_mp_clear(&g[1].x); - silc_mp_clear(&g[2].x); - silc_mp_clear(&v[0].x); - silc_mp_clear(&v[1].x); - silc_mp_clear(&v[2].x); + silc_mp_uninit(&y); + silc_mp_uninit(&x); + silc_mp_uninit(&g[0].x); + silc_mp_uninit(&g[1].x); + silc_mp_uninit(&g[2].x); + silc_mp_uninit(&v[0].x); + silc_mp_uninit(&v[1].x); + silc_mp_uninit(&v[2].x); }