mpi/mpi-gcd.c

   1 /* mpi-gcd.c  -  MPI functions
   2  *      Copyright (C) 1998, 2001, 2002, 2003 Free Software Foundation, Inc.
   3  *
   4  * This file is part of Libgcrypt.
   5  *
   6  * Libgcrypt is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU Lesser General Public License as
   8  * published by the Free Software Foundation; either version 2.1 of
   9  * the License, or (at your option) any later version.
  10  *
  11  * Libgcrypt is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
  19  */
  20
  21 #include <config.h>
  22 #include <stdio.h>
  23 #include <stdlib.h>
  24 #include "mpi-internal.h"
  25
  26 /****************
  27  * Find the greatest common divisor G of A and B.
  28  * Return: true if this 1, false in all other cases
  29  */
  30 int
  31 _gcry_mpi_gcd (gcry_mpi_t g, gcry_mpi_t xa, gcry_mpi_t xb)
  32 {
  33     gcry_mpi_t a, b;
  34
  35     a = mpi_copy(xa);
  36     b = mpi_copy(xb);
  37
  38     /* TAOCP Vol II, 4.5.2, Algorithm A */
  39     a->sign = 0;
  40     b->sign = 0;
  41     while (mpi_cmp_ui (b, 0))
  42       {
  43         _gcry_mpi_fdiv_r( g, a, b ); /* G is used as temporary variable. */
  44         mpi_set(a,b);
  45         mpi_set(b,g);
  46       }
  47     mpi_set(g, a);
  48
  49     mpi_free(a);
  50     mpi_free(b);
  51     return !mpi_cmp_ui( g, 1);
  52 }