安全質數

出自維基百科,自由嘅百科全書
跳去: 定向搵嘢

安全質數係指滿足 2p + 1 形式嘅一種數,係以上呢一條式入面 p 都係質數。(相反,質數p 叫做謝爾曼質數。)

頭幾大個安全質數係:

571123475983107167179227263347359383467479503563587719839863887983101911871283130713191367143914871523161918231907

之所以叫佢哋做「安全」質數,係因為佢哋係加密算法當中嘅運用好容易令人理解:任何一個細過 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 嚟做結尾,咁樣佢就具有 10n+7 嘅形式。