mpi-genesis~ 1
mpi-genesis~ 2 * Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
mpi-genesis~ 3 *
mpi-genesis~ 4 * This file is part of GnuPG.
mpi-genesis~ 5 *
mpi-genesis~ 6 * GnuPG is free software; you can redistribute it and/or modify
mpi-genesis~ 7 * it under the terms of the GNU General Public License as published by
mpi-genesis~ 8 * the Free Software Foundation; either version 3 of the License, or
mpi-genesis~ 9 * (at your option) any later version.
mpi-genesis~ 10 *
mpi-genesis~ 11 * GnuPG is distributed in the hope that it will be useful,
mpi-genesis~ 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
mpi-genesis~ 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
mpi-genesis~ 14 * GNU General Public License for more details.
mpi-genesis~ 15 *
mpi-genesis~ 16 * You should have received a copy of the GNU General Public License
mpi-genesis~ 17 * along with this program; if not, see <http:
mpi-genesis~ 18 */
mpi-genesis~ 19
mpi-genesis~ 20 #include <config.h>
mpi-genesis~ 21 #include <stdio.h>
mpi-genesis~ 22 #include <stdlib.h>
mpi-genesis~ 23 #include "mpi-internal.h"
mpi-genesis~ 24 #include "longlong.h"
mpi-genesis~ 25 #include <assert.h>
mpi-genesis~ 26
mpi-genesis~ 27 static int
mpi-genesis~ 28 build_index( MPI *exparray, int k, int i, int t )
mpi-genesis~ 29 {
mpi-genesis~ 30 int j, bitno;
mpi-genesis~ 31 int idx = 0;
mpi-genesis~ 32
mpi-genesis~ 33 bitno = t-i;
mpi-genesis~ 34 for(j=k-1; j >= 0; j-- ) {
mpi-genesis~ 35 idx <<= 1;
mpi-genesis~ 36 if( mpi_test_bit( exparray[j], bitno ) )
mpi-genesis~ 37 idx |= 1;
mpi-genesis~ 38 }
mpi-genesis~ 39 return idx;
mpi-genesis~ 40 }
mpi-genesis~ 41
mpi-genesis~ 42
mpi-genesis~ 43 * RES = (BASE[0] ^ EXP[0]) * (BASE[1] ^ EXP[1]) * ... * mod M
mpi-genesis~ 44 */
mpi-genesis~ 45 void
mpi-genesis~ 46 mpi_mulpowm( MPI res, MPI *basearray, MPI *exparray, MPI m)
mpi-genesis~ 47 {
mpi-genesis~ 48 int k;
mpi-genesis~ 49 int t;
mpi-genesis~ 50 int i, j, idx;
mpi-genesis~ 51 MPI *G;
mpi-genesis~ 52 MPI tmp;
mpi-genesis~ 53
mpi-genesis~ 54 for(k=0; basearray[k]; k++ )
mpi-genesis~ 55 ;
mpi-genesis~ 56 assert(k);
mpi-genesis~ 57 for(t=0, i=0; (tmp=exparray[i]); i++ ) {
mpi-genesis~ 58 j = mpi_get_nbits(tmp);
mpi-genesis~ 59 if( j > t )
mpi-genesis~ 60 t = j;
mpi-genesis~ 61 }
mpi-genesis~ 62 assert(i==k);
mpi-genesis~ 63 assert(t);
mpi-genesis~ 64 assert( k < 10 );
mpi-genesis~ 65
mpi-genesis~ 66 G = xmalloc_clear( (1<<k) * sizeof *G );
mpi-genesis~ 67
mpi-genesis~ 68 tmp = mpi_alloc( mpi_get_nlimbs(m)+1 );
mpi-genesis~ 69 mpi_set_ui( res, 1 );
mpi-genesis~ 70 for(i = 1; i <= t; i++ ) {
mpi-genesis~ 71 mpi_mulm(tmp, res, res, m );
mpi-genesis~ 72 idx = build_index( exparray, k, i, t );
mpi-genesis~ 73 assert( idx >= 0 && idx < (1<<k) );
mpi-genesis~ 74 if( !G[idx] ) {
mpi-genesis~ 75 if( !idx )
mpi-genesis~ 76 G[0] = mpi_alloc_set_ui( 1 );
mpi-genesis~ 77 else {
mpi-genesis~ 78 for(j=0; j < k; j++ ) {
mpi-genesis~ 79 if( (idx & (1<<j) ) ) {
mpi-genesis~ 80 if( !G[idx] )
mpi-genesis~ 81 G[idx] = mpi_copy( basearray[j] );
mpi-genesis~ 82 else
mpi-genesis~ 83 mpi_mulm( G[idx], G[idx], basearray[j], m );
mpi-genesis~ 84 }
mpi-genesis~ 85 }
mpi-genesis~ 86 if( !G[idx] )
mpi-genesis~ 87 G[idx] = mpi_alloc(0);
mpi-genesis~ 88 }
mpi-genesis~ 89 }
mpi-genesis~ 90 mpi_mulm(res, tmp, G[idx], m );
mpi-genesis~ 91 }
mpi-genesis~ 92
mpi-genesis~ 93
mpi-genesis~ 94 mpi_free(tmp);
mpi-genesis~ 95 for(i=0; i < (1<<k); i++ )
mpi-genesis~ 96 mpi_free(G[i]);
mpi-genesis~ 97 xfree(G);
mpi-genesis~ 98 }