快速判断一个数是否是素数（求方法）
如题，我所见过较快的方法是对于一个数a，依次除2－sqrt(a)，可是如果a非常大的话，运行时间会很长。有没有根据素数的某个性质快速判断的方法？请给出判断方法及简单的依据
作者: wenbodong 发布时间: 2011-06-11
效率高的不简单，
简单的效率不高。
简单的效率不高。
作者: yq_118 发布时间: 2011-06-11
非常大，就要用非常的方法了~~~，并且有还是基于概率的非确定性算法，这一般用在加密算法中，如RSA，一个基本的问题就是要找一个大的素数~~~
素性判别是数论中一个基本而古老的问题，对它的研究，不仅具有很大的理论意义，而且由于近代密码学的需要，更具有重要的应用价值。 对于大数的素性判别，目前Miller-Rabin算法应用最广泛，但这种算法只是一种概率算法，不过这种概率算法出错的概率是很小的。Maninadra Agrawal 教授和他的两个学生Neeraj Kayal,Nitin Saxena设计了一个被称为 AKS 的算法，它是第一个多项式的、确定的、无需其他条件的素性判断算法，它的速度较慢，适用于对加密可靠性要求高的场合。
素性判别是数论中一个基本而古老的问题，对它的研究，不仅具有很大的理论意义，而且由于近代密码学的需要，更具有重要的应用价值。 对于大数的素性判别，目前Miller-Rabin算法应用最广泛，但这种算法只是一种概率算法，不过这种概率算法出错的概率是很小的。Maninadra Agrawal 教授和他的两个学生Neeraj Kayal,Nitin Saxena设计了一个被称为 AKS 的算法，它是第一个多项式的、确定的、无需其他条件的素性判断算法，它的速度较慢，适用于对加密可靠性要求高的场合。
作者: chinayuppie 发布时间: 2011-06-11
引用 1 楼 yq_118 的回复:
效率高的不简单，
简单的效率不高。
效率高的不简单，
简单的效率不高。
我说的简单的依据是指简要给出依据，不是说这个依据要很简单
作者: wenbodong 发布时间: 2011-06-11