gnupg-1.0.6/mpi/mpi-inv.c

[Carlo Perassi]

Hi.

I ported nine PRNGs to the GNU Scientific Library
(http://sources.redhat.com/gsl)

I studied (a very little part of) TAOCP, Volume II and I was looking for 
a GPL implementation of the modular inverse function.

I found one on gnupg:
gnupg-1.0.6/mpi/mpi-inv.c

In this file I discovered you referred to TAOCP too:

(on line 80)
/* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
  * modified according to Michael Penk's solution for Exercice 35 */
$
/* FIXME: we can simplify this in most cases (see Knuth) */

by the way: two little typos
s/TAOPC/TAOCP
s/Exercice/Exercise

and
(on line 161)
/* Extended Euclid's algorithm (See TAOPC Vol II, 4.5.2, Alg X)
  * modified according to Michael Penk's solution for Exercice 35
  * with further enhancement */

same typos

I'd like to try GNUPG like a modular algebra library so I should pass to 
mpi_invm three MPI.
I read include/mpi.h to find how MPI is made.
MPI is

struct gcry_mpi {
     int alloced; /* array size (# of allocated limbs) */
     int nlimbs; /* number of valid limbs */
     int nbits; /* the real number of valid bits (info only) */
     int sign; /* indicates a negative number */
     unsigned flags; /* bit 0: array must be allocated in secure memory
                        space */
                     /* bit 1: the mpi is encrypted */
                     /* bit 2: the limb is a pointer to some m_alloced */
                     /*        data */
     mpi_limb_t *d;  /* array with the limbs */
};

typedef struct gcry_mpi *MPI;

So to use it as an algebra library I should understand limbs (???) and 
so on...

How to find that all? (I can continue reading the whole thing but... 
it's not so fast)
I also started studing tools/mpicalc.c to understand how mpi_invm is 
used but it's not so trivial because the mathematical part is merged 
into cryptographic things...

I could try to "fix the FIXME :-P" in mpi-inv.c but first I should 
investigate more your architecture... can you help me?

Thanks for your patience.

-- 
Carlo Perassi
http://www.linux.it/~carlo/