荔园在线
荔园之美，在春之萌芽，在夏之绽放，在秋之收获，在冬之沉淀
[回到开始]
[上一篇][下一篇]
发信人: kaman (天外飞仙), 信区: ACMICPC
标 题: 数论算法指南
发信站: 荔园晨风BBS站 (Fri Jul 23 10:59:11 2004), 站内信件
有关数论的算法
数论一度被认为是漂亮的但却没什么大用处的纯数学学科。今天，有关数论的算法
已被广泛使用，部分是因为基于大素数的密码系统的发明。这些系统的可行之处在
于我们能够容易地求出大素数，而系统的可靠性在于大素数的积难以分解。下面我
们将介绍了一些基本的数论知识和相关的算法，它们都是我们应用数论的基础。
输入的规模与算术运算的代价
因为我们将处理一些大整数，所以需要调整一下看法：如何看待输入规模和算术运
算的代价？
在下面的讨论中，一个“大的输入”意味着输入包含“大的整数”，而不是意味着
输入中包含“许多整数”(如排序算法中的情况)。因此，我们将根据表示输入数所
要求的位数来衡量输入的规模，而不是仅根据输入中包含的整数个数来衡量。我们
说，具有整数输入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系
统的安全性取决于对大整数进行因子分解的困难程度吧。
--
Long long ago,there is a hero stand at the edge of the land,a sword in
hand.......
︵～` ╭) ▁▁
︸ヾ) (╯ ▕天外▏
ゞ7( ︵ )) ▕飞仙▏
╰ ︶へ︶╯ ▔▔
ヅ╯ ジ〉
※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.14.107]
[回到开始]
[上一篇][下一篇]
荔园在线首页 友情链接：深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店