FFT 代码的功能 　　FFT 的目标是把一个 n-1 次多项式 P(x) = a_0+a_1x+a_2x^2+...+a_{n-1}x^{n-1} 　　根据其**系数表示（共 n 项）** 　　计算出该多项式在 **n 个不同 x 值处的赋值表示，**即 (x_1,P(x_1)),(x_2,P(x_2)),...,( ..

蝴蝶变换是一种怎样的（换位操作） 　　现假设 n = 2^k 是多项式的系数个数，即 x 的各幂次系数（从 0 次幂系数，即常数项开始）可记为： a_0,a_1,a_2,...a_{2^k-1} 　　按奇偶分组正好一半一半 　　直观起见，以 k = 3 为例，即： \begin{array}{c} a_0,a_1,a_ ..

多项式乘法 给定一个 n 次多项式 F(x) = a_{0}+a_{1}x+a_{2}x^{2}+...+a_{n}x^{n} 以及一个 m 次多项式 G(x) = b_{0}+b_{1}x+b_{2}x^{2}+...+b_{m}x^{m} 已知 H(x) = F(X) \cdot G(x) = c_{0}+c_{1 ..

问题 蒙哥马利乘法1时 \mod N \to \mod R，需要预先计算以下几个参数： \begin{array}{cl} r2 & = R^2 \mod N \\ N' & = -N^{-1} \mod R \end{array} N^{-1} \mod R 的求解，扩展欧几里得算法 这几个参数的求解 ..

6

辗转相除法 　　对正整数 a，b，求他们的最大公约数 gcd(a,b) 设 a>b，则gcd(a,b) = gcd(b,a \mod b) a \mod b = r \to a=bq + r \to r = a - bq , q = [\frac{a}{b}] 构造以下数列： r_0 = a r_1 = b r_ ..

欧拉函数 对于给定的正整数 x，在区间 [1,x] 内与 x 构成互质关系的整数的个数，叫做欧拉函数，记为\varphi(x) 例如，x = 5 时，构成互质关系的数有 4 个：1，2，3，4 所以：\varphi(5) = 4 计算\varphi(x) x = 1 时，\varphi(1) = 1 x 为质数时，\v ..

质数 质数又被称为素数 质数是指在大于 1 的自然数中，除了 1 和它本身外不能被其他自然数整除的数 0、1 既不是质素也不是合数 2 是最小的质数 质数有无穷多个（欧几里得反证法） 质数定律 前 x 个自然数中，质数的个数，记为\Pi(x) 例如：\Pi(2)=1，\Pi(3)=2，\Pi(10)=4 质数定理：\l ..

蒙哥马利乘法(上)-引言 　　蒙哥马利乘法(下)-只需要实现约减算法 蒙哥马利乘法 对于任意正整数 N，可选取 R > N 且 gcd(N,R)=1，通过蒙哥马利乘法可以把 mod N 的运算转换成 mod R 的运算 当把 mod N 转换为 mod R 时，a \mod N需要转换为：aR \mod N，aR ..