Merged silc_1_0_branch to trunk.

[silc.git] / lib / silcmath / modinv.c

diff --git a/lib/silcmath/modinv.c b/lib/silcmath/modinv.c
index 7863923e4bf7dc76c88163d91812bd638255a3fd..5c6e0657ad5338284f89dab9f0f4ca2c35e4184e 100644 (file)
--- a/lib/silcmath/modinv.c
+++ b/lib/silcmath/modinv.c
@@ -2,15 +2,14 @@
 
   modinv.h
 
-  Author: Pekka Riikonen <priikone@poseidon.pspt.fi>
+  Author: Pekka Riikonen <priikone@silcnet.org>
 
-  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
@@ -29,21 +28,21 @@ typedef struct {
 #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.)
 */
 
@@ -52,10 +51,10 @@ void silc_mp_modinv(SilcMPInt *inv, SilcMPInt *a, SilcMPInt *n)
   int i;
   SilcMPInt y;
   SilcMPInt x;
-  
+
   ModInv g[3];
   ModInv v[3];
-  
+
   /* init MP vars */
   silc_mp_init(&y);
   silc_mp_init(&x);
@@ -69,7 +68,7 @@ void silc_mp_modinv(SilcMPInt *inv, SilcMPInt *a, SilcMPInt *n)
   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 */
@@ -79,14 +78,14 @@ void silc_mp_modinv(SilcMPInt *inv, SilcMPInt *a, SilcMPInt *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));