视频字幕
什麼是質數?質數是指一個大於1的自然數,除了1和它本身以外,沒有其他的正因數。例如2、3、5、7、11、13、17、19等都是質數。在數線上,我們可以標記出這些質數。
如何判斷一個數是否為質數?我們可以遵循以下步驟:首先,確認該數大於1;然後,嘗試用2到該數平方根之間的所有整數去除它;如果沒有一個數能夠整除它,那麼這個數就是質數。讓我們以13為例:13除以2等於6.5,有餘數;13除以3等於4.33,有餘數;13除以2到3之間的所有整數都不能整除13,因此13是一個質數。
埃拉托斯特尼篩法是一種古老而高效的篩選質數的方法。首先,我們列出2到n的所有整數。然後,我們標記出2的所有倍數,除了2本身。接著,我們標記出3的所有倍數,除了3本身。我們繼續這個過程,直到標記完√n以內的所有質數的倍數。最後,所有未被標記的數字就是質數。讓我們用這個方法找出30以內的所有質數。
質數有許多有趣的特性。除了2以外,所有的質數都是奇數。數學家已經證明質數的數量是無限的,但它們的分佈隨著數字增大而變得越來越稀疏。圖表顯示了質數計數函數π(n),它表示小於或等於n的質數數量。我們可以看到,隨著n的增加,曲線的增長速度變慢,表明質數變得更加稀少。另一個有趣的現象是孿生質數,即相差2的兩個質數,如(3,5)、(11,13)和(17,19)等。雖然孿生質數看起來也是無限的,但這仍然是一個未解決的數學猜想。
質數在現代科技中有著廣泛的應用,尤其是在密碼學和資訊安全領域。RSA加密算法是最著名的公鑰加密系統之一,它的安全性基於大質數分解的困難性。在RSA中,我們選擇兩個大質數p和q,計算它們的乘積n和歐拉函數φ(n),然後選擇一個公鑰e。加密過程是將明文M轉換為密文C,計算公式為C等於M的e次方除以n的餘數。由於大質數分解的計算複雜度,即使知道n和e,在不知道p和q的情況下,也很難破解密文。此外,質數還應用於哈希函數、偽隨機數生成和錯誤檢測等領域。