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

[Camm Maguire]

Greetings

Robert Boyer <address@hidden> writes:

> 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"
>    which we read by asking for successive chunks, input(0), input(1), 
> 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
> 
> 
> 

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah