-
+ 0AD3099F1DB858EB1D25E7BCCC7461F981ADAB9F7853346EF97A161639D3BCC31F22539ABB342C96EB087F0FCE3C91BB26A7E9C78C92DC33CA1FCA5EFCF534FEeucrypt/mpi/mpi-gcd.c(0 . 0)(1 . 57)
3610 /* mpi-gcd.c - MPI functions
3611 * Modified by No Such Labs. (C) 2015. See README.
3612 *
3613 * This file was originally part of Gnu Privacy Guard (GPG), ver. 1.4.10,
3614 * SHA256(gnupg-1.4.10.tar.gz):
3615 * 0bfd74660a2f6cedcf7d8256db4a63c996ffebbcdc2cf54397bfb72878c5a85a
3616 * (C) 1994-2005 Free Software Foundation, Inc.
3617 *
3618 * This program is free software: you can redistribute it and/or modify
3619 * it under the terms of the GNU General Public License as published by
3620 * the Free Software Foundation, either version 3 of the License, or
3621 * (at your option) any later version.
3622 *
3623 * This program is distributed in the hope that it will be useful,
3624 * but WITHOUT ANY WARRANTY; without even the implied warranty of
3625 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
3626 * GNU General Public License for more details.
3627 *
3628 * You should have received a copy of the GNU General Public License
3629 * along with this program. If not, see <http://www.gnu.org/licenses/>.
3630 */
3631
3632 #include <stdio.h>
3633 #include <stdlib.h>
3634
3635 #include "knobs.h"
3636 #include "mpi-internal.h"
3637
3638 /****************
3639 * Find the greatest common divisor G of A and B.
3640 * Return: true if this 1, false in all other cases
3641 */
3642 int
3643 mpi_gcd( MPI g, MPI xa, MPI xb )
3644 {
3645 MPI a, b;
3646
3647 a = mpi_copy(xa);
3648 b = mpi_copy(xb);
3649
3650 /* TAOCP Vol II, 4.5.2, Algorithm A */
3651 a->sign = 0;
3652 b->sign = 0;
3653 while( mpi_cmp_ui( b, 0 ) ) {
3654 mpi_fdiv_r( g, a, b ); /* g used as temorary variable */
3655 mpi_set(a,b);
3656 mpi_set(b,g);
3657 }
3658 mpi_set(g, a);
3659
3660 mpi_free(a);
3661 mpi_free(b);
3662 return !mpi_cmp_ui( g, 1);
3663 }
3664
3665
3666