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