![]() |
![]() |
#1 |
Apr 2004
Blacksburg, VA
32 Posts |
![]()
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 |
![]() |
![]() |
![]() |
#2 |
Apr 2004
Blacksburg, VA
10012 Posts |
![]()
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 |
![]() |
![]() |
![]() |
#3 | |
Nov 2003
746010 Posts |
![]() Quote:
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. |
|
![]() |
![]() |
![]() |
#4 |
"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 |
![]() |
![]() |
![]() |
#5 | |
Nov 2003
22×5×373 Posts |
![]() Quote:
H.J. Nussbaumer Fast Fourier Transform and Convolution Algorithms Springer Verlag (paperback!) It is, IMHO, a superb book. |
|
![]() |
![]() |
![]() |
Thread Tools | |
![]() |
||||
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 b-1 | jasong | Miscellaneous Math | 5 | 2016-04-24 03:40 |
Integer factorization? | bearnol2 | Information & Answers | 7 | 2010-12-09 02:50 |
Integer factorization with q < 2p | mgb | Math | 36 | 2009-11-07 15:59 |
Integer Factorization 2 | mgb | Math | 5 | 2007-07-23 12:55 |
Always an integer. | mfgoode | Puzzles | 18 | 2007-07-13 18:03 |