Coverage Report

Created: 2024-11-21 07:03

/src/libgcrypt/mpi/mpi-gcd.c
Line
Count
Source
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, see <https://www.gnu.org/licenses/>.
18
 * SPDX-License-Identifier: LGPL-2.1-or-later
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
404
{
33
404
    gcry_mpi_t a, b;
34
35
404
    a = mpi_copy(xa);
36
404
    b = mpi_copy(xb);
37
38
    /* TAOCP Vol II, 4.5.2, Algorithm A */
39
404
    a->sign = 0;
40
404
    b->sign = 0;
41
194k
    while (mpi_cmp_ui (b, 0))
42
193k
      {
43
193k
  _gcry_mpi_fdiv_r( g, a, b ); /* G is used as temporary variable. */
44
193k
  mpi_set(a,b);
45
193k
  mpi_set(b,g);
46
193k
      }
47
404
    mpi_set(g, a);
48
49
404
    mpi_free(a);
50
404
    mpi_free(b);
51
404
    return !mpi_cmp_ui( g, 1);
52
404
}