1 /* mpz_invert (inv, x, n). Find multiplicative inverse of X in Z(N).
2 If X has an inverse, return non-zero and store inverse in INVERSE,
3 otherwise, return 0 and put garbage in INVERSE.
5 Copyright 1996, 1997, 1998, 1999, 2000, 2001, 2005 Free Software Foundation,
8 This file is part of the GNU MP Library.
10 The GNU MP Library is free software; you can redistribute it and/or modify
11 it under the terms of the GNU Lesser General Public License as published by
12 the Free Software Foundation; either version 3 of the License, or (at your
13 option) any later version.
15 The GNU MP Library is distributed in the hope that it will be useful, but
16 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
17 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
18 License for more details.
20 You should have received a copy of the GNU Lesser General Public License
21 along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
27 mpz_invert (mpz_ptr inverse, mpz_srcptr x, mpz_srcptr n)
30 mp_size_t xsize, nsize, size;
37 size = MAX (xsize, nsize) + 1;
39 /* No inverse exists if the leftside operand is 0. Likewise, no
40 inverse exists if the mod operand is 1. */
41 if (xsize == 0 || (nsize == 1 && (PTR (n))[0] == 1))
46 MPZ_TMP_INIT (gcd, size);
47 MPZ_TMP_INIT (tmp, size);
48 mpz_gcdext (gcd, tmp, (mpz_ptr) 0, x, n);
50 /* If no inverse existed, return with an indication of that. */
51 if (SIZ (gcd) != 1 || PTR(gcd)[0] != 1)
57 /* Make sure we return a positive inverse. */
61 mpz_sub (inverse, tmp, n);
63 mpz_add (inverse, tmp, n);
66 mpz_set (inverse, tmp);