fp_gcd.c

00001 /* TomsFastMath, a fast ISO C bignum library.
00002  * 
00003  * This project is meant to fill in where LibTomMath
00004  * falls short.  That is speed ;-)
00005  *
00006  * This project is public domain and free for all purposes.
00007  * 
00008  * Tom St Denis, tomstdenis@gmail.com
00009  */
00010 #include <tfm.h>
00011 
00012 /* c = (a, b) */
00013 void fp_gcd(fp_int *a, fp_int *b, fp_int *c)
00014 {
00015    fp_int u, v, r;
00016 
00017    /* either zero than gcd is the largest */
00018    if (fp_iszero (a) == 1 && fp_iszero (b) == 0) {
00019      fp_abs (b, c);
00020      return;
00021    }
00022    if (fp_iszero (a) == 0 && fp_iszero (b) == 1) {
00023      fp_abs (a, c);
00024      return;
00025    }
00026 
00027    /* optimized.  At this point if a == 0 then
00028     * b must equal zero too
00029     */
00030    if (fp_iszero (a) == 1) {
00031      fp_zero(c);
00032      return;
00033    }
00034 
00035    /* sort inputs */
00036    if (fp_cmp_mag(a, b) != FP_LT) {
00037       fp_init_copy(&u, a);
00038       fp_init_copy(&v, b);
00039    } else {
00040       fp_init_copy(&u, b);
00041       fp_init_copy(&v, a);
00042    }
00043  
00044    fp_zero(&r);
00045    while (fp_iszero(&v) == FP_NO) {
00046       fp_mod(&u, &v, &r);
00047       fp_copy(&v, &u);
00048       fp_copy(&r, &v);
00049    }
00050    fp_copy(&u, c);
00051 }
00052 
00053 /* $Source: /cvs/libtom/tomsfastmath/src/numtheory/fp_gcd.c,v $ */
00054 /* $Revision: 1.1 $ */
00055 /* $Date: 2007/01/24 21:25:19 $ */