1 #include "tommath_private.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 * SPDX-License-Identifier: Unlicense
13 */
14
15 /* computes least common multiple as |a*b|/(a, b) */
mp_lcm(const mp_int * a,const mp_int * b,mp_int * c)16 int mp_lcm(const mp_int *a, const mp_int *b, mp_int *c)
17 {
18 int res;
19 mp_int t1, t2;
20
21
22 if ((res = mp_init_multi(&t1, &t2, NULL)) != MP_OKAY) {
23 return res;
24 }
25
26 /* t1 = get the GCD of the two inputs */
27 if ((res = mp_gcd(a, b, &t1)) != MP_OKAY) {
28 goto LBL_T;
29 }
30
31 /* divide the smallest by the GCD */
32 if (mp_cmp_mag(a, b) == MP_LT) {
33 /* store quotient in t2 such that t2 * b is the LCM */
34 if ((res = mp_div(a, &t1, &t2, NULL)) != MP_OKAY) {
35 goto LBL_T;
36 }
37 res = mp_mul(b, &t2, c);
38 } else {
39 /* store quotient in t2 such that t2 * a is the LCM */
40 if ((res = mp_div(b, &t1, &t2, NULL)) != MP_OKAY) {
41 goto LBL_T;
42 }
43 res = mp_mul(a, &t2, c);
44 }
45
46 /* fix the sign to positive */
47 c->sign = MP_ZPOS;
48
49 LBL_T:
50 mp_clear_multi(&t1, &t2, NULL);
51 return res;
52 }
53 #endif
54
55 /* ref: $Format:%D$ */
56 /* git commit: $Format:%H$ */
57 /* commit time: $Format:%ai$ */
58