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
);