跳至內容

安全素數

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

安全素數是滿足2p+1形式的一類數,在這裡p也是素數。(相反地,素數p叫做索菲熱爾曼素數。)開始的幾個安全素數是:

5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907 (OEIS數列A005385

由來

之所以叫它們是「安全」素數,是因為它們在加密算法中的運用:某些因數分解的演算法(如Pollard Rho演算法英語Pollard's rho algorithm)的計算時間部份取決於被分解數的質因數減去一的因數大小,而若被分解的數以一個安全質數2p+1作為因數,由於此質數減去一有一個大質數p做為因數,計算時間將會變多。但是很容易理解任何一個小於1050的素數都不是真正安全的,因為對於任何一個有着合適算法的現代計算機都能在適當的時間內判斷出它的素性,但是這些小一點的安全素數在加密算法原理的教學中仍然還是很有用的。不過現在對於安全素數還沒有像對費馬素數梅森素數一樣的特別的素性檢測方法。

除了5,沒有既是費馬素數又是安全素數的數了。一個給定的費馬素數F,一個小小的運算就可以證明(F-1)/2會是2的

除了7,沒有既是梅森素數又是安全素數的數了。這個證明有點麻煩,不過仍然在基礎代數的範疇內:p必須是素數,2p-1才有可能是素數,那麼((2p - 1) - 1)/2 = 2p - 1 - 1是個梅森數,因此只有當p=3時p-1才是素數,此時23-1=7。

第一類坎寧安鏈中所有的數除了最後一項都是索菲熱爾曼素數,除了第一項都是安全素數。以7結尾的安全質數必定會出現在坎寧安鏈的尾端,因為其兩倍加一將會以5結尾,而這是5的倍數。

危險素數

所有不是安全素數的素數都稱為「危險素數」或「不安全素數」,也就是說,所有無法滿足2p+1形式的一類素數都是危險素數,在這裡p也是素數。開始的幾個危險素數是:

2, 3, 13, 17, 19, 29, 31, 37, 41, 43, 53, 61, 67, 71, 73, 79, 89, 97, 101, 103, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 173, 181, 191, 193, 197, 199, 211, 223, 229, 233, 239, 241, 251, 257, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337OEIS數列A059456