[comp.lang.lisp] WANTED: FAST bignum or modular arithmetic or FFT

klier@ucbarpa.Berkeley.EDU (Pete Klier) (04/07/89)

I would like some fast routines written
in Common Lisp (or some other lisp) for:
 
[in order of preference]
(The routines should work on BIIIIIGnums, e.g. 3000 bits)

     - the modular power, equivalent of (mod (expt a b) N)   
       (all three numbers are ~3000 bits), in 
       O(n-squared log n log log n) or thereabout.
     - bignum multiplication and/or bignum modulus in
       O(n log n log log n) or thereabout.	
     - Fast Fourier transform in O(n log n log log n) or thereabout. 


What I really want is the modular power, but if I have good bignum
multiplication I can implement modular power, and if I have a fast
Fourier transform I can implement bignum arithmetic.  The Common Lisp
implementation(s) I am using has O(n-squared) bignum arithmetic, which
just doesn't cut the mustard for these large numbers. 

 Please respond by email.


Thanks in advance,
    
     Pete Klier
     klier@ernie.Berkeley.EDU

Pete Klier
klier@ernie.Berkeley.EDU