强素数

维基百科,自由的百科全书
跳转至: 导航搜索

数学中, 强素数是指具有某些特性的素数。强素数的定义在密码学数论中是不同的(但有一定的关联)。

密码学中的定义[编辑]

密码学中,一个素数p在满足下列条件时被称为强素数 [1]

  1. p 必须是很大的数。
  2. p-1 有很大的质因数。也就是说,对于某个整数a_1以及大素数q_1,我们有p = a_1 q_1 + 1
  3. q_1-1 有很大的质因数。也就是说,对于某个整数a_2以及大素数q_2,我们有q_1 = a_2 q_2 + 1
  4. p+1 有很大的质因数。也就是说,对于某个整数a_3以及大素数q_3,我们有p = a_3 q_3 - 1

有时,当一个素数只满足上面一部分条件的时候,我们也称它是强素数。而有的时候,我们则要求加入更多的条件。例如,我们可以要求a_1 = 2,或者a_2 = 2。从这个角度上来说,很大的安全素数可以看作是强素数的一种。

数论上的定义[编辑]

数论中,如果一个素数p比它相邻的两个素数的平均数要大,则我们称p强素数。 换句话说,一个强素数是这样的素数:和它前面的相邻素数比较,它总是更靠近在它后面的下一个素数。 或者用代数的语言来说,对于素数p_nn是它在所有素数的有序集合中的索引),则p_n为强素数当且仅当p_n > {{p_{n - 1} + p_{n + 1}} \over 2}。 下面列出最小的几个强素数:

11, 17, 29, 37, 41, 59, 67, 71, 79, 97, 101, 107, 127, 137, 149, 163, 179, 191, 197, 223, 227, 239, 251, 269, 277, 281, 307, 311, 331, 347, 367, 379, 397, 419, 431, 439, 457, 461, 479, 487, 499OEIS中的数列A051634

例如,17是第7个素数。而第6个和第8个素数分别是13和19,加起来是32,平均值是16,小于17。所以17是一个强素数。

在一对孪生素数p, p+2)里,当p>5时,p总是强素数。这是因为p-2必能被3整除,所以不可能是素数。

有些素数既符合密码学的强素数定义也符合数论上的强素数定义。比方说, 439351292910452432574786963588089477522344331 就是一个数论意义上的强素数,因为与它相邻的两的素数的平均数比它小62。如果没有电脑的话,这个数也可以是一个密码学意义上的强素数。这是因为 439351292910452432574786963588089477522344330 有一个大质因数 1747822896920092227343 (而这个质因数减去1后又有一个大质因数 1683837087591611009 ),而 439351292910452432574786963588089477522344332 也有一个大质因数 864608136454559457049 (而它减去1后也有大质因数 105646155480762397 )。 就算是用比较先进的算法,用纸和笔也很难分解这样大的数。但对于现代的计算机代数系统来说,分解这样的数是很容易的事。所以真正的密码学意义上的强素数比前例中的这些数还要大很多。

强素数在密码学上的应用[编辑]

基于整数分解的密码系统[编辑]

有人建议在RSA密码系统的钥匙生成算法中,模数n应该是两个强素数之积。这样,如果用Pollard的p-1质因数分解算法来分解n = pq就会变得不可行。由于这个原因,ANSI X.31标准要求,在为基于RSA的数字签名算法生成钥匙的时候,必须用强素数。但是,强素数并不能保证n在用其它更新的算法来分解时也一样难以分解。例如Lenstra的椭圆分解法英语Lenstra elliptic curve factorization普通数域筛选法。考虑到为了生成强素数需要用去更多的时间,RSA Security英语RSA Security目前并不建议在钥匙生成算法中使用强素数。Rivest和Silverman [1]也给出了类似但更细致的论述。

基于离散对数的密码系统[编辑]

1978年由 Stephen Pohlig 和 Martin Hellman 证明,如果 p-1 的所有质因数都小于 log^c p,那么解决模数p离散对数 问题就属于 P问题。所以,对于基于离散对数的密码系统,比如数字签名算法(即DSA),我们就要求 p-1 至少要有一个大质因数。

其它[编辑]

要注意的是,判断一个伪素数是否是强伪素数时,我们看的是它除以某个基数的幂之后的余数,而不是看它和相邻的伪素数的平均数那个较大。

在数论中,如果一个素数刚好等于其相邻素数的平均数,那么我们把这个素数叫做均衡素数。如果它比平均数小,则叫做弱素数

参考资料[编辑]

  1. ^ 1.0 1.1 Ron Rivest and Robert Silverman, Are 'Strong' Primes Needed for RSA?, Cryptology ePrint Archive: Report 2001/007. http://eprint.iacr.org/2001/007

外部链接[编辑]