mersenneforum.org > Math Integer FFT
 Register FAQ Search Today's Posts Mark Forums Read

 2004-07-27, 19:36 #1 nevarcds     Apr 2004 Blacksburg, VA 32 Posts Integer FFT Could anyone point me to some reference / explanation of an all-integer FFT? I have a basic understanding of the complex-number FFT, but am having difficulty deriving an integer FFT (an FFT performed mod some prime). From my meager understanding, you need a prime that has roots of unity. I believe the length of the FFT is determined by the factors of the Prime minus one. Is this correct? I am attempting to draw the butterfly diagram for a 4-point integer FFT using P = 13 (roots of unity being 7 and 11). Any assistance would be appreciated. Thanks! Nevarcds
 2004-07-27, 20:21 #2 nevarcds     Apr 2004 Blacksburg, VA 10012 Posts Problem fixed I believe I may have found my problem... I should be using an Nth primitive root of unity... 5 or 8 in this case. Any additional insights are appreciated. Nevarcds
2004-07-28, 15:53   #3
R.D. Silverman

Nov 2003

746010 Posts

Quote:
 Originally Posted by nevarcds I believe I may have found my problem... I should be using an Nth primitive root of unity... 5 or 8 in this case. Any additional insights are appreciated. Nevarcds

For a complete description of how to do integer FFT's see:

P. Montgomery & R. Silverman
An FFT Extension to the P-1 Factoring Algorithm
Math. Comp. #54, April 1990

You always need a generator with full period, so yes, you do need a
*primitive* n'th root of unity modulo your prime.

To work modulo composites, you reduce the composite modulo primes
that are 1 mod the length of the fft. Then you do the fft mod each prime
and paste the results together with the CRT. The above paper gives the
details.

 2004-07-28, 16:31 #4 akruppa     "Nancy" Aug 2002 Alexandria 246710 Posts Two other sources that describe FFTs in general and mention NTTs are Jörg Arndt's fxtbook Carey Bloodworth's page Alex
2004-07-28, 19:14   #5
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by akruppa Two other sources that describe FFTs in general and mention NTTs are Jörg Arndt's fxtbook Carey Bloodworth's page Alex
I think that the FFT "bible" is Nussbaumer's book:

H.J. Nussbaumer
Fast Fourier Transform and Convolution Algorithms
Springer Verlag (paperback!)

It is, IMHO, a superb book.

 Similar Threads Thread Thread Starter Forum Replies Last Post jasong Miscellaneous Math 5 2016-04-24 03:40 bearnol2 Information & Answers 7 2010-12-09 02:50 mgb Math 36 2009-11-07 15:59 mgb Math 5 2007-07-23 12:55 mfgoode Puzzles 18 2007-07-13 18:03

All times are UTC. The time now is 21:51.

Tue Jan 19 21:51:38 UTC 2021 up 47 days, 18:02, 0 users, load averages: 1.47, 1.39, 1.60