半質數

半質數 圖片來自newton

数学中，两个素数的乘积所得的自然数我们称之为半素数（也叫双素数，二次殆素数 ）。开始的几个半素数是4, 6, 9, 10, 14, 15, 21, 22, 25, 26, ... id=A001358它們包含1及自己在內合共有3或4個因數。

目录

性质

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

对于非平方半素数n=pq（p\ne q），其欧拉函数的值varphi(n)（小于或等于n的正整数中与n互质的数的数目）可以用简单的公式表达：

varphi(n)=(p-1)(q-1)=n-(p+q)+1.

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

varphi(n)=p(p-1)=n-p.

应用

半素数在密码学和数论中非常有用，最显著的例子的是RSA加密演算法和隨機數發生器等公开密钥加密应用。这些应用的基本原理是，计算两素数相乘结果（一个半素数）的过程简单，而反过来整数分解大半素数则比较困难。简单的来说，虽然35很容易就可以被分解成5×7，但是要想分解很大的半素数就不是那么容易了。RSA加密演算法中有一個稱為RSA-2048的半素数，有2,048位元，十進位有617位，RSA曾經公開懸賞200,000美元，給予成功將RSA-2048因數分解的人，迄2007年活動終止，未有人挑戰成功領取懸賞。

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

例子与种类

比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, 95 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, ... A006881

半素数是<math>k=2</math>的<math>k</math>次殆素数（有且仅有<math>k</math>个质因数的数）。 但是有些数列将“半素数”解释为一种更加宽泛的数，即最多有两个质因数的数，包括：

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, ... A037143