All, I tried to add an FFT section to the FAQ, and here is what I got: (please add, or correct errors...) -Lucas Wiman P.S. Sorry if the FAQ is causing more traffic than it is supposed to prevent ;) =========================================================================== Q6.1: How can we perform the massive squarings required for the LL test in reasonable time? A: We use a method known as FFT convolution. In this method, we take the number that we are squaring, and run an FFT on it. This results in an array, and we square each element in that array, and run an IFFT (iverse-FFT). This yields the answer mod some number. This operates in O(n*log(n)) time, which means that it is proportional to n*log(n). This is a signicant improvement over normal multiplication which is O(n^2). =========================================================================== Q6.2: What is an FFT? A: An FFT is a Fast Fourier Transform. These are often used in signal processing, and they are basically transforming a signal into a series of discrete sine and cosine waves. For more information on FTT's, see the following websites: "http://theory.lcs.mit.edu/~fftw/fft-links.html" FFT Introduction (many FFT links) "http://www.spd.eee.strath.ac.uk/~interact/FFT/" Fourier Transform in Signal Processing "http://cfatab.harvard.edu/nr/bookcpdf.html" Numerical Recipes in C (See parts on FFT) I have also heard that the book _Who is Fourier_ is quite good, though I have not read it. Thank you Vincent J. Mooney Jr. ________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
