20040727, 19:36  #1 
Apr 2004
Blacksburg, VA
3^{2} Posts 
Integer FFT
Could anyone point me to some reference / explanation of an allinteger FFT? I have a basic understanding of the complexnumber 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 4point integer FFT using P = 13 (roots of unity being 7 and 11). Any assistance would be appreciated. Thanks! Nevarcds 
20040727, 20:21  #2 
Apr 2004
Blacksburg, VA
9_{16} 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 
20040728, 15:53  #3  
Nov 2003
16444_{8} Posts 
Quote:
For a complete description of how to do integer FFT's see: P. Montgomery & R. Silverman An FFT Extension to the P1 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. 

20040728, 16:31  #4 
"Nancy"
Aug 2002
Alexandria
100110100011_{2} Posts 
Two other sources that describe FFTs in general and mention NTTs are
Jörg Arndt's fxtbook Carey Bloodworth's page Alex 
20040728, 19:14  #5  
Nov 2003
16444_{8} Posts 
Quote:
H.J. Nussbaumer Fast Fourier Transform and Convolution Algorithms Springer Verlag (paperback!) It is, IMHO, a superb book. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
k*b^n+/c where b is an integer greater than 2 and c is an integer from 1 to b1  jasong  Miscellaneous Math  5  20160424 03:40 
Integer factorization?  bearnol2  Information & Answers  7  20101209 02:50 
Integer factorization with q < 2p  mgb  Math  36  20091107 15:59 
Integer Factorization 2  mgb  Math  5  20070723 12:55 
Always an integer.  mfgoode  Puzzles  18  20070713 18:03 