1. 分治（Divide and Conquer）

分治算法是算法的重要分支之一，主要思想就是：

1. 自上而下把问题划分成几个小的子问题，每个子问题与原问题类型相同。
2. 自下而上递归地解决子问题。
3. 把子问题的解适当地组合成原问题的解。

虽然分治法的核心结构是递归，但也不一定非得用函数递归来实现；递归法便于分析问题，迭代法可能却更为高效 。

1. Divisible?

$4^{1536}-9^{4824}$是否能被35整除？

$35=5\times 7$，根据费马小定理：$a^{5-1}\equiv 1 (\mod 5)$，$a^{7-1}\equiv 1(\mod 7)$，由于5和7都是素数，易得：$a^{(5-1)(7-1)}\equiv 1(\mod 35)$，即$a^{24}\equiv 1(\mod 35),1\leq a<35$。因此$4^{1536}-9^{4824}\equiv 4^{24\cdot 64}-9^{24\cdot 201}\equiv 1-1(\mod 35)$，故$4^{1536}-9^{4824}$能被35整除。

1. 哈希表

数论算法在哈希函数的设计方面也有应用。假设在编写网络服务应用时，我们需要维护一个动态变化的客户的IPv4地址的list，如何快速地查询某个IP呢？一个最快的方法是建立大小为$2^{32}$的array，以IP作为index。虽然很快，但是会非常浪费内存，大多数内存可能都是空的。还有一个方法是使用链表，但是查询速度很慢，与客户个数成正比。使用哈希的方法能使占用内存的大小与客户数量成正比，同时获得较快的查询速度。

1. 密码学简介

数论算法应用最广泛的领域之一就是密码学，密码学也是网络安全的重要研究分支。密码学研究的主要问题可以用以下情境描述：Alice和Bob二人想要进行私密通信，但是Eve想要偷听他们的私密通信。Alice和Bob为了保证私密性，他们决定对消息进行加密和解密（编码和译码）：

1. 费马素性测试-1

上一章提到过两数互质的问题，质数（素数）一直以来都是数论中的重点内容。一个基本问题就是：如何判断一个数是否为素数？最容易想到的方法：将这个数做质因数分解，若因数只有1和它本身，则为素数，但是质因数分解效率很低；另一种方法是，依次判断是否有比它小的数整除它，本质上还是质因数分解。下面要介绍的一种高效的素性测试方法，基于一个重要的定理：