半素数

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

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

半素数在密码学数论中非常有用,最显著的例子是密码学中的公钥(例如RSA加密演算法)和隨機數發生器。主要的基本原理是利用这类数与生俱来的难以進行因數分解(至少是现在),而且随着数字的增长难度增加。简单的来说,35很容易就可以被分解成5×7,但是要想分解很大的半素数就不是那么容易了,RSA加密演算法中有一個稱為RSA-2048的半素数,有2,048位元,十進位有617位,RSA曾公開懸賞200,000美元,給予成功將RSA-2048因數分解的人,迄2007年活動終止,未有人挑戰成功領取懸賞。[1]

參考資料與附註[编辑]