计算机科学

首页 > 计算机科学

半素数

2018-09-10 11:51:56

数学中,两个素数的乘积所得的自然数我们称之为半素数(也叫双素数,二次殆素数)。开始的几个半素数是4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... (OEIS中的数列A001358)它们包含1及自己在内合共有3或4个约数。[1]

目录

  • 1 例子与种类
  • 2 性质
  • 3 应用
  • 4 另见
  • 5 参考资料与附注
  • 6 外部链接

例子与种类

比100小的半素数有:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, and 95 (OEIS中的数列A001358).

不是平方数的半素数被称为离散、特异或非平方半素数,包括:

6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, ... (OEIS中的数列A006881)

半素数是次殆素数(有且仅有个质因数的数)。 但是有些数列将“半素数”解释为一种更加宽泛的数,即最多有两个质因数的数[2],包括:

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 46, 47, 49, ... (OEIS中的数列A037143)

性质

除了自己本身外,半素数没有其他合数因数。[3]例如,1、2、13及26是半素数26的因数,其中只有26是合数。

对于非平方半素数),其欧拉函数的值(小于或等于的正整数中与互质的数的数目)可以用简单的公式表达:

这个公式是RSA加密算法半素数应用的重要部分。[4]对于一个平方半素数,该公式又会简化为:[4]

应用

半素数在密码学和数论中非常有用,最显著的例子的是RSA加密算法和随机数发生器等公开密钥加密应用。这些应用的基本原理是,计算两素数相乘结果(一个半素数)的过程简单,而反过来整数分解大半素数则比较困难。简单的来说,虽然35很容易就可以被分解成5×7,但是要想分解很大的半素数就不是那么容易了。RSA加密算法中有一个称为RSA-2048的半素数,有2,048位元,十进制有617位,RSA曾经公开悬赏200,000美元,给予成功将RSA-2048约数分解的人,迄2007年活动终止,未有人挑战成功领取悬赏。[5]

1974年,阿雷西博信息通过无线电信号被发向星团。其由1679个二进制数字组成,这些数字的用意是让接收方将信息解析成位图图像。选择数字是因为其是一个半素数,只存在一种构成矩形图像的可能(up to 图像平面的旋转和反射)。[6]

另见

  • 陈氏定理

参考资料与附注

  1. ^ Template:Cite OEIS
  2. ^ Stewart, Ian. Professor Stewart's Cabinet of Mathematical Curiosities. Profile Books. 2010: 154. ISBN 9781847651280. 
  3. ^ French, John Homer. Advanced Arithmetic for Secondary Schools. New York: Harper & Brothers. 1889: 53. 
  4. ^ 4.0 4.1 Cozzens, Margaret; Miller, Steven J., The Mathematics of Encryption: An Elementary Introduction, Mathematical World 29, American Mathematical Society: 237, 2013, ISBN 9780821883211 
  5. ^ The RSA Factoring Challenge[失效链接] 互联网档案馆的存档,存档日期2013-05-07.
  6. ^ du Sautoy, Marcus. The Number Mysteries: A Mathematical Odyssey through Everyday Life. St. Martin's Press. 2011: 19. ISBN 9780230120280. 

外部链接

  • 埃里克·韦斯坦因. Semiprime. MathWorld. 



上一篇:对称密钥加密
下一篇:对等加密
相关推荐