-
+ F582DE56EE9BC1D4CF2EEA35BDABDCD61E0CC93DD186950709E32FC707D2F769669BAFDCFBF2AD074596BA474BF1E7AF5E29EA81CFF2316ACBFCD27A0F93F185mpi/mpi-gcd.c(0 . 0)(1 . 53)
6971 /* mpi-gcd.c - MPI functions
6972 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
6973 *
6974 * This file is part of GnuPG.
6975 *
6976 * GnuPG is free software; you can redistribute it and/or modify
6977 * it under the terms of the GNU General Public License as published by
6978 * the Free Software Foundation; either version 3 of the License, or
6979 * (at your option) any later version.
6980 *
6981 * GnuPG is distributed in the hope that it will be useful,
6982 * but WITHOUT ANY WARRANTY; without even the implied warranty of
6983 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
6984 * GNU General Public License for more details.
6985 *
6986 * You should have received a copy of the GNU General Public License
6987 * along with this program; if not, see <http://www.gnu.org/licenses/>.
6988 */
6989
6990 #include <config.h>
6991 #include <stdio.h>
6992 #include <stdlib.h>
6993 #include "mpi-internal.h"
6994
6995 /****************
6996 * Find the greatest common divisor G of A and B.
6997 * Return: true if this 1, false in all other cases
6998 */
6999 int
7000 mpi_gcd( MPI g, MPI xa, MPI xb )
7001 {
7002 MPI a, b;
7003
7004 a = mpi_copy(xa);
7005 b = mpi_copy(xb);
7006
7007 /* TAOCP Vol II, 4.5.2, Algorithm A */
7008 a->sign = 0;
7009 b->sign = 0;
7010 while( mpi_cmp_ui( b, 0 ) ) {
7011 mpi_fdiv_r( g, a, b ); /* g used as temorary variable */
7012 mpi_set(a,b);
7013 mpi_set(b,g);
7014 }
7015 mpi_set(g, a);
7016
7017 mpi_free(a);
7018 mpi_free(b);
7019 return !mpi_cmp_ui( g, 1);
7020 }
7021
7022
7023