安全素数
(重定向自安全質數)
此条目没有列出任何参考或来源。 (2013年12月18日) |
安全素数是满足2p+1形式的一类数,在这里p也是素数。(相反地,素数p叫做索菲热尔曼素数。)开始的几个安全素数是:
由来
编辑之所以叫它们是“安全”素数,是因为它们在加密算法中的运用:某些约数分解的算法(如Pollard Rho算法)的计算时间部分取决于被分解数的素因数减去一的约数大小,而若被分解的数以一个安全素数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也是素数。开始的几个危险素数是: