1f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#include <tommath.h> 2f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#ifdef BN_MP_GCD_C 3f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* LibTomMath, multiple-precision integer library -- Tom St Denis 4f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 5f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * LibTomMath is a library that provides multiple-precision 6f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * integer arithmetic as well as number theoretic functionality. 7f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 8f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The library was designed directly after the MPI library by 9f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Michael Fromberger but has been written from scratch with 10f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * additional optimizations in place. 11f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 12f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * The library is free for all purposes without any express 13f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * guarantee it works. 14f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * 15f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project * Tom St Denis, tomstdenis@gmail.com, http://math.libtomcrypt.com 16f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 17f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 18f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* Greatest Common Divisor using the binary method */ 19f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_gcd (mp_int * a, mp_int * b, mp_int * c) 20f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 21f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int u, v; 22f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int k, u_lsb, v_lsb, res; 23f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 24f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* either zero than gcd is the largest */ 25f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_iszero (a) == MP_YES) { 26f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return mp_abs (b, c); 27f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 28f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_iszero (b) == MP_YES) { 29f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return mp_abs (a, c); 30f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 31f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 32f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* get copies of a and b we can modify */ 33f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init_copy (&u, a)) != MP_OKAY) { 34f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return res; 35f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 36f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 37f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_init_copy (&v, b)) != MP_OKAY) { 38f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_U; 39f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 40f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 41f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* must be positive for the remainder of the algorithm */ 42f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project u.sign = v.sign = MP_ZPOS; 43f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 44f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* B1. Find the common power of two for u and v */ 45f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project u_lsb = mp_cnt_lsb(&u); 46f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project v_lsb = mp_cnt_lsb(&v); 47f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project k = MIN(u_lsb, v_lsb); 48f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 49f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (k > 0) { 50f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* divide the power of two out */ 51f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_div_2d(&u, k, &u, NULL)) != MP_OKAY) { 52f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_V; 53f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 54f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 55f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_div_2d(&v, k, &v, NULL)) != MP_OKAY) { 56f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_V; 57f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 58f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 59f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 60f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* divide any remaining factors of two out */ 61f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (u_lsb != k) { 62f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_div_2d(&u, u_lsb - k, &u, NULL)) != MP_OKAY) { 63f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_V; 64f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 65f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 66f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 67f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (v_lsb != k) { 68f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_div_2d(&v, v_lsb - k, &v, NULL)) != MP_OKAY) { 69f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_V; 70f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 71f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 72f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 73f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project while (mp_iszero(&v) == 0) { 74f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* make sure v is the largest */ 75f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (mp_cmp_mag(&u, &v) == MP_GT) { 76f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* swap u and v to make sure v is >= u */ 77f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_exch(&u, &v); 78f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 79f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 80f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* subtract smallest from largest */ 81f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = s_mp_sub(&v, &u, &v)) != MP_OKAY) { 82f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_V; 83f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 84f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 85f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* Divide out all factors of two */ 86f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_div_2d(&v, mp_cnt_lsb(&v), &v, NULL)) != MP_OKAY) { 87f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_V; 88f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 89f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 90f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 91f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* multiply by 2**k which we divided out at the beginning */ 92f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((res = mp_mul_2d (&u, k, c)) != MP_OKAY) { 93f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project goto LBL_V; 94f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 95f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project c->sign = MP_ZPOS; 96f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project res = MP_OKAY; 97f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_V:mp_clear (&u); 98f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source ProjectLBL_U:mp_clear (&v); 99f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return res; 100f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 101f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#endif 102f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 103f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Source: /cvs/libtom/libtommath/bn_mp_gcd.c,v $ */ 104f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Revision: 1.4 $ */ 105f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Date: 2006/03/31 14:18:44 $ */ 106