Xref: utzoo comp.lang.lisp:1628 sci.math.symbolic:675
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!ucbvax!ucbarpa.Berkeley.EDU!klier
From: klier@ucbarpa.Berkeley.EDU (Pete Klier)
Newsgroups: comp.lang.lisp,sci.math.symbolic
Subject: WANTED: FAST bignum or modular arithmetic or FFT
Keywords: NlogN, FFT, bignum, modular arithmetic, Common Lisp
Message-ID: <28718@ucbvax.BERKELEY.EDU>
Date: 7 Apr 89 02:25:24 GMT
Sender: usenet@ucbvax.BERKELEY.EDU
Distribution: na
Lines: 30

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