安全素数

(重定向自安全質數

安全素数是满足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