1#include <tommath.h>
2#ifdef BN_MP_LCM_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://libtom.org
16 */
17
18/* computes least common multiple as |a*b|/(a, b) */
19int mp_lcm (mp_int * a, mp_int * b, mp_int * c)
20{
21  int     res;
22  mp_int  t1, t2;
23
24
25  if ((res = mp_init_multi (&t1, &t2, NULL)) != MP_OKAY) {
26    return res;
27  }
28
29  /* t1 = get the GCD of the two inputs */
30  if ((res = mp_gcd (a, b, &t1)) != MP_OKAY) {
31    goto LBL_T;
32  }
33
34  /* divide the smallest by the GCD */
35  if (mp_cmp_mag(a, b) == MP_LT) {
36     /* store quotient in t2 such that t2 * b is the LCM */
37     if ((res = mp_div(a, &t1, &t2, NULL)) != MP_OKAY) {
38        goto LBL_T;
39     }
40     res = mp_mul(b, &t2, c);
41  } else {
42     /* store quotient in t2 such that t2 * a is the LCM */
43     if ((res = mp_div(b, &t1, &t2, NULL)) != MP_OKAY) {
44        goto LBL_T;
45     }
46     res = mp_mul(a, &t2, c);
47  }
48
49  /* fix the sign to positive */
50  c->sign = MP_ZPOS;
51
52LBL_T:
53  mp_clear_multi (&t1, &t2, NULL);
54  return res;
55}
56#endif
57
58/* $Source$ */
59/* $Revision$ */
60/* $Date$ */
61