https://tcs.nju.edu.cn/wiki/api.php?action=feedcontributions&feedformat=atom&user=2001%3A14BA%3A8FB%3A4E01%3AD470%3AFA10%3AEA04%3A9E09TCS Wiki - User contributions [en]2026-05-26T20:33:43ZUser contributionsMediaWiki 1.45.3https://tcs.nju.edu.cn/wiki/index.php?title=Primality_test&diff=7544Primality test2017-07-24T14:10:56Z<p>2001:14BA:8FB:4E01:D470:FA10:EA04:9E09: capitalization</p>
<hr />
<div>A '''primality test''' is a method (or [[algorithm]]) to find out if a certain number is a [[prime number]]. [[Cryptography]] uses prime numbers, and needs to test if a certain number is prime. The official proof of a prime is through its primality certificate.<br />
<br />
==Simple methods==<br />
*[[Sieve of Eratosthenes]]: Determine if there is a number (between 2 and n, the number to test) that divides n, without a rest<br />
* Wilson's theorem (inefficient): <math>(p-1)!</math> evaluates to -1 mod p where p is the candidate prime number<br />
<br />
==Better methods==<br />
*[[Fermat's primality test]]<br />
*[[:en:Miller–Rabin_primality_test|Miller-Rabin primality test]]<br />
<br />
{{math-stub}}<br />
[[Category:Number theory]]<br />
.</div>2001:14BA:8FB:4E01:D470:FA10:EA04:9E09