1 /* mpi-inv.c - MPI functions
2 * Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
4 * This file is part of GnuPG.
6 * GnuPG is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * GnuPG 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 General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
21 #include "mpi-internal.h"
25 * Calculate the multiplicative inverse X of A mod N
26 * That is: Find the solution x for
30 mpi_invm( MPI x, const MPI a, const MPI n )
32 /* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
33 * modified according to Michael Penk's solution for Exercice 35
34 * with further enhancement */
35 MPI u = NULL, v = NULL;
36 MPI u1 = NULL, u2 = NULL, u3 = NULL;
37 MPI v1 = NULL, v2 = NULL, v3 = NULL;
38 MPI t1 = NULL, t2 = NULL, t3 = NULL;
44 if (mpi_copy(&u, a) < 0) goto cleanup;
45 if (mpi_copy(&v, n) < 0) goto cleanup;
47 for(k=0; !mpi_test_bit(u,0) && !mpi_test_bit(v,0); k++ ) {
48 if (mpi_rshift(u, u, 1) < 0) goto cleanup;
49 if (mpi_rshift(v, v, 1) < 0) goto cleanup;
51 odd = mpi_test_bit(v,0);
53 u1 = mpi_alloc_set_ui(1); if (!u1) goto cleanup;
55 u2 = mpi_alloc_set_ui(0);
56 if (!u2) goto cleanup;
58 if (mpi_copy(&u3, u) < 0) goto cleanup;
59 if (mpi_copy(&v1, v) < 0) goto cleanup;
61 v2 = mpi_alloc( mpi_get_nlimbs(u) ); if (!v2) goto cleanup;
62 if (mpi_sub( v2, u1, u ) < 0) goto cleanup; /* U is used as const 1 */
64 if (mpi_copy(&v3, v) < 0) goto cleanup;
65 if( mpi_test_bit(u, 0) ) { /* u is odd */
66 t1 = mpi_alloc_set_ui(0); if (!t1) goto cleanup;
68 t2 = mpi_alloc_set_ui(1); if (!t2) goto cleanup;
71 if (mpi_copy(&t3, v) < 0) goto cleanup;
76 t1 = mpi_alloc_set_ui(1); if (!t1) goto cleanup;
78 t2 = mpi_alloc_set_ui(0); if (!t2) goto cleanup;
80 if (mpi_copy(&t3, u) < 0) goto cleanup;
85 if( mpi_test_bit(t1, 0) || mpi_test_bit(t2, 0) ) { /* one is odd */
86 if (mpi_add(t1, t1, v) < 0) goto cleanup;
87 if (mpi_sub(t2, t2, u) < 0) goto cleanup;
89 if (mpi_rshift(t1, t1, 1) < 0) goto cleanup;
90 if (mpi_rshift(t2, t2, 1) < 0) goto cleanup;
91 if (mpi_rshift(t3, t3, 1) < 0) goto cleanup;
94 if( mpi_test_bit(t1, 0) )
95 if (mpi_add(t1, t1, v) < 0) goto cleanup;
96 if (mpi_rshift(t1, t1, 1) < 0) goto cleanup;
97 if (mpi_rshift(t3, t3, 1) < 0) goto cleanup;
101 } while( !mpi_test_bit( t3, 0 ) ); /* while t3 is even */
104 if (mpi_set(u1, t1) < 0) goto cleanup;
106 if (mpi_set(u2, t2) < 0) goto cleanup;
107 if (mpi_set(u3, t3) < 0) goto cleanup;
110 if (mpi_sub(v1, v, t1) < 0) goto cleanup;
111 sign = u->sign; u->sign = !u->sign;
113 if (mpi_sub(v2, u, t2) < 0) goto cleanup;
115 sign = t3->sign; t3->sign = !t3->sign;
116 if (mpi_set(v3, t3) < 0) goto cleanup;
119 if (mpi_sub(t1, u1, v1) < 0) goto cleanup;
121 if (mpi_sub(t2, u2, v2) < 0) goto cleanup;
122 if (mpi_sub(t3, u3, v3) < 0) goto cleanup;
124 if (mpi_add(t1, t1, v) < 0) goto cleanup;
126 if (mpi_sub(t2, t2, u) < 0) goto cleanup;
128 } while( mpi_cmp_ui( t3, 0 ) ); /* while t3 != 0 */
129 /* mpi_lshift( u3, k ); */