1 #include "tommath_private.h"
2 #ifdef BN_MP_LCM_C
3 /* LibTomMath, multiple-precision integer library -- Tom St Denis */
4 /* SPDX-License-Identifier: Unlicense */
5
6 /* computes least common multiple as |a*b|/(a, b) */
mp_lcm(const mp_int * a,const mp_int * b,mp_int * c)7 mp_err mp_lcm(const mp_int *a, const mp_int *b, mp_int *c)
8 {
9 mp_err err;
10 mp_int t1, t2;
11
12
13 if ((err = mp_init_multi(&t1, &t2, NULL)) != MP_OKAY) {
14 return err;
15 }
16
17 /* t1 = get the GCD of the two inputs */
18 if ((err = mp_gcd(a, b, &t1)) != MP_OKAY) {
19 goto LBL_T;
20 }
21
22 /* divide the smallest by the GCD */
23 if (mp_cmp_mag(a, b) == MP_LT) {
24 /* store quotient in t2 such that t2 * b is the LCM */
25 if ((err = mp_div(a, &t1, &t2, NULL)) != MP_OKAY) {
26 goto LBL_T;
27 }
28 err = mp_mul(b, &t2, c);
29 } else {
30 /* store quotient in t2 such that t2 * a is the LCM */
31 if ((err = mp_div(b, &t1, &t2, NULL)) != MP_OKAY) {
32 goto LBL_T;
33 }
34 err = mp_mul(a, &t2, c);
35 }
36
37 /* fix the sign to positive */
38 c->sign = MP_ZPOS;
39
40 LBL_T:
41 mp_clear_multi(&t1, &t2, NULL);
42 return err;
43 }
44 #endif
45