Return to invert.c CVS log

Up to [local] / OpenXM_contrib / gmp / mpz

Annotation of OpenXM_contrib/gmp/mpz/invert.c, Revision 1.1.1.3

1.1       maekawa     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,
1.1.1.2   maekawa     3:    otherwise, return 0 and put garbage in INVERSE.
1.1       maekawa     4:
1.1.1.3 ! ohara       5: Copyright 1996, 1997, 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
1.1       maekawa     6:
                      7: This file is part of the GNU MP Library.
                      8:
                      9: The GNU MP Library is free software; you can redistribute it and/or modify
1.1.1.2   maekawa    10: it under the terms of the GNU Lesser General Public License as published by
                     11: the Free Software Foundation; either version 2.1 of the License, or (at your
1.1       maekawa    12: option) any later version.
                     13:
                     14: The GNU MP Library is distributed in the hope that it will be useful, but
                     15: WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
1.1.1.2   maekawa    16: or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
1.1       maekawa    17: License for more details.
                     18:
1.1.1.2   maekawa    19: You should have received a copy of the GNU Lesser General Public License
1.1       maekawa    20: along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
                     21: the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
                     22: MA 02111-1307, USA. */
                     23:
                     24: #include "gmp.h"
1.1.1.2   maekawa    25: #include "gmp-impl.h"
1.1       maekawa    26:
                     27: int
                     28: mpz_invert (mpz_ptr inverse, mpz_srcptr x, mpz_srcptr n)
                     29: {
1.1.1.2   maekawa    30:   mpz_t gcd, tmp;
                     31:   mp_size_t xsize, nsize, size;
                     32:   TMP_DECL (marker);
                     33:
                     34:   xsize = SIZ (x);
                     35:   nsize = SIZ (n);
                     36:   xsize = ABS (xsize);
                     37:   nsize = ABS (nsize);
                     38:   size = MAX (xsize, nsize) + 1;
                     39:
                     40:   /* No inverse exists if the leftside operand is 0.  Likewise, no
                     41:      inverse exists if the mod operand is 1.  */
                     42:   if (xsize == 0 || (nsize == 1 && (PTR (n))[0] == 1))
                     43:     return 0;
                     44:
                     45:   TMP_MARK (marker);
                     46:
                     47:   MPZ_TMP_INIT (gcd, size);
                     48:   MPZ_TMP_INIT (tmp, size);
                     49:   mpz_gcdext (gcd, tmp, (mpz_ptr) 0, x, n);
                     50:
                     51:   /* If no inverse existed, return with an indication of that.  */
1.1.1.3 ! ohara      52:   if (SIZ (gcd) != 1 || PTR(gcd)[0] != 1)
1.1.1.2   maekawa    53:     {
                     54:       TMP_FREE (marker);
                     55:       return 0;
                     56:     }
                     57:
                     58:   /* Make sure we return a positive inverse.  */
                     59:   if (SIZ (tmp) < 0)
                     60:     {
                     61:       if (SIZ (n) < 0)
                     62:        mpz_sub (inverse, tmp, n);
                     63:       else
                     64:        mpz_add (inverse, tmp, n);
                     65:     }
                     66:   else
                     67:     mpz_set (inverse, tmp);
1.1       maekawa    68:
1.1.1.2   maekawa    69:   TMP_FREE (marker);
                     70:   return 1;
1.1       maekawa    71: }