gcl-devel
[Top][All Lists]

## [Gcl-devel] Re: revision & simplification & gmp_powm

 From: Camm Maguire Subject: [Gcl-devel] Re: revision & simplification & gmp_powm Date: 01 Nov 2005 12:31:09 -0500 User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2

Greetings

> Here is a simple correction to the description I sent you of the RSA
> decryption algorithm.  I must have been asleep.  All I have done here is to
> set the constant d to 1.
>
>    Now, the RSA decryption computation simply consists of computing
>
>       m(i) =  (( input(i) ) ^ e) mod (p * q)
>
>    for successive i, where p, q, and e are fixed positive integers (with some
>    other properties not especially relevant to the computation) and each
>    input(i) in a nonnegative integer less than p*q.  We imagine an input
> "file"
> input(2),
>    ..., input(n).  We wish to assemble as our answer m(0), m(1), m(2), ...,
>    m(n).  As soon as we have read any input(i), we can fork off a job to
> compute
>    m(i).  We don't want to fork off too many jobs, of course, and we do want
> to
>    assemble answers in a timely orderly fashion, maximizing use of available
>    hardware, writing the output to an output file as and when we can.
>
> To simplify the example further, one might want to replace (p * q) with just
> single constant, say r.
>
>       m(i) =  (( input(i) ) ^ e) mod r
>
>    for successive i, where r and e are fixed positive integers (with some ...
>
> It is also the case that one can assume that e is less than r.
>
> For all I know, GMP already has a function to do exactly this job very
> efficiently.  I suspect it might be called gmp_powm.  That's what they
> seem to call it in PHP, cf.
>
>   http://aspn.activestate.com/ASPN/docs/PHP/function.gmp-powm.html
>
> So you'd be doing the GCL community a favor by making available directly in
> Lisp access to that gmp_powm function (if it does what I think).  (And maybe
> a host of other gmp functions?)

Pushing forward the rest of gmp has been on my todo list for some
time.  Thus far, I've taken an on-demand approach.  Usually, I've
tried to integrate these functions into existing common lisp
functions, but here I can see no CL function which contains this one
(please correct me if wrong).  Do we need a gmp package?  What are the
other functions you would find useful?

Take care,

>
> Bob
>
>
>

--