initially checkin
[gnupg.git] / mpi / mpi-inv.c
1 /* mpi-inv.c  -  MPI functions
2  *      Copyright (c) 1997 by Werner Koch (dd9jn)
3  *
4  * This file is part of G10.
5  *
6  * G10 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.
10  *
11  * G10 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.
15  *
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
19  */
20
21 #include <config.h>
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include "mpi-internal.h"
25
26 /****************
27  * Calculate the multiplicative inverse X of U mod V
28  * That is: Find the solution for
29  *              1 = (u*x) mod v
30  * This has only a unique solution if U and V are relatively prime.
31  * Returns 0 if a solution was found.
32  */
33 int
34 mpi_inv_mod( MPI x, MPI u, MPI v )
35 {
36   #if 0
37     /* Extended Euclid's algorithm (See TAOPC Vol II, 4.52. Alg X) */
38     MPI u1, u2, u3, v1, v2, v3, q, t1, t2, t3;
39
40     u1 = mpi_alloc_set_ui(1);
41     u2 = mpi_alloc_set_ui(0);
42     u3 = mpi_copy(u);
43     v1 = mpi_alloc_set_ui(0);
44     v2 = mpi_alloc_set_ui(1);
45     v3 = mpi_copy(v);
46     q  = mpi_alloc( mpi_get_nlimbs(u) );
47     t1 = mpi_alloc( mpi_get_nlimbs(u) );
48     t2 = mpi_alloc( mpi_get_nlimbs(u) );
49     t3 = mpi_alloc( mpi_get_nlimbs(u) );
50     while( mpi_cmp_ui( v3, 0 ) ) {
51       /*log_debug("----------------------\n");
52         log_mpidump("q =", u1);
53         log_mpidump("u1=", u1);
54         log_mpidump("u2=", u2);
55         log_mpidump("u3=", u3);
56         log_mpidump("v1=", v1);
57         log_mpidump("v2=", v2);
58         log_mpidump("v3=", v3); */
59         mpi_fdiv_q( q, u3, v3 );
60         mpi_mul(t1, v1, q); mpi_mul(t2, v2, q); mpi_mul(t3, v3, q);
61         mpi_sub(t1, u1, t1); mpi_sub(t2, u2, t2); mpi_sub(t3, u3, t3);
62
63         mpi_set(u1, v1); mpi_set(u2, v2); mpi_set(u3, v3);
64         mpi_set(v1, t1); mpi_set(v2, t2); mpi_set(v3, t3);
65     }
66     mpi_set(x, u3);
67
68     mpi_free(u1);
69     mpi_free(u2);
70     mpi_free(u3);
71     mpi_free(v1);
72     mpi_free(v2);
73     mpi_free(v3);
74     mpi_free(q);
75     mpi_free(t1);
76     mpi_free(t2);
77     mpi_free(t3);
78   #endif
79
80     /*****************************
81      *  1. Init:   g0 = u  g1 = v  v0  = 0   v1 = 1
82      *  2. Test:   if g1 is 0 terminate. Result = v0 < 0: v0 + n
83      *                                              else: v0
84      *  3. Divide: div,rem = g0 / g1
85      *             t1 = v0 - div * v1
86      *             v0 = v1
87      *             v1 = t1
88      *             g0 = g1
89      *             g1 = rem
90      *     continue with step 2.
91      */
92     MPI g0, g1, v0, v1, div, rem, t1;
93
94     g0 = mpi_copy(v);
95     g1 = mpi_copy(u);
96     v0 = mpi_alloc_set_ui( 0 );
97     v1 = mpi_alloc_set_ui( 1 );
98     div = mpi_alloc(mpi_get_nlimbs(v));
99     rem = mpi_alloc(mpi_get_nlimbs(v));
100     t1  = mpi_alloc(mpi_get_nlimbs(v));
101     while( mpi_cmp_ui( g1, 0) ) {
102         mpi_fdiv_qr(div, rem, g0, g1);
103         mpi_mul(t1, div, v1);
104         mpi_sub(t1, v0, t1);
105         mpi_set(v0, v1);
106         mpi_set(v1, t1);
107         mpi_set(g0, g1);
108         mpi_set(g1, rem);
109
110     }
111     if( mpi_cmp_ui( v0, 0) < 0 )
112         mpi_add( x, v0, v);
113     else
114         mpi_set( x, v0);
115
116     mpi_free(g0);
117     mpi_free(g1);
118     mpi_free(v0);
119     mpi_free(v1);
120     mpi_free(div);
121     mpi_free(rem);
122     mpi_free(t1);
123     return 0;
124 }
125
126
127