apfloat网站的Number theoretic transforms介绍

无心人

http://www.apfloat.org/ntt.html Number theoretic transforms Please e-mail all corrections to Mikko.Tommila@apfloat.org Last updated: March 20th, 1997 -------------------------------------------------------------------------------- In order to understand any of the following, you should be somewhat familiar with the Fourier Transform and some elementary number theory (like modulo arithmetic). I wrote this text simply because I was so glad when I understood what this is all about. I will not take any responsibility for any trouble caused by the errors that this document might contain. Basically, a number theoretic transform is a Fourier transform. Now, suppose you have a normal discrete Fourier transform. You do it in matrix form by multiplicating your data with a Fourier matrix (for example n=4): [ 1 1 1 1 ] [ 1 w w^2 w^3 ] [ 1 w^2 w^4 w^6 ] [ 1 w^3 w^6 w^9 ] The unit w is exp(2pi i / n). Now everything a number theoretic transform is all about is that w^n=1. But instead of using a complex number w you do everything in some other number field where w^n=1. Now integers modulo a prime p form a number field. From elementary number theory we know, that for all integers a, when p is prime a^(p-1)=1 (mod p) (From now on we just might suppose that the modulus p is prime). Then there exists a primitive root r, that is, when x goes from 1 to p-1, then r^x (mod p) goes through all the numbers 1...(p-1) in some order. Now, we want w^n=1 (mod p) (here n is our transform length). So we find (not too difficult with, say, Mathematica) a prime of the form p=k*n+1. So p-1=k*n. Now find the primitive root r (with Mathematica). To know more about primitive roots go to my primitive roots page. We calculate (when p=k*n+1) w=r^k (mod p) That's it. Now w^n=r^(k*n)=r^(p-1)=1 (mod p). And w^n=1 but w^m != 1 if m < n. So it works. The matrix can be factored to do a fast number theoretic transform just like a Fourier matrix can be factored. Just take any fft code and change the complex numbers to integers modulo p, and use the w found above. Unlike the "normal" Fourier transform, a number theoretic transform does not transform the data to any "physically meaningful" space, like a Fourier transform transforms the "time" data to "frequency" space. So one is mostly interested in doing convolutions efficiently. This can be used to multiply very big numbers efficiently, which originally was the author's goal. Number theoretic transforms are actually very simple. I wrote a program in Mathematica to demonstrate multiple precision arithmetic with ntts: numberth.m In order to use the above program with Mathematica you need to load first <http://www.jjj.de David H. Bailey: http://www.nersc.gov/~dhbailey/dhbpapers/index.html -------------------------------------------------------------------------------- Some books: Henri J. Nussbaumer: Fast Fourier Transform and Convolution Algorithms, 2nd edition, Springer-Verlag 1982 E. Oran Brigham: The Fast Fourier Transform, Prentice-Hall 1974 Kenneth H. Rosen: Elementary Number Theory and Its Applications, 3rd edition, Addison-Wesley 1993 D. Knuth: The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, Addison-Wesley 1981 -------------------------------------------------------------------------------- Go to the apfloat home page.

无心人

谈到了基选择的问题 也提到了最大可卷积限制 呵呵 似乎是小于等于2^27*32字=2^31比特