libs/libtommath/bn_mp_exteuclid.c

   1 #include <tommath.h>
   2 #ifdef BN_MP_EXTEUCLID_C
   3 /* LibTomMath, multiple-precision integer library -- Tom St Denis
   4  *
   5  * LibTomMath is a library that provides multiple-precision
   6  * integer arithmetic as well as number theoretic functionality.
   7  *
   8  * The library was designed directly after the MPI library by
   9  * Michael Fromberger but has been written from scratch with
  10  * additional optimizations in place.
  11  *
  12  * The library is free for all purposes without any express
  13  * guarantee it works.
  14  *
  15  * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com
  16  */
  17
  18 /* Extended euclidean algorithm of (a, b) produces
  19    a*u1 + b*u2 = u3
  20  */
  21 int mp_exteuclid(mp_int *a, mp_int *b, mp_int *U1, mp_int *U2, mp_int *U3)
  22 {
  23    mp_int u1,u2,u3,v1,v2,v3,t1,t2,t3,q,tmp;
  24    int err;
  25
  26    if ((err = mp_init_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL)) != MP_OKAY) {
  27       return err;
  28    }
  29
  30    /* initialize, (u1,u2,u3) = (1,0,a) */
  31    mp_set(&u1, 1);
  32    if ((err = mp_copy(a, &u3)) != MP_OKAY)                                        { goto _ERR; }
  33
  34    /* initialize, (v1,v2,v3) = (0,1,b) */
  35    mp_set(&v2, 1);
  36    if ((err = mp_copy(b, &v3)) != MP_OKAY)                                        { goto _ERR; }
  37
  38    /* loop while v3 != 0 */
  39    while (mp_iszero(&v3) == MP_NO) {
  40        /* q = u3/v3 */
  41        if ((err = mp_div(&u3, &v3, &q, NULL)) != MP_OKAY)                         { goto _ERR; }
  42
  43        /* (t1,t2,t3) = (u1,u2,u3) - (v1,v2,v3)q */
  44        if ((err = mp_mul(&v1, &q, &tmp)) != MP_OKAY)                              { goto _ERR; }
  45        if ((err = mp_sub(&u1, &tmp, &t1)) != MP_OKAY)                             { goto _ERR; }
  46        if ((err = mp_mul(&v2, &q, &tmp)) != MP_OKAY)                              { goto _ERR; }
  47        if ((err = mp_sub(&u2, &tmp, &t2)) != MP_OKAY)                             { goto _ERR; }
  48        if ((err = mp_mul(&v3, &q, &tmp)) != MP_OKAY)                              { goto _ERR; }
  49        if ((err = mp_sub(&u3, &tmp, &t3)) != MP_OKAY)                             { goto _ERR; }
  50
  51        /* (u1,u2,u3) = (v1,v2,v3) */
  52        if ((err = mp_copy(&v1, &u1)) != MP_OKAY)                                  { goto _ERR; }
  53        if ((err = mp_copy(&v2, &u2)) != MP_OKAY)                                  { goto _ERR; }
  54        if ((err = mp_copy(&v3, &u3)) != MP_OKAY)                                  { goto _ERR; }
  55
  56        /* (v1,v2,v3) = (t1,t2,t3) */
  57        if ((err = mp_copy(&t1, &v1)) != MP_OKAY)                                  { goto _ERR; }
  58        if ((err = mp_copy(&t2, &v2)) != MP_OKAY)                                  { goto _ERR; }
  59        if ((err = mp_copy(&t3, &v3)) != MP_OKAY)                                  { goto _ERR; }
  60    }
  61
  62    /* make sure U3 >= 0 */
  63    if (u3.sign == MP_NEG) {
  64       mp_neg(&u1, &u1);
  65       mp_neg(&u2, &u2);
  66       mp_neg(&u3, &u3);
  67    }
  68
  69    /* copy result out */
  70    if (U1 != NULL) { mp_exch(U1, &u1); }
  71    if (U2 != NULL) { mp_exch(U2, &u2); }
  72    if (U3 != NULL) { mp_exch(U3, &u3); }
  73
  74    err = MP_OKAY;
  75 _ERR: mp_clear_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL);
  76    return err;
  77 }
  78 #endif
  79
  80 /* $Source: /cvs/libtom/libtommath/bn_mp_exteuclid.c,v $ */
  81 /* $Revision: 1.3 $ */
  82 /* $Date: 2006/03/31 14:18:44 $ */