素数问题是一个使很多数学家着迷的问题。素数就是一个除了1和它自身以外不能被其它数整除的数。素数的一个基本问题是如何有效地确定一个数是否是一个素数,即素性测试问题。素性测试问题不仅在数学上是一个有挑战性的问题,而且在实际应用中也是非常重要的。在现代密码系统中,大素数的判别和寻找对一些加密系统的建立起着关键作用。很多公钥密码算法都用到素数,特别是160位(二进制)以上的大素数。RSA的公共模数就是两个512位以上的大素数的乘积;基于有限域PF上离散对数的公钥密码体制,其中素数p要求在512位以上;基于椭圆曲线离散对数的公钥密码体制(ECC)中,一般要求基点的阶是一个160位以上的大整数,且是一个素数。由此可见对大数进行的素性判断的重要性。判定一个整数是否是素数,最为简单的想法是直接利用素数的定义,用比要判断的整数小的素数去一一试除,如果能整除被检测的数的话,那就能确定无疑为合数了,但是对于大素数来说,由于计算量太大,根本无法实现以用于具体应用。所以科学家们根据素数判断的理论发明了许多新的算法,提高了判断一个大数是否是一个大素数的效率。Eratosthenes筛法是对于所有素数都有效的最古老的算法,然而它的时间复杂性是输入规模的幂指数,因此在实际中使用它是不合适的。17世纪的Fermat小定理是一些有效素性测试算法的起点,但其逆定理是不满足的。许多科学家在费马小定理的基础上进行研究发明了很多新的素数检测方法,但是这些算法大部分都是概率性的,比如说Miller-Rabin算法和Solovay-Strassen概率素数测试法。直2002年,印度的三位科学家发明了确定性的素数检测算法AKS算法。但是研究表明AKS算法的时间复杂度和空间复杂度并不能满足时间中的需要。随着椭圆曲线算法的研究的开展,许多科学家又发明了利用椭圆曲线算法进行素性检测的方法,并且成为今年来素性检测领域里的一个重要方向。本文也对2中基本的椭圆曲线素性检测算法做了简单的分析。本文从素性检测算法的基本理论入手,对素性将测算法做一个全面的介绍,对大部分的素性检测算法进行了分析,其中着重对实践中常用的Miller-Rabin算法进行了分析,并且对Miller-Rabin算法做了一定的优化,使Miller-Rabin算法的效率提高了一倍,生成1024位素数的效率提升至,在1.5G的计算机上每1.5秒生成一个,并且给出了Miller-Rabin算法的算法流程图和部分关键代码的实现。