很多常用的东西不知道放哪比较顺手，想起自己常写Q空间，就放这里好了，省的在机房那容易丢失。。。 这篇文章是我学习数论的开始，是转自网络上的，至于具体网址，倒是不记得了，希望作者看到后给我留言，我也好感谢一番。这篇文章使我对数论有个大概的理解，使我在以后的学习和到图书馆借书时都有个明确的目标。
有关数论的算法
数论一度被认为是漂亮的但却没什么大用处的纯数学学科。今天，有关数论的算法已被广泛使用，部分是因为基于大素数的密码系统的发明。这些系统的可行之处在于我们能够容易地求出大素数，而系统的可靠性在于大素数的积难以分解。下面我们将介绍了一些基本的数论知识和相关的算法，它们都是我们应用数论的基础。
输入的规模与算术运算的代价
因为我们将处理一些大整数，所以需要调整一下看法：如何看待输入规模和算术运算的代价？
在下面的讨论中，一个“大的输入”意味着输入包含“大的整数”，而不是意味着输入中包含“许多整数”(如排序算法中的情况)。因此，我们将根据表示输入数所要求的位数来衡量输入的规模，而不是仅根据输入中包含的整数个数来衡量。我们说，具有整数输入a1,a2,...,ak的算法是多项式时间算法仅当其运行时间表示是㏒a1,㏒a2,..,㏒ak的多项式，即它是转换为二进制的输入长度的多项式。 对于一般的算法来说，我们把基本算术运算 (乘法、除法或余数的计算)看作仅需一个单位时间的原语操作是很方便的。通过计算一个算法所执行的这种算术运算的次数，我们就可以以此为基础合理地估算出算法在计算机上的实际运行时间。但是，当输入值很大时基本操作也可能是费时的，因此衡量一个数论算法所要求的位操作的次数将是比较适宜的。在这种模型中，用普通的方法进行两个b位整数的乘法需要进行Q(b)次位操作。类似地，一个b位整数除以一个短整数的运算，或者求一个b位整数除以一个短整数所得的余数的运算，也可以用简单算法在Q(b2)的时间内完成。目前也有更快的算法，例如，关于两个b位整数相乘的一种简单分治算法的运行时间为Q(b ㏒3)，目前已知的最快算法的运行时间为Q(b ㏒b ㏒㏒b )。在实际应用中时，Q(b2)的算法常常是最好的算法，我们将用这个界作为我们分析的基础。
在后面的讨论中，我们在分析算法时一般既考虑算术运算的次数，也考虑它所要求的位操作的次数。 数论的基本知识 —— 介绍了数论的基本概念，例如可除性、模等价和唯一因子分解等。
最大公约数 —— 研究一个很古老的算法：关于计算两个整数的最大公因数的欧几里德算法。
模运算 —— 介绍了模运算的概念。 求解模线性方程 —— 讨论了一个已知数a的倍数模n所得到的集合，并说明如何利用欧儿里德算法来求出方程ax=b(modn)的所有解。
中国余数定理 —— 阐述了中国余数定理和一些应用。
元素的幂 —— 考察了已知数a的幂模n所得的结果，并阐述了一种已知a，b和n，可以有效地计算ab模 n的反复平方算法。这一运算是有效地进行素数测试的中心问题。
RSA公开密钥加密系统 —— 当今数论最有价值的应用领域。
素数的测试 —— 主要讨论了随机性素数测试，它可以用于有效地找出大素数，这是我们为RSA加密系统构造密钥的过程中所必须完成的基本任务。
整数的因子分解 —— 介绍了一种把小整数分解因子的简单而有效的启发性方法。令人惊奇的是人们往往希望分解因子是一个难于处理的问题，这也许是因为RSA系统的安全性取决于对大整数进行因子分解的困难程度吧