mersenneforum.org > Math Integer FFT
 User Name Remember Me? Password
 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 916 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

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

164448 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 05:04.

Thu Jan 20 05:04:18 UTC 2022 up 180 days, 23:33, 1 user, load averages: 1.93, 1.52, 1.48

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔