-
+ F582DE56EE9BC1D4CF2EEA35BDABDCD61E0CC93DD186950709E32FC707D2F769669BAFDCFBF2AD074596BA474BF1E7AF5E29EA81CFF2316ACBFCD27A0F93F185mpi/mpi-gcd.c(0 . 0)(1 . 53)
7372 /* mpi-gcd.c - MPI functions
7373 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
7374 *
7375 * This file is part of GnuPG.
7376 *
7377 * GnuPG is free software; you can redistribute it and/or modify
7378 * it under the terms of the GNU General Public License as published by
7379 * the Free Software Foundation; either version 3 of the License, or
7380 * (at your option) any later version.
7381 *
7382 * GnuPG is distributed in the hope that it will be useful,
7383 * but WITHOUT ANY WARRANTY; without even the implied warranty of
7384 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
7385 * GNU General Public License for more details.
7386 *
7387 * You should have received a copy of the GNU General Public License
7388 * along with this program; if not, see <http://www.gnu.org/licenses/>.
7389 */
7390
7391 #include <config.h>
7392 #include <stdio.h>
7393 #include <stdlib.h>
7394 #include "mpi-internal.h"
7395
7396 /****************
7397 * Find the greatest common divisor G of A and B.
7398 * Return: true if this 1, false in all other cases
7399 */
7400 int
7401 mpi_gcd( MPI g, MPI xa, MPI xb )
7402 {
7403 MPI a, b;
7404
7405 a = mpi_copy(xa);
7406 b = mpi_copy(xb);
7407
7408 /* TAOCP Vol II, 4.5.2, Algorithm A */
7409 a->sign = 0;
7410 b->sign = 0;
7411 while( mpi_cmp_ui( b, 0 ) ) {
7412 mpi_fdiv_r( g, a, b ); /* g used as temorary variable */
7413 mpi_set(a,b);
7414 mpi_set(b,g);
7415 }
7416 mpi_set(g, a);
7417
7418 mpi_free(a);
7419 mpi_free(b);
7420 return !mpi_cmp_ui( g, 1);
7421 }
7422
7423
7424