安全質數

安全質數

安全質數也稱為安全素數是滿足2p+1形式的一類數,在這裡p也是素數。相反地,素數p叫做索菲熱爾曼素數。

拼音

ān quán zhì shù

英文解釋

safe prime

釋義

安全素數(安全質數)是滿足2p+1形式的一類數,在這裡p也應是素數。(相反地,素數p叫做索菲熱爾曼素數。)詳細介紹之所以叫它們是“安全”素數,是因為它們在加密算法中的運用:某些因子分解的算法(如Pollard P-1算法)的計算時間的部份取決於被分解數的質因子減去一的因子大小,而若被分解的數以一個安全素數2p+1作為因子,由於此素數減去一有一個大素數p做為因子,計算時間將會變多。但是很容易理解任何一個小於10的素數都不是真正安全的,因為對於任何一個有著合適算法的現代計算機都能在適當的時間內判斷出它的素性,但是這一些小一點的安全素數在加密算法原理的教學中仍然還是很有用的。

簡介

安全素數又稱為安全質數,為滿足2p+1形式的一類數,這裡p也應是素數。(相反,素數p稱之為索菲熱爾曼素數。)

詳細介紹

安全質數在加密算法中的運用:一些因子分解的算法(象PollardRho算法)的計算時間部份取決於被分解數的質因子減去一的因子大小,假如被分解的數以一個安全素數2 p+1作為因子,因為此素數減去一有一個大素數 p做為因子,計算時間會變多。可是很容易理解任何一個小於10的素數都不是真正安全的,對於任何一個有著合適算法的現代計算機都能在適當的時間內判斷出它的素性,可是這些小一點的安全素數在加密算法原理的教學中仍然還是很有用的。對於安全素數還沒有像對費馬素數與梅森素數一樣的特別的素性檢測方法。

開始的幾個安全素數是:

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

之所以叫它們是“安全”素數,是因為它們在加密算法中的運用,很容易理解:任何一個小於1050的素數都不是真正安全的,對於任何一個有著合適算法的現代計算機都可以在適當的時間內判斷出它的素性,但是這些小一點的安全素數在加密算法原理的教學中仍然還是很有用的。 不過對於安全素數還沒有像對費馬素數與梅森素數一樣的特別的素性檢測方法。

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

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

第一類坎寧安鏈中所有的數除了最後一項都是索菲熱爾曼素數,除了第一項都是安全素數,如果安全素數是以7結尾,那么它具有10n+7的形式。

相關詞條

相關搜尋

熱門詞條

聯絡我們