假如Alice和Bob需要经过一个不可靠媒介传送一条消息, 他们大概会把这条消息加密, 而普遍使用的字母移位法(凯撒加密法)太容易被破解, 所以他们可能会考虑使用更加安全的加密法.
在上个世纪70年代被麻省理工学院的三位教授发明的RSA加密算法就是一个足够安全的加密法, 当今互联网的SSL安全连接协议的重要加密算法就包括了RSA加密算法. 连接到你的网上银行, 查看这个安全连接的证书, 证书上很可能写的就是“RSA加密”.
当然, RSA被广泛使用的原因还有一个, 那就是它的加密钥匙是公开的, 也就是说, 任何人都可以使用公开的密钥给消息加密, 却无法给刚加密的消息解密.
我们经常跟素数打交道, 我们知道素数的各种验证算法, 但是是否存在素数的生成算法呢?
事实上, 我们有许多可以生成素数的算法, 但是, 由于这些算法的效率极低, 我们基本上不会使用这些算法.
方法一: 素数编码
设 pn 是第n个素数, Sierpinski 先生曾经定义了这样一个常量:
若定义[x]为一取下整函数, 即[x]表示不大于x的最大整数. 那么我们有:
对于这一类方法, 当把相关常量计算出来时才有实际价值, 这似乎不太可能.
方法二: 利用 Wilson 原理
Willans 先生这样定义了函数 pi(x) :
那么, 对于大于2的任意整数n, 我们有:
这个方法虽然比前一个更具体, 但是, 其中涉及到了很大的数, 要应用到实际运算中还有一定的困难.
关于素数还有很多精彩的算法, 比如验证素数的 Miller-Rabin 测试, 以及应用素数性质的 RSA 加密算法, 但有关生成素数的真正可行的算法, 还有待我们继续去探究.
Read more…
去年就开始用 Mathematica 了, 在今年 Wolfram|Alpha 推出后, 我使用 Mathematica 的次数就越来越多了, 但有时候有的函数用起来还是不够得心应手, 所以前几天特意看了一下 Overview, 把初用者需要的重点记了下来, 难免会有不准确之处, 请各位大牛批评指正.
另外, 最近一直都很忙, 有几个话题一直没写完, 所以有段时间没有更新, 望各位见谅.
有的时候我们需求一种简介的表示数的方法，对于普通的有理数来说，普通的分数足够了。但是对于无理数，普通的分数可就无能为力了。我们有没有简介的方法来表示无理数呢？
连分数( continued fractions )就是这样的一种表示数的方法，连分数是形如下图的式子。
我们一般将连分数简写成
World of Goo 是一个由 2D BOY 推出的大型物理学&建筑学益智游戏，这是一个有着成千上万的叫做 Goo 的粘性小球的神奇世界，该游戏的乐趣在于如何把这些 Goo 搭建到水管口处，好让更多的 Goo 被水管收集。
前几天，在2009年全国信息学竞赛冬令营中，CCF 的杜秘书长提出了近期要取消 NOIp （全国信息学竞赛分区联赛）的一等奖保送资格，取而代之的是高考加分。有些人就不高兴了，我在冬令营的寝室里就经常听到众多选手的埋怨。接下来，CCF 的网站被黑了，大概也是这个原因。还有就是 cnBeta 里发的这一篇《论NOIP取消保送与CCF被黑——NOIP选手自白》。
网络流是图论中相当重要的一部分，也是计算机科学中比较难掌握的一类知识，在这我就给各位讲一讲网络流的有关知识。要注意的是，网络上，包括很多书籍中关于网络流的名词很容易被理解错，为了方便大家理解，我在这里对很多名词作了详尽解释。
