添加的内容 删除的内容
小 （撤销繁简转换） 标签：回退 |
小 （机器人：清理不当的来源、移除无用的模板参数） |
||
（未显示同一用户的1个中间版本） | |||
| 第11行： | 第11行： | ||
半素数是<math>k=2</math>的<math>k</math>次[[殆素数]]（有且仅有<math>k</math>个质因数的数）。 |
半素数是<math>k=2</math>的<math>k</math>次[[殆素数]]（有且仅有<math>k</math>个质因数的数）。 |
||
但是有些数列将“半素数”解释为一种更加宽泛的数，即最多有两个质因数的数<ref>{{cite book|title=Professor Stewart's Cabinet of Mathematical Curiosities|first=Ian|last=Stewart|publisher=Profile Books|year=2010|isbn=9781847651280|page=154 |
但是有些数列将“半素数”解释为一种更加宽泛的数，即最多有两个质因数的数<ref>{{cite book|title=Professor Stewart's Cabinet of Mathematical Curiosities|first=Ian|last=Stewart|publisher=Profile Books|year=2010|isbn=9781847651280|page=154}}</ref>，包括： |
||
: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}} |
: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}} |
||
== 性质 == |
== 性质 == |
||
除了自己本身外，半素数没有其他合数因数。<ref>{{cite book|page=53| |
除了自己本身外，半素数没有其他合数因数。<ref>{{cite book|page=53||title=Advanced Arithmetic for Secondary Schools|first=John Homer|last=French|year=1889|publisher=Harper & Brothers|location=New York}}</ref>例如，1、2、13及26是半素数26的因数，其中只有26是合数。 |
||
对于非平方半素数<math>n=pq</math>（<math>p\ne q</math>），其[[欧拉函数]]的值<math>\varphi(n)</math>（小于或等于<math>n</math>的正整数中与<math>n</math>[[互质]]的数的数目）可以用简单的公式表达： |
对于非平方半素数<math>n=pq</math>（<math>p\ne q</math>），其[[欧拉函数]]的值<math>\varphi(n)</math>（小于或等于<math>n</math>的正整数中与<math>n</math>[[互质]]的数的数目）可以用简单的公式表达： |
||
:<math>\varphi(n)=(p-1)(q-1)=n-(p+q)+1.</math> |
:<math>\varphi(n)=(p-1)(q-1)=n-(p+q)+1.</math> |
||
这个公式是[[RSA加密演算法]]半素数应用的重要部分。<ref name=moe>{{citation|title=The Mathematics of Encryption: An Elementary Introduction|volume=29|series=Mathematical World|first1=Margaret|last1=Cozzens|first2=Steven J.|last2=Miller|publisher=American Mathematical Society|year=2013|isbn=9780821883211|page=237 |
这个公式是[[RSA加密演算法]]半素数应用的重要部分。<ref name=moe>{{citation|title=The Mathematics of Encryption: An Elementary Introduction|volume=29|series=Mathematical World|first1=Margaret|last1=Cozzens|first2=Steven J.|last2=Miller|publisher=American Mathematical Society|year=2013|isbn=9780821883211|page=237}}</ref>对于一个平方半素数，该公式又会简化为：<ref name=moe/> |
||
:<math>\varphi(n)=p(p-1)=n-p.</math> |
:<math>\varphi(n)=p(p-1)=n-p.</math> |
||
== 应用 == |
== 应用 == |
||
半素数在[[密码学]]和[[数论]]中非常有用，最显著的例子的是[[RSA加密演算法]]和[[隨機數發生器]]等[[公开密钥加密]]应用。这些应用的基本原理是，计算两素数相乘结果（一个半素数）的过程简单，而反过来[[整数分解]]大半素数则比较困难。简单的来说，虽然35很容易就可以被分解成5×7，但是要想分解很大的半素数就不是那么容易了。RSA加密演算法中有一個稱為RSA-2048的半素数，有2,048位元，十進位有617位，RSA曾經公開懸賞200,000[[美元]]，給予成功將RSA-2048因數分解的人，迄2007年活動終止，未有人挑戰成功領取懸賞。<ref>{{Cite web |url=http://www.rsa.com/rsalabs/node.asp?id=2092 |title=The RSA Factoring Challenge |access-date=2012-08-04 |
半素数在[[密码学]]和[[数论]]中非常有用，最显著的例子的是[[RSA加密演算法]]和[[隨機數發生器]]等[[公开密钥加密]]应用。这些应用的基本原理是，计算两素数相乘结果（一个半素数）的过程简单，而反过来[[整数分解]]大半素数则比较困难。简单的来说，虽然35很容易就可以被分解成5×7，但是要想分解很大的半素数就不是那么容易了。RSA加密演算法中有一個稱為RSA-2048的半素数，有2,048位元，十進位有617位，RSA曾經公開懸賞200,000[[美元]]，給予成功將RSA-2048因數分解的人，迄2007年活動終止，未有人挑戰成功領取懸賞。<ref>{{Cite web |url=http://www.rsa.com/rsalabs/node.asp?id=2092 |title=The RSA Factoring Challenge |access-date=2012-08-04 }}</ref> |
||
1974年，[[阿雷西博信息]]通过无线电信号被发向[[星团]]。其由1679个二进制数字组成，这些数字的用意是让接收方将信息解析成[[位图]]图像。选择数字<math>1679=23\cdot 73</math>是因为其是一个半素数，只存在一种构成矩形图像的可能（[[up to]] 图像平面的旋转和反射）。<ref>{{cite book|title=The Number Mysteries: A Mathematical Odyssey through Everyday Life|first=Marcus|last=du Sautoy| |
1974年，[[阿雷西博信息]]通过无线电信号被发向[[星团]]。其由1679个二进制数字组成，这些数字的用意是让接收方将信息解析成[[位图]]图像。选择数字<math>1679=23\cdot 73</math>是因为其是一个半素数，只存在一种构成矩形图像的可能（[[up to]] 图像平面的旋转和反射）。<ref>{{cite book|title=The Number Mysteries: A Mathematical Odyssey through Everyday Life|first=Marcus|last=du Sautoy||publisher=St. Martin's Press|year=2011|isbn=9780230120280|page=19}}</ref> |
||
== 另见 == |
== 另见 == |
||