From: Pete Klier
Subject: WANTED: FAST bignum or modular arithmetic or FFT
Date:
Message-ID: <28718@ucbvax.BERKELEY.EDU>
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
·····@ernie.Berkeley.EDU
Pete Klier
·····@ernie.Berkeley.EDU