1f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#include <tommath.h> 2f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#ifdef BN_MP_EXTEUCLID_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/* Extended euclidean algorithm of (a, b) produces 19f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project a*u1 + b*u2 = u3 20f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project */ 21f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Projectint mp_exteuclid(mp_int *a, mp_int *b, mp_int *U1, mp_int *U2, mp_int *U3) 22f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project{ 23f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_int u1,u2,u3,v1,v2,v3,t1,t2,t3,q,tmp; 24f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project int err; 25f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 26f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_init_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL)) != MP_OKAY) { 27f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return err; 28f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 29f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 30f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* initialize, (u1,u2,u3) = (1,0,a) */ 31f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set(&u1, 1); 32f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_copy(a, &u3)) != MP_OKAY) { goto _ERR; } 33f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 34f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* initialize, (v1,v2,v3) = (0,1,b) */ 35f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_set(&v2, 1); 36f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_copy(b, &v3)) != MP_OKAY) { goto _ERR; } 37f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 38f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* loop while v3 != 0 */ 39f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project while (mp_iszero(&v3) == MP_NO) { 40f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* q = u3/v3 */ 41f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_div(&u3, &v3, &q, NULL)) != MP_OKAY) { goto _ERR; } 42f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 43f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* (t1,t2,t3) = (u1,u2,u3) - (v1,v2,v3)q */ 44f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_mul(&v1, &q, &tmp)) != MP_OKAY) { goto _ERR; } 45f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_sub(&u1, &tmp, &t1)) != MP_OKAY) { goto _ERR; } 46f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_mul(&v2, &q, &tmp)) != MP_OKAY) { goto _ERR; } 47f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_sub(&u2, &tmp, &t2)) != MP_OKAY) { goto _ERR; } 48f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_mul(&v3, &q, &tmp)) != MP_OKAY) { goto _ERR; } 49f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_sub(&u3, &tmp, &t3)) != MP_OKAY) { goto _ERR; } 50f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 51f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* (u1,u2,u3) = (v1,v2,v3) */ 52f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_copy(&v1, &u1)) != MP_OKAY) { goto _ERR; } 53f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_copy(&v2, &u2)) != MP_OKAY) { goto _ERR; } 54f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_copy(&v3, &u3)) != MP_OKAY) { goto _ERR; } 55f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 56f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* (v1,v2,v3) = (t1,t2,t3) */ 57f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_copy(&t1, &v1)) != MP_OKAY) { goto _ERR; } 58f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_copy(&t2, &v2)) != MP_OKAY) { goto _ERR; } 59f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if ((err = mp_copy(&t3, &v3)) != MP_OKAY) { goto _ERR; } 60f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 61f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 62f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* make sure U3 >= 0 */ 63f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (u3.sign == MP_NEG) { 64f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_neg(&u1, &u1); 65f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_neg(&u2, &u2); 66f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project mp_neg(&u3, &u3); 67f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project } 68f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 69f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project /* copy result out */ 70f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (U1 != NULL) { mp_exch(U1, &u1); } 71f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (U2 != NULL) { mp_exch(U2, &u2); } 72f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project if (U3 != NULL) { mp_exch(U3, &u3); } 73f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 74f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project err = MP_OKAY; 75f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project_ERR: mp_clear_multi(&u1, &u2, &u3, &v1, &v2, &v3, &t1, &t2, &t3, &q, &tmp, NULL); 76f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project return err; 77f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project} 78f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project#endif 79f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project 80f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Source: /cvs/libtom/libtommath/bn_mp_exteuclid.c,v $ */ 81f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Revision: 1.3 $ */ 82f7fc46c63fdc8f39234fea409b8dbe116d73ebf8The Android Open Source Project/* $Date: 2006/03/31 14:18:44 $ */ 83