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.2

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.2 ! maekawa     5: Copyright (C) 1996, 1997, 1998, 1999, 2000 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: #if __STDC__
                     29: mpz_invert (mpz_ptr inverse, mpz_srcptr x, mpz_srcptr n)
                     30: #else
                     31: mpz_invert (inverse, x, n)
                     32:      mpz_ptr inverse;
                     33:      mpz_srcptr x, n;
                     34: #endif
                     35: {
1.1.1.2 ! maekawa    36:   mpz_t gcd, tmp;
        !            37:   mp_size_t xsize, nsize, size;
        !            38:   TMP_DECL (marker);
        !            39:
        !            40:   xsize = SIZ (x);
        !            41:   nsize = SIZ (n);
        !            42:   xsize = ABS (xsize);
        !            43:   nsize = ABS (nsize);
        !            44:   size = MAX (xsize, nsize) + 1;
        !            45:
        !            46:   /* No inverse exists if the leftside operand is 0.  Likewise, no
        !            47:      inverse exists if the mod operand is 1.  */
        !            48:   if (xsize == 0 || (nsize == 1 && (PTR (n))[0] == 1))
        !            49:     return 0;
        !            50:
        !            51:   TMP_MARK (marker);
        !            52:
        !            53:   MPZ_TMP_INIT (gcd, size);
        !            54:   MPZ_TMP_INIT (tmp, size);
        !            55:   mpz_gcdext (gcd, tmp, (mpz_ptr) 0, x, n);
        !            56:
        !            57:   /* If no inverse existed, return with an indication of that.  */
        !            58:   if (gcd->_mp_size != 1 || (gcd->_mp_d)[0] != 1)
        !            59:     {
        !            60:       TMP_FREE (marker);
        !            61:       return 0;
        !            62:     }
        !            63:
        !            64:   /* Make sure we return a positive inverse.  */
        !            65:   if (SIZ (tmp) < 0)
        !            66:     {
        !            67:       if (SIZ (n) < 0)
        !            68:        mpz_sub (inverse, tmp, n);
        !            69:       else
        !            70:        mpz_add (inverse, tmp, n);
        !            71:     }
        !            72:   else
        !            73:     mpz_set (inverse, tmp);
1.1       maekawa    74:
1.1.1.2 ! maekawa    75:   TMP_FREE (marker);
        !            76:   return 1;
1.1       maekawa    77: }