poj 1006 Biorhythms 线性同余式 中国剩余定理（CRT）

缘起

中国剩余定理（CRT）是数论中非常著名的一个定理. 因为最早见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知其数”问题 ，所以又叫孙子定理. 用现代数学的话来说, CRT解决了一元一次同余方程组
$$
(S)：\begin{cases}
x≡a_1 (mod \ m_1) \
x≡a_2 (mod \ m_2) \
…\
x≡a_n (mod \ m_n) \
\end{cases}
$$
其中，m1,…,mn 这n个整数两两互质.

Read More

poj 1811 Prime Test Pollard rho算法 分解素因数 快速幂

缘起

【1】中，我们写了一个算法求出一个正整数m的欧拉函数的同时，筛出了[1,m-1]中所有与m互质的正整数, 以及输出了m分解素因数的结果（真是全能的算法诶~） 但是那是对于m较小（1e6数量级）的情况效率尚可. 但是对于超大整数，使用该算法效率就堪忧了. 于是我学习 Pollard rho 分解超大整数（long long级别）的算法.

Read More

POJ 3641 Pseudoprime numbers Miller-Rabin素数测试

缘起

素性测试(即测试给定的数是否为素数)是近代密码学中的一个非常重要的课题.

而众所周知，测试一个数是不是素数，我们有O(sqrt(N))算法. 但是对于超大的n, 这个算法复杂度依旧很高. 所以我们来学习著名的Miller-Rabin素数测试算法。这是一种基于概率的算法,说白了，就是如果一个数能全部通过次数相当的Miller-Rabin测试的话，则我们以非常高的置信度判定它是质数.

Read More