安全系统中有趣的不确定性

这个学期上的加密理论是一门挺好玩儿的课，一半原因是Bergeman老头儿，一半原因是本身也很有意思，了解了很多以前不知道的或者一知半解的理论。其中一个好玩的就是不确定性。算法一般有确定性和不确定性两种。确定性算法获得全部正确的解，而不确定算法（或者称为概率算法，Probabilistic algorithm）以一定的概率获得正确的解。换句话说，不确定算法不一定每次都能获得正确的解。匪夷所思吧。为啥非要用概率算法呢？ 如果确定性算法算的太慢，或者根本就没有确定性算法，就不得不用概率算法了。那，这个概率算法咋用呢？用Bergeman老头儿的话来说，就跟钓鱼一样。甩钩下去，钓上来一条鱼，如果是大鱼（正确的解），就留下。如果是小鱼（不正确的解），就扔回去重钓。只要钓上大鱼的几率足够大（一般大于1/2就够了），这个算法就能有效的工作。

比如大素数就是用这种概率算法计算的。现代安全系统基于素数，通常需要一个很大的素数（比如几百个比特的）。那怎么得到一个大素数？没有一个确定性算法能够很快的算出小于N的所有素数，但是对于一个整数，我们可以很快的判定它是不是素数。所以目前的算法就是随机的取一个小于N的数，如果判断是素数（大鱼），就用它，如果不是，那就继续取一个随机数直到取到素数为止。幸好素数足够多。
haha