素数测试（primality test），理学-计算机科学技术-计算机科学理论-算法-随机算法，判定给定一个自然数N是否是素数的算法。素性测试不仅是一个重要的数学问题，在密码学中也有着广泛的应用。素性测试可以归约到整数分解问题，但又与整数分解不同，因为素性测试只需要判定给定自然数N是否为素数，而不用给出N的具体分解或任何一个非平凡因数。事实上已有素性测试的关于的多项式时间算法，但仍不知道整数分解问题能否在多项式时间内解决。素数判定简单而古老的方法是埃拉托斯特尼筛法，该方法从小到大遍历所有小于等于的素数，逐步剔除1∼N中的合数。如果N在某一步被剔除了，则说明N是合数，否则就是素数。另一种简单的方法是试除法，即遍历2到的自然数，逐个判断是否可以整除N。这两种方法的时间复杂度都是关于N的多项式而不是logN的多项式。在实践中素性测试往往采用的logN的多项式时间的随机算法，尽管这类方法有一定的概率出错。随机素性测试最简单的是基于费马小定理的测试，其思路是随机选择一些和N互素的自然数a并计算a𝑁−1modN，如果所有结果都是1，则N可能是素数，否则一定不是素数。