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