如何快速验证一个超大的数为质数

给定随机任意一个超大的数，如何快速验证这个数为质数？

---

。。。。楼上说的有道理，但不是完全对。

如果要确切的判断一个大数是不是质数是NP难问题，当前的计算机架构不可解。所以可以从概率的角度上来判断一个大数是否为质数。也就是传说中非常神奇的米勒-拉宾检验:http://zh.wikipedia.org/wiki/%E7%B1%B3%E5%8B%92-%E6%8B%89%E5%AE%BE%E6%A3%80%E9%AA%8C
如wiki所说，通过一轮有 3/4 的概率为素数，所以可以跑 N 轮，这样这个数就有 1- (1/4) ^ n 的概率为素数，当你要求你的判断准度为 0.9999999999(10个9）也只要跑 log(0.0000000001) / log(0.25) = 17 次。

有问题请指出，谢谢

---

如果你看过 Algorithms by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani，里面素性检验的部分有关于检测大质数的方式
第一次看到简直毁我三观，概率检测？
Testing k = 100 values of a makes the probability of failure at most 2^−100, which is miniscule: far less, for instance, than the probability that a random cosmic ray will sabotage the computer during the computation!
用 Python 实现的话，大致是这样的：

def primality(n):
    """give a positive integer n, testing primality.
    With the power of Fermat's little theorem, we can use a probabilistic tests
    that it makes the probability of failure at most 2^(-100).
    """
    if n <= 102:
        for a in xrange(2, n):
            if pow(a, n - 1, n) != 1:
                return False
        return True
    else:
        for i in xrange(100):
            a = random.randint(2, n - 1)
            if pow(a, n - 1, n) != 1:
                return False
        return True

---

非确定性算法可以用米勒－拉宾
http://zh.wikipedia.org/wiki/%E7%B1%B3%E5%8B%92-%E6%8B%89%E5%AE%BE%E6%A3%80%E9%AA%8C

如果需要100%确定，可以用AKS算法
http://zh.wikipedia.org/wiki/AKS%E8%B3%AA%E6%95%B8%E6%B8%AC%E8%A9%A6