ＦＦＴ的历史和中国余数定理
FFT这种算法，包括其递归应用，是在1805年高斯发明的。
他用此法研究小行星--智行星和婚行星的轨道。但他的
著作没有被广泛认可（发表于他死后，且以近代拉丁文
发表）。高斯没有分析渐近计算时间。19世纪和20世纪
早期，陆续出现有限的FFT算法形式。FFT的广泛应用，
是在IBM公司的Cooley和普林斯顿的Tukey于1965年发表
的文章之后，重新发现计算机算法，且描述如何方便地用于
计算机。
 
据报道，Tukey是在肯尼迪总统科学咨询委员会讨论时提
出的方法，用于检测前苏联的核武器试验，利用地震仪，
在苏联之外的地方加以监测。这些传感器将产生地震时间
序列。然而，数据分析要求在计算DFT时要有快速算法。
因为与传感器的数量和时间长度的有关。这个任务对于谴责
核试验的根据极为关键。使得任何冒犯行动都将被监测到，
而不必访问苏联的设备就能办到。此次会议的其他参与者，
还有IBM公司的Garwin认为此方法是可行的。并联系Tukey
与Cooley接触，尽管Cooley并不知情。只是告知Cooley，必
须确定氦3的3D晶体自旋方向的周期。此后，Cooley与Tukey
发表了他们的相关著作，快速广泛采用，由于同时开发的
还有模拟--数字转换器，取样率能够达到300kHz。

高斯曾经描述同样的算法（虽然没有分析其渐近成本），
一直未实现，直到Cooley与Tukey的1965年的文章发表之后。
他们的文章被引用作为Good的著作的灵感，现在叫做质数
系数FFT 算法（PFA），尽管Good的算法本来看作等同于
Cooley-Tuley算法，很快意识到这是完全不同的算法（它仅
工作在相对互质的系数范围，且依赖中国余数定理，而不
支持Cooley-Tukey的任意范围）。
／／／／／／／／／／／／／／／／／／／／／
中国余数定理
一元线性同余方程组问题最早可见于中国南北朝时期（公元
5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物
不知数”问题，原文如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩
二。问物几何？

中国剩馀定理是数论中的一个关于一元线性同余方程组的定
理，说明了一元线性同余方程组有解的准则以及求解方法。
也称为孙子定理，古有“韩信点兵”、“孙子定理”、“求一术”
（宋 沈括）“鬼谷算”（宋 周密）、“隔墙算”（宋 周密）、
“剪管术”（宋 杨辉）、“秦王暗点兵”、“物不知数”之名。
宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》
对“物不知数”问题做出了完整系统的解答。明朝数学家程大位
将解法编成易于上口的《孙子歌诀》：
三人同行七十希，五树梅花廿一支，七子团圆正半月，除百
零五使得知
http://blog.sina.com.cn/s/blog_8dc294230101dofw.html
/////////////////////////////////////////////////
1801年高斯的著作中曾经提到过中国余数定理。见图。

孙子算经原始公式