lib/mpi/mpi-inv.c

0001 /* mpi-inv.c  -  MPI functions
0002  *  Copyright (C) 1998, 2001, 2002, 2003 Free Software Foundation, Inc.
0003  *
0004  * This file is part of Libgcrypt.
0005  *
0006  * Libgcrypt is free software; you can redistribute it and/or modify
0007  * it under the terms of the GNU Lesser General Public License as
0008  * published by the Free Software Foundation; either version 2.1 of
0009  * the License, or (at your option) any later version.
0010  *
0011  * Libgcrypt is distributed in the hope that it will be useful,
0012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
0013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
0014  * GNU Lesser General Public License for more details.
0015  *
0016  * You should have received a copy of the GNU Lesser General Public
0017  * License along with this program; if not, see <http://www.gnu.org/licenses/>.
0018  */
0019
0020 #include "mpi-internal.h"
0021
0022 /****************
0023  * Calculate the multiplicative inverse X of A mod N
0024  * That is: Find the solution x for
0025  *      1 = (a*x) mod n
0026  */
0027 int mpi_invm(MPI x, MPI a, MPI n)
0028 {
0029     /* Extended Euclid's algorithm (See TAOCP Vol II, 4.5.2, Alg X)
0030      * modified according to Michael Penk's solution for Exercise 35
0031      * with further enhancement
0032      */
0033     MPI u, v, u1, u2 = NULL, u3, v1, v2 = NULL, v3, t1, t2 = NULL, t3;
0034     unsigned int k;
0035     int sign;
0036     int odd;
0037
0038     if (!mpi_cmp_ui(a, 0))
0039         return 0; /* Inverse does not exists.  */
0040     if (!mpi_cmp_ui(n, 1))
0041         return 0; /* Inverse does not exists.  */
0042
0043     u = mpi_copy(a);
0044     v = mpi_copy(n);
0045
0046     for (k = 0; !mpi_test_bit(u, 0) && !mpi_test_bit(v, 0); k++) {
0047         mpi_rshift(u, u, 1);
0048         mpi_rshift(v, v, 1);
0049     }
0050     odd = mpi_test_bit(v, 0);
0051
0052     u1 = mpi_alloc_set_ui(1);
0053     if (!odd)
0054         u2 = mpi_alloc_set_ui(0);
0055     u3 = mpi_copy(u);
0056     v1 = mpi_copy(v);
0057     if (!odd) {
0058         v2 = mpi_alloc(mpi_get_nlimbs(u));
0059         mpi_sub(v2, u1, u); /* U is used as const 1 */
0060     }
0061     v3 = mpi_copy(v);
0062     if (mpi_test_bit(u, 0)) { /* u is odd */
0063         t1 = mpi_alloc_set_ui(0);
0064         if (!odd) {
0065             t2 = mpi_alloc_set_ui(1);
0066             t2->sign = 1;
0067         }
0068         t3 = mpi_copy(v);
0069         t3->sign = !t3->sign;
0070         goto Y4;
0071     } else {
0072         t1 = mpi_alloc_set_ui(1);
0073         if (!odd)
0074             t2 = mpi_alloc_set_ui(0);
0075         t3 = mpi_copy(u);
0076     }
0077
0078     do {
0079         do {
0080             if (!odd) {
0081                 if (mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0)) {
0082                     /* one is odd */
0083                     mpi_add(t1, t1, v);
0084                     mpi_sub(t2, t2, u);
0085                 }
0086                 mpi_rshift(t1, t1, 1);
0087                 mpi_rshift(t2, t2, 1);
0088                 mpi_rshift(t3, t3, 1);
0089             } else {
0090                 if (mpi_test_bit(t1, 0))
0091                     mpi_add(t1, t1, v);
0092                 mpi_rshift(t1, t1, 1);
0093                 mpi_rshift(t3, t3, 1);
0094             }
0095 Y4:
0096             ;
0097         } while (!mpi_test_bit(t3, 0)); /* while t3 is even */
0098
0099         if (!t3->sign) {
0100             mpi_set(u1, t1);
0101             if (!odd)
0102                 mpi_set(u2, t2);
0103             mpi_set(u3, t3);
0104         } else {
0105             mpi_sub(v1, v, t1);
0106             sign = u->sign; u->sign = !u->sign;
0107             if (!odd)
0108                 mpi_sub(v2, u, t2);
0109             u->sign = sign;
0110             sign = t3->sign; t3->sign = !t3->sign;
0111             mpi_set(v3, t3);
0112             t3->sign = sign;
0113         }
0114         mpi_sub(t1, u1, v1);
0115         if (!odd)
0116             mpi_sub(t2, u2, v2);
0117         mpi_sub(t3, u3, v3);
0118         if (t1->sign) {
0119             mpi_add(t1, t1, v);
0120             if (!odd)
0121                 mpi_sub(t2, t2, u);
0122         }
0123     } while (mpi_cmp_ui(t3, 0)); /* while t3 != 0 */
0124     /* mpi_lshift( u3, k ); */
0125     mpi_set(x, u1);
0126
0127     mpi_free(u1);
0128     mpi_free(v1);
0129     mpi_free(t1);
0130     if (!odd) {
0131         mpi_free(u2);
0132         mpi_free(v2);
0133         mpi_free(t2);
0134     }
0135     mpi_free(u3);
0136     mpi_free(v3);
0137     mpi_free(t3);
0138
0139     mpi_free(u);
0140     mpi_free(v);
0141     return 1;
0142 }
0143 EXPORT_SYMBOL_GPL(mpi_invm);