From e178e34317621a0bcfe649d74cdc6b44415226a4 Mon Sep 17 00:00:00 2001 From: Martin Mares Date: Tue, 1 Dec 2009 22:16:18 +0100 Subject: [PATCH] FFT: Vysvetleni multiplikativni grupy. --- 9-fft/9-fft.tex | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/9-fft/9-fft.tex b/9-fft/9-fft.tex index 53549b3..e0ff2be 100644 --- a/9-fft/9-fft.tex +++ b/9-fft/9-fft.tex @@ -385,7 +385,8 @@ a $2^0,2^1,\ldots,2^{2k-1}$ jsou navz $2k$-tá odmocnina z~jedné. To se nám ov¹em nehodí pro algoritmus FFT, jeliko¾ $2k$ bude málokdy mocnina dvojky. -Zachrání nás ov¹em algebraická vìta, která øíká, ¾e multiplikativní grupa +Zachrání nás ov¹em algebraická vìta, která øíká, ¾e multiplikativní grupa\foot{To je +mno¾ina v¹ech nenulových prvkù tìlesa s~operací násobení.} libovolného koneèného tìlesa je cyklická, tedy ¾e v¹echny nenulové prvky tìlesa lze zapsat jako mocniny nìjakého èísla~$g$ (generátoru). Napøíklad pro $p=2^{16}+1=65\,537$ je jedním takovým generátorem èíslo~$3$. Jeliko¾ mezi èísly $g^1,g^2,\ldots,g^{p-1}$ -- 2.39.2