mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2004-07-27, 19:36   #1
nevarcds
 
nevarcds's Avatar
 
Apr 2004
Blacksburg, VA

32 Posts
Default 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
nevarcds is offline   Reply With Quote
Old 2004-07-27, 20:21   #2
nevarcds
 
nevarcds's Avatar
 
Apr 2004
Blacksburg, VA

10012 Posts
Default 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
nevarcds is offline   Reply With Quote
Old 2004-07-28, 15:53   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

746010 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Old 2004-07-28, 16:31   #4
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

246710 Posts
Default

Two other sources that describe FFTs in general and mention NTTs are

Jörg Arndt's fxtbook
Carey Bloodworth's page

Alex
akruppa is offline   Reply With Quote
Old 2004-07-28, 19:14   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

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.
R.D. Silverman is offline   Reply With Quote
Reply

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 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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.