Line data    Source code

       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        9638 : _gcry_mpi_gcd (gcry_mpi_t g, gcry_mpi_t xa, gcry_mpi_t xb)
      32             : {
      33             :     gcry_mpi_t a, b;
      34             : 
      35        9638 :     a = mpi_copy(xa);
      36        9638 :     b = mpi_copy(xb);
      37             : 
      38             :     /* TAOCP Vol II, 4.5.2, Algorithm A */
      39        9638 :     a->sign = 0;
      40        9638 :     b->sign = 0;
      41       92479 :     while (mpi_cmp_ui (b, 0))
      42             :       {
      43       73203 :         _gcry_mpi_fdiv_r( g, a, b ); /* G is used as temporary variable. */
      44       73203 :         mpi_set(a,b);
      45       73203 :         mpi_set(b,g);
      46             :       }
      47        9638 :     mpi_set(g, a);
      48             : 
      49        9638 :     mpi_free(a);
      50        9638 :     mpi_free(b);
      51        9638 :     return !mpi_cmp_ui( g, 1);
      52             : }