-
+ 0AD3099F1DB858EB1D25E7BCCC7461F981ADAB9F7853346EF97A161639D3BCC31F22539ABB342C96EB087F0FCE3C91BB26A7E9C78C92DC33CA1FCA5EFCF534FEsmg_comms/mpi/mpi-gcd.c(0 . 0)(1 . 57)
4349 /* mpi-gcd.c - MPI functions
4350 * Modified by No Such Labs. (C) 2015. See README.
4351 *
4352 * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10,
4353 * SHA256(gnupg-1.4.10.tar.gz):
4354 * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a
4355 * (C) 1994-2005 Free Software Foundation, Inc.
4356 *
4357 * This program is free software: you can redistribute it and/or modify
4358 * it under the terms of the GNU General Public License as published by
4359 * the Free Software Foundation, either version 3 of the License, or
4360 * (at your option) any later version.
4361 *
4362 * This program is distributed in the hope that it will be useful,
4363 * but WITHOUT ANY WARRANTY; without even the implied warranty of
4364 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
4365 * GNU General Public License for more details.
4366 *
4367 * You should have received a copy of the GNU General Public License
4368 * along with this program. If not, see <http://www.gnu.org/licenses/>.
4369 */
4370
4371 #include <stdio.h>
4372 #include <stdlib.h>
4373
4374 #include "knobs.h"
4375 #include "mpi-internal.h"
4376
4377 /****************
4378 * Find the greatest common divisor G of A and B.
4379 * Return: true if this 1, false in all other cases
4380 */
4381 int
4382 mpi_gcd( MPI g, MPI xa, MPI xb )
4383 {
4384 MPI a, b;
4385
4386 a = mpi_copy(xa);
4387 b = mpi_copy(xb);
4388
4389 /* TAOCP Vol II, 4.5.2, Algorithm A */
4390 a->sign = 0;
4391 b->sign = 0;
4392 while( mpi_cmp_ui( b, 0 ) ) {
4393 mpi_fdiv_r( g, a, b ); /* g used as temorary variable */
4394 mpi_set(a,b);
4395 mpi_set(b,g);
4396 }
4397 mpi_set(g, a);
4398
4399 mpi_free(a);
4400 mpi_free(b);
4401 return !mpi_cmp_ui( g, 1);
4402 }
4403
4404
4405