**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