LXR linux/lib/mpi/mpi-inv.c

   1/* mpi-inv.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 <http://www.gnu.org/licenses/>.
  18 */
  19
  20#include "mpi-internal.h"
  21
  22/****************
  23 * Calculate the multiplicative inverse X of A mod N
  24 * That is: Find the solution x for
  25 *              1 = (a*x) mod n
  26 */
  27int mpi_invm(MPI x, MPI a, MPI n)
  28{
  29        /* Extended Euclid's algorithm (See TAOCP Vol II, 4.5.2, Alg X)
  30         * modified according to Michael Penk's solution for Exercise 35
  31         * with further enhancement
  32         */
  33        MPI u, v, u1, u2 = NULL, u3, v1, v2 = NULL, v3, t1, t2 = NULL, t3;
  34        unsigned int k;
  35        int sign;
  36        int odd;
  37
  38        if (!mpi_cmp_ui(a, 0))
  39                return 0; /* Inverse does not exists.  */
  40        if (!mpi_cmp_ui(n, 1))
  41                return 0; /* Inverse does not exists.  */
  42
  43        u = mpi_copy(a);
  44        v = mpi_copy(n);
  45
  46        for (k = 0; !mpi_test_bit(u, 0) && !mpi_test_bit(v, 0); k++) {
  47                mpi_rshift(u, u, 1);
  48                mpi_rshift(v, v, 1);
  49        }
  50        odd = mpi_test_bit(v, 0);
  51
  52        u1 = mpi_alloc_set_ui(1);
  53        if (!odd)
  54                u2 = mpi_alloc_set_ui(0);
  55        u3 = mpi_copy(u);
  56        v1 = mpi_copy(v);
  57        if (!odd) {
  58                v2 = mpi_alloc(mpi_get_nlimbs(u));
  59                mpi_sub(v2, u1, u); /* U is used as const 1 */
  60        }
  61        v3 = mpi_copy(v);
  62        if (mpi_test_bit(u, 0)) { /* u is odd */
  63                t1 = mpi_alloc_set_ui(0);
  64                if (!odd) {
  65                        t2 = mpi_alloc_set_ui(1);
  66                        t2->sign = 1;
  67                }
  68                t3 = mpi_copy(v);
  69                t3->sign = !t3->sign;
  70                goto Y4;
  71        } else {
  72                t1 = mpi_alloc_set_ui(1);
  73                if (!odd)
  74                        t2 = mpi_alloc_set_ui(0);
  75                t3 = mpi_copy(u);
  76        }
  77
  78        do {
  79                do {
  80                        if (!odd) {
  81                                if (mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0)) {
  82                                        /* one is odd */
  83                                        mpi_add(t1, t1, v);
  84                                        mpi_sub(t2, t2, u);
  85                                }
  86                                mpi_rshift(t1, t1, 1);
  87                                mpi_rshift(t2, t2, 1);
  88                                mpi_rshift(t3, t3, 1);
  89                        } else {
  90                                if (mpi_test_bit(t1, 0))
  91                                        mpi_add(t1, t1, v);
  92                                mpi_rshift(t1, t1, 1);
  93                                mpi_rshift(t3, t3, 1);
  94                        }
  95Y4:
  96                        ;
  97                } while (!mpi_test_bit(t3, 0)); /* while t3 is even */
  98
  99                if (!t3->sign) {
 100                        mpi_set(u1, t1);
 101                        if (!odd)
 102                                mpi_set(u2, t2);
 103                        mpi_set(u3, t3);
 104                } else {
 105                        mpi_sub(v1, v, t1);
 106                        sign = u->sign; u->sign = !u->sign;
 107                        if (!odd)
 108                                mpi_sub(v2, u, t2);
 109                        u->sign = sign;
 110                        sign = t3->sign; t3->sign = !t3->sign;
 111                        mpi_set(v3, t3);
 112                        t3->sign = sign;
 113                }
 114                mpi_sub(t1, u1, v1);
 115                if (!odd)
 116                        mpi_sub(t2, u2, v2);
 117                mpi_sub(t3, u3, v3);
 118                if (t1->sign) {
 119                        mpi_add(t1, t1, v);
 120                        if (!odd)
 121                                mpi_sub(t2, t2, u);
 122                }
 123        } while (mpi_cmp_ui(t3, 0)); /* while t3 != 0 */
 124        /* mpi_lshift( u3, k ); */
 125        mpi_set(x, u1);
 126
 127        mpi_free(u1);
 128        mpi_free(v1);
 129        mpi_free(t1);
 130        if (!odd) {
 131                mpi_free(u2);
 132                mpi_free(v2);
 133                mpi_free(t2);
 134        }
 135        mpi_free(u3);
 136        mpi_free(v3);
 137        mpi_free(t3);
 138
 139        mpi_free(u);
 140        mpi_free(v);
 141        return 1;
 142}
 143EXPORT_SYMBOL_GPL(mpi_invm);
 144