素数

素数是指大於1的自然數，除了1與其本身之外，無法被其他自然數整除的數。 在數論中，素数構成了基本元素，因為所有大於1的自然數都可以唯一地寫成若干個素数的乘積，稱為因數分解。 歐幾里得在《幾何原本》中證明了素数有無窮多個，這一發現奠定了數論的基石。 現代密碼學廣泛利用素数的困難因數特性，如RSA加密演算法便是以兩個大素数的乘積作為公鑰，安全性基於短期內無法有效分解大整數的事實。 尋找大素数的常用方法包括埃拉托斯特尼篩法與米勒-拉賓檢測等算法，這些技術可在短時間內判斷一個數是否為素数。