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