1/* $NetBSD: bn_mp_lcm.c,v 1.2 2017/01/28 21:31:47 christos 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) */ 21int 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 54LBL_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