Talk:Number-theoretic transform
From Wikipedia, the free encyclopedia
The modulus in a Number Theoretic Transfer doesn't necessarily have to be prime. It makes many things simpler if the modulus is prime, but it's possible to have an NTT also with a composite modulus. The requirements for the modulus are (when n is the transform length):
- An n:th root of unity exists
- The multiplicative inverse of n exists
Also, what may be of interest for practical applications of the NTT, is that if the transform length is highly composite (e.g. 2n), the NTT can be calculated using a Fast Number Theoretic Transform (sometimes abbreviated FNT), with an algorithm similar to the Fast Fourier transform.
Mikko Tommila 18:19, 1 Apr 2005 (UTC)
Contents |
[edit] Works for any finite field
It should work for any finite field. w must just be a generator or something. -- Nic Roets 13:54, 20 July 2005 (UTC)
- Yes, it should work for any finite field of order q, provided that n|q-1. In this case ω must be a primitive nth root of unity, i.e. n must be the least natural number such that ωn = 1. But you need to raise your "generator" to the
power to get the necessary primitive root.
- I don't think it will work for a composite modulus as described above, though. You need a real field, with a multiplicative inverse for all elements except zero. (I actually tried to do Schönhage multiplication that way once, by the way. It didn't work.) -- 130.94.162.64 09:27, 30 November 2005 (UTC)
- For example the Fermat Number Transform has some practical applications, and the modulus can be composite. Just search Google for Fermat Number Transform. For example, somebody is apparently doing Linear Predictive Speech Coding Using Fermat Number Transform. -- Mikko Tommila 21:13, 6 September 2006 (UTC)
[edit] Gauss sum
This article appears to be about the Gauss sum, under a strange-sounding title. Are there any actual mathematicians who actually call it "NTT" instead of "Gauss sum"? Anyway, I think these articles should be merged. linas 06:39, 9 February 2006 (UTC)
- Never mind. I got confused. linas 04:22, 10 February 2006 (UTC)
[edit] Rabbit ears
Why is the term primitive root held in rabbit ears in the definition paragraph? omega is just a primitive root of unity.
Another q. When discussing the advatage for integer convolutions, this sentense seems odd:
- "the NTT has no round-off because it deals purely with integers that can be exactly represented, although arithmetic overflow is still a possibility."
How is arithmentic overflow still an option? except for an implementation bug? *anything* is possible as an implementation bug, if ops are done modulu, or in the field, everything should be kept alright... can anyone expand on this? am I missing something? Oyd11 01:23, 27 July 2006 (UTC)
- I suppose arithmetic overflow is only meaningful when doing a convolution using a NTT. In the result of the convolution, the result elements (being sums of the numbers in the original sequences) can be larger than the modulus, effectively resulting in overflow. For example, if the numbers in the sequences to be convolved are in the range 0 ... 1000 and the transform length is 1000 then your modulus should be more than 1000 * 1000 * 1000 = 1000000000 to avoid overflow. Alternatively, you can calculate the convolution using two or three different moduli, and get the final result using the Chinese remainder theorem. -- Mikko Tommila 21:31, 6 September 2006 (UTC)
[edit] Number of primitive roots
The article says "there should be lots of ω which fit this condition": this is easily seen as follows: since the non-zero integers modulo p form a cyclic group under multiplication modulo p, there are exactly φ(p − 1) elements whose order is exactly p − 1, that is, which are primitive modulo p. If you pick any one of these, say a, and any integer k from 1 to p − 1 which is relatively prime to p − 1 (that is, has no common factor with p − 1), then ak (mod p) will also be a primitive root. Hence there are indeed lots of primitive roots around: the totient function φ(m) has an easy asymptotic lower bound of
meγ / loglog(m).
The subgroup of those elements whose order divides </math>n</math> is also cyclic, and the number of primitive roots there is again φ(n): pick any one of them, say b and as k ranges over those integers coprime to 
, bk (mod p) will give the primitive nth roots of unity (mod p).
If a is primitive (mod p), then as noted above, a primitive nth root of unity mod p is given by a(p − 1) / n. The others will be generated by all kth powers of this root, where k and n are relatively prime, and 
. From the lower bound for the totient function, we see that there will be at least around n / loglog(n) roots, and potentially as many as constant times n. Furthermore, they can be easily found, providing (p − 1) can be factored: find a primitive element (mod p) at random (that is, an element of order (p − 1) (mod p): on average you will have to examine about loglog(n) elements before you find a primitive one) and just raise it to the power (p − 1) / n.
I think that the point about working over a prime field rather than a prime power field is that the computation embeds naturally as exact computation over the integers (you can do prime power fields exactly, but the embedding is not just modular arithmetic). If you take care with all your computations, I don't think that you ever need do a side-computation involving numbers larger than p2. Hence if your integer datatype has maximum size bigger than p2 then it really is exact (mod p). To obtain results that are correct over the integers, one can obtain apriori upper bounds on the size of the integers resulting from the convolution, and then either choose primes that are sufficiently large, or work modulo several smaller primes, whose product is large enough, and use the Chinese Remainder Theorem. Note, however, that it is better in this case to use residues in the ranges − [(p − 1) / 2,(p − 1) / 2] rather than least non-negative residues (mod p), since this enables us to identify negative numbers as well as positive ones.
Calkin 20:40, 24 November 2006 (UTC)
[edit] missing assumptions or inconsistent notation?
The article is missing something and therefore hard to understand for someone new in this field. For example, in section "Definition":
< ... ω is a "primitive root" of p, a number where the lowest positive integer n such that ω^n=1 is n=p-1. There should be plenty of ω which fit this condition. Note that both and ω^ξ raised to the power of n are equal to 1 (mod p), all lesser positive powers not equal to 1 ...>
The last statment about "all lesser positive powers (of ω^ξ) not equal to 1" would be wrong for ξ = p-1 because all lesser positive powers would be equal to 1, according to previous definition of "primitive root".
Could anyone fix this? Or explain this section in less convoluted way.
Thank you in advance, DR —Preceding unsigned comment added by 12.30.32.10 (talk) 19:11, 30 April 2008 (UTC)
