2L

a（模n）的阶数【整除】phi(n)
===（模n）阶数 m 的定义：最小的正幂使得a^m === 1 mod n
proof
首先设a的阶数为x，即a^x === 1 mod n
如果a和n互素，由Euler定理可得a^phi(n) === 1 mod n ---- （1）
由于x <= phi(n), 可以令 phi(n) = kx + r，其中0 <= r < x
代入（1）得到a^r === 1 mod n【矛盾：存在更小的阶数r使得定义成立】
所以r === 0
也就是 phi(n) === kx， 或者说 x 整除 phi(n)

欧拉函数的性质
============
phi(p) = p-1
phi(1) = 1
=========
phi(pq) = phi(p)*phi(q) pq 互质
phi(p^k) = p^k - p^ k-1 = (p-1) * p^ k-1
=========

safe prime
形如2p+1的素数，其中p也为素数。
例子：5、7、11、23、47
---------------------------------------------------
strong prime
如果q是strong prime的话，q+1和q-1都存在大的素因子
--------------------------------------------------
safe prime的safe是相对strong而言的
例如：对于safe prime 【q】=2p+1，【q-1】有一个素因子p
也就是说q满足strong prime的一部分条件
---------------------------------------------
待续

floyd cycle detection
x0 x1=f(x0) x2=f(f(x0)) ....
f(x) = (3x^2 + 7x + 5) % 97
x0 = 62、周期lambda=11、初始点mu=5
-----------------------------------
等价于需找 i >= mu 且 xi = xi+klambda
当i=klambda且i >= mu时，有 xklambda = x2klambda
于是有龟兔赛跑算法：t和h从x0出发，每次t走一步，h走两步，
当它们在环中相遇时，t走了v=klambda，h就走了2v，
------------------------------------
现在要求mu，则有xmu = xmu+klambda，
由于v=klambda，则有xmu = xmu+v，
所以让t回到x0，h保持原位xv，两者同时每次走一步直到相遇，
这样就求出mu。
-------------------------------------
有了mu再求lambda也简单了，直接根据xmu+lambda = xmu，
让t保持原位xmu，而h从xmu出发，走一圈直到相遇，
这样就求出lambda。
~~~wikipedia

离散对数
---------------------------
问题描述：
对于群G，阶数n，
给定a, b, 其中a^x = b，x未知
现在要求x
---------------------------
Shank's baby-step giant-step algorithm
由于群的阶数为n，那么0 <= x < n，(x=n时b=1，直接可以得到x)
设m = sqrt(n)
则将x写成x=im+j，其中0<= i < m, 0 <= j < m
（这样写是合理的，遍历所有i、j组合可以得到x=0,1,2,3,...n-1,...）
那么a^x = b就可以写成
a^(im+j) = b
====> b*(a^-m)^i = a^j
1）预先计算出所有的a^j（共m个）放入table中
2）迭代计算i=0 ... m-1，从表中查找结果
3）找到的话就输出x=im+j
复杂度O(sqrt(n))
----------------------------------
待续

Birthday problem
生日问题：（原问题）
-------------------------------
假设教室里有【23】人，一年有【365】天，问【至少2人】有【相同生日】的概率是多少？
-------------------------------
解：
事件A = 至少2人有相同生日
事件A' = 所有23人生日均不同
则P(A) = 1 - P(A')
事件E2 = 第2个人的生日和第1个人的生日不同
事件E3 = 第3个人的生日和第2、1个人的生日均不同 【可用条件概率表示这些事件】
....
再定义事件E1 = 第一个人有生日
则P(E1) = 1，
P(E2|E1) = 364/365 （给定第1个人有生日，求第2个人和第1个人生日不同的概率：和第1个人不同，剩下364种选择）
P(E3|E2,E1) = 363/365 （给定第2个人和第1个人生日不同，且第1个人有生日，求第3个人和第2、1个人生日不同的概率：和第2、1个人不同，剩下363种选择）
...
则P(A') = P(E1, E2, E3, ... ) = P(E1) * P(E2|E1) * P(E3|E2,E1) * ...
= 365/365 * 364/365 * 363/365 * ... * 343/365 【343 = 365 - 23 + 1】
= 365P23 / 365^23 （kPr表示k个数中选r个数的排列数的个数）
则P(A) = 1 - P(A') = 50.7%
---------------------------------
通常记p(n,d)，原问题中n=23，d=365【即在365个不同的数中选择23个数，其中至少2个数相同的概率】
_p(n,d) = dPn / d^n
p(n,d) = 1 - _p(n,d)
---------------------------------
近似值：
_p(n,d) ~= 1* e^(-1/365) * e^(-2/365) .... e^(-(n-1)/365)
而e^x通过泰勒级数展开得到【e^x = 1 + x + x^2/2 + ... 】
只保留1阶，得e^x = 1+x，
带入_p(n,d)得到
p(n,d) = 1 - _p(n,d) ~= 1 - e^( -n^2 / 2d )
---------------------------------
反转问题：
如果已知d，求最小的n使得p(n,d) 大于某个概率pi
【从365个数里最少选择多少数，才能使得选出来的数中至少有2个数相同的概率大于pi】
例如：要求使得p大于50%
则根据近似值1 - e ^ (-n^2 / 2d) = p(n,d) > 0.5。
=> 0.5 > e^ ( -n^2 / 2d )。
=> n > sqrt(ln 4) d^0.5 ~> 1.177d^0.5。
如果d=365，带入得到n ~> 22.49，所以n=23时，即365中选23个数至少有2个重复的概率大于0.5
---------------------------------

因式分解算法：
==========================
Pollard's rho algorithm
算法基于Floyd cycle-finding（龟兔算法）和birthday problem（生日问题）
-------------------
问题：
首先对于一个数N=pq（pq未知, p < sqrt(n)），求p。
用枚举的算法需要枚举domain=[2, sqrt(n)]，测试n%p == 0，
这是因为p|n，但是这样的p只有1个，就算从domain里随机选，其概率也是1/sqrt(n)。
--------------------
那么新的问题就是：
能否将这个概率提高？
可以观察p、2p、3p ... kp in [1,N] 这些数也有因子p，
假如只想找到这样的数 x 使得 p | gcd(x, n)
那么这样的x就多得多了（如上2p,3p ....）
但是我们并不知道p是多少，根本无法枚举这些数。
这里就用到了【生日问题】birthday paradox / birthday problem
------------------
假设从[1,N]这【n】个数中选出 【t】 个数x1,x2,x3 ..., xt，使得至少有2个数xi、xj，满足xi - xj = 0 mod p的概率大于50%，（即xi == xj mod p，或使得满足gcd(xi - xj, N) = p or q or != 1）
则根据生日问题t 至少是 1.177 * sqrt(n)。｛？？？？｝
see https_www_cs_colorado_edu/~srirams/courses/csci2824-spr14/pollardsRho_html
里面说是近似n^1/4??
有了t后还需要比对 t 这样t个数，判断xi - xj是不是符合。
这就就有新的问题：这t个数要同时存储于内存中。
--------------------
解决办法：Pollard's rho algorithm
我们可以每次只生成2个数x和y，使这两个数看起来是随机的。
设f是一个伪随机生成函数，
一般可以用f(x) = (x^2 + a) mod N，（a = 1,2 ...），
-----------------------
一般来说，随机生成函数给定一个初始值x0，可以生成序列
x0, x1, x2, ....，
对于该问题（找到两个数使得 GCD(| xi - xj | , N) ！= 1）来说，
我们首先设置选择随机数xi = x0、再选择一个随机数xj = f(x0)，然后计算判断GCD。
如果不是另xi = f(xi) == f(xj)，xj = f(xi) == f(f(xi))....
code:
xi = x0;
while ( ... exit cond ) {
xj = f(xi);
check gcd; break if found;
xi = xj;
}
注意：这里要把每次调用f想象成是int x = rand(); 所以才叫伪随机。
----------------------
新的问题：
1）可能由于初始值的选择，或者a的选择不恰当，
导致生成的序列里并没有对应的xi 或xj 的 解。
2）f序列可能会产生环，又因为【1）】，所以导致无限循环，程序无法终止。
-----------------------
Floyd cycle finding：
这里就又回到判圏问题，
用龟兔赛跑解决，xi = f(x0), xj = f(f(x0))，在循环体内
xi = f(xi), xj = f(f(xj));
如果找到了则直接退出，
如果相遇，则表示进入环，直接退出重新选择初始值或a。
------------------------
code
xi = x0;
xj = x0;
while (xi != xj) {
xi = f(x0);
xj = f(f(x0));
check gcd(|xi - xj|, N) > 1 ?; break if found;
}
not found ? reset x0 or a;
-----------------------------

欧拉函数性质~
n的欧拉函数phi(n)， 其代表的元素是指和n互质的元素，一共phi(n)个
-----------------------------------------------
性质：
求和（遍历d，d整除n）{ phi(d) } = n
注：d是n的【约数】
例子：n = 5，求和（d，d|5） ｛phi（d）｝ = phi(1) + phi(5) = 1 + 4 = 5 = n；
例子：n = 6，求和（d，d|6）｛phi（d）｝ = phi(1) + phi(2) + phi(3) + phi(6) = 1 + 1 + 2 + 2 = 6 = n；
注2：只有1、5 与6互质，所以phi(6) = 2，也可以用公式phi(6) = phi(2*3) = phi(2)*phi(3) = 1 * 2 = 2;
说明：
欧拉函数phi(n)的值 = 循环群Cn的生成元个数。
(循环群：Cn中的每个元素够可以写成a^k，其中a是固定元素)
（例如：Cn 为 mod 19的循环群，元素有1~19，生成元/本原根可以是2\3\...）
Cn中的每个元素gi都能生成Cn的一个子群Gi，也就是说gi是这个Gi的生成元。
不同子群不可能有相同的生成元（即一个生成元只能对应一个子群）。
Cn的所有子群有着Cd的形式（其中d|n）。
现在只要考虑子群Cd中生成元的个数，将其相加就得到n。
----------------------------------------------
用【莫比乌斯反转公式】可以得到另一个欧拉函数的表达式：
phi(n) = 求和（遍历d，d|n）{ d*mu(n/d) }
其中mu是【莫比乌斯函数】
=============================证明待续=======================
---------------------------------------------
【莫比乌斯函数】
mu(n) = { 1 if n = 1
(-1)^k if n = p1p2p3pk (无平方因数)
-1 if n 有大于1的平方因数，
性质：
求和（遍历d，d|n）{ mu(d) }
= 1 if n = 1
= 0 otherwise
---------------------------------------------
【莫比乌斯反转公式】
假设对于数论函数?? f(n) 和 F(n)，有
F(n) = 求和（遍历d，d|n）{ f(d) }
则将其莫比乌斯反转公式定义为：
f(n) = 求和（遍历d，d|n）{ mu(d) * F(n/d) }

http_math_stackexchange_com/questions/1757352/understanding-the-proof-of-m%C3%B6bius-inversion-formula
莫比乌斯反转公式证明：

第一个箭头成立是因为mu(k)可以先放到第二个求和里面，两个求和条件可以合并。第二个箭头同理？

Bézout's identity
貝祖等式、裴蜀等式
===================
对于给定整数 a 和 b，另 d = gcd(a, b)
那么，【ax + by = d 】中 未知数 x 和 y 一定有整数解。
另外
对于 ax + by 其中 x 和 y 是任意整数时
1、 ax + by | d。
2、d 是 所有 ax + by 取值中最小的正整数。
===================
证明：
------------
1）设S = ｛ax + by | x，y in Z｝，并另 d = as + bt 是 S 集合中最小的正整数。
假设 S 中的其他元素 n 不整除 d，那么 就一定存在 q，r，其中 r in （0，d），
使得 n = qd + r，
则 r = n - qd = ax + by - q（as + bt） = （x - qs）a + （y - qt）b，
也就是说 r 也是 S 中的一个元素，但是 r 必须小于 d，而 d 已经是 S 中最小的元素，
因此矛盾。
所以 S 中的 任意元素 一定 整除 其中 最小的正整数 d。
------------
2）现在证明 d = gcd（a，b）。
先取S 中的两个特殊元素，即另（x=1，y=0）和（x=0，y=1），
得到两个特殊元素 n1 = a，n2 = b，
由证明1）可知：
a | d 且 b | d，
现在假设c = gcd（a，b），那么就有
a = pc，b = qc，
d = as + bt = (pc)s + (qc)t = c(ps + qt)，
因此，如果 c 整除 a 和 b，那么 c 一定也 整除 d，
根据最大公约数（gcd）的定义，可知，
既然d能整除 a 和 b，又 c = gcd(a,b) 能整除 d，
那么 c 一定不大于 d，所以只能c = d，也就是 d 也是最大公约数。
--------------------------

modular e-th roots
现在已知a和e，考虑a^(1/e) mod p如何求解？
假设p是质数，
那么当gcd（e，p-1）=1时，可以求得。
=======================
how？
由于gcd（e，p-1）=1，则e*x + （p-1）*y = 1【贝祖等式】，
那么就是e*d == 1 mod (p-1) [这里用d 代替x]，
因此 d 是 e^-1 in Z_{p-1}，
而a^(1/e) == a^d mod p。
----------------------------------------
why？
考虑 a^(e*d) mod p = a^( k(p-1) + 1 ) mod p
= ( a^(p-1) )^k * a mod p
由欧拉定理a^phi(p) mod p = 1可得
a^(e*d) = a mod p，
两边同时取(1/e)次幂，得到
【 a^d == a^(1/e) mod p。其中d = e^-1 in Z_{p-1} 】
===============================

欧几里得算法
Euclidean algorithm
http_mathworld_wolfram_com/EuclideanAlgorithm.html
1、如果a=bq+r，则a和b的公约数 与 b和r的公约数相同。
2、rn是a和b的最大公约数。
q1=a\b，a=q1b+r1，r1=a-q1b；
q2=b\r1，b=q2r1+r2，r2=b-q2r1；
q3=r1\r2，r1=q3r2+r3，r3=r1-q3r2；
...
qn=r(n-2)\r(n-1)，r(n-2)=qnr(n-1)+rn，rn=r(n-2)-qnr(n-1)；
q(n+1)=r(n-1)\rn，r(n-1)=q(n+1)rn+0；