我的猜测是，找到随机素数比查找随机数需要更多的计算能力。有人可以确认吗？
#1 楼
质数很重要，因为许多加密算法的安全性基于以下事实：将两个大质数相乘并获得结果非常快，而进行相反的运算则非常耗费计算机资源。当您知道一个数字是两个质数的乘积时，很难找到这两个质数。这个问题称为素因数分解，找到一种能快速完成的算法是计算机科学尚未解决的问题之一。评论
$ \ begingroup $
@mwhs并非如此，计算$ \ varphi（n）$仅与素因数分解有关，因为尚无其他方法可知。实际上，这两个问题是等效的。这意味着，如果您知道$ n $的素因式分解，则可以计算$ \ varphi（n）$（您已经提到过），另一方面，如果您知道$ \ varphi（n）$，则您可以可以推断出主要因素。编辑：这就是真的，如果您知道，$ n $是两个质数的乘积。
$ \ endgroup $
– Thekwasti
2014-12-18 14:40
$ \ begingroup $
@mwhs首先，您应该让冷静一下。第二：假设您知道$ n = pq $和$ \ varphi（n）=（p-1）（q-1）= pq-p-q + 1 $（而$ p $和$ q $未知）：然后，您可以将$ q $表示为$ q = n-\ varphi（n）-p + 1 $。将其放入$ n = pq $会得到$ n = p *（n- \ varphi（n）-p + 1）= -p ^ 2 +（n-\ varphi（n）+ 1）p $。最后一个方程是一个简单的二次方程，其中除p外，其他所有已知。您可以解决该问题以获得$ p $。做完了在这方面，当$ n $恰好有两个素数时，计算$ \ varphi（n）$和分解$ n $是相等的（因为其中一个的解产生了另一个的解）。
$ \ endgroup $
– Thekwasti
2014-12-18 15:42
$ \ begingroup $
两个问题是相等的，如果解决一个问题会产生另一个问题的（多项式时间）解决方案，反之亦然。就像我上面显示的：在此前提下，您知道$ n = pq $正好有两个素数，您可以从知道$ {n，p，q} $来计算$ \ varphi（n）$，反之亦然，您可以通过知道$ {n，\ varphi（n）} $来计算$ {p，q} $。这意味着，如果您找到了一种神奇的方法来为某些给定的公共RSA密钥$ n $计算私钥$ \ varphi（n）$，那么您就隐含地解决了$ n $的分解问题。
$ \ endgroup $
– Thekwasti
2014-12-18 16:06
#2 楼
实际上，重要的不是素数，而是具有因子（而不是1和它们本身）但很难分解的数字。通过将两个非常大的质数相乘得到这样的数字。同样大但因子较小的数字非常容易分解，因此不适合密码学目的-出于实际目的，分解数的难度随其最小素数的大小而变化，而不管其大小如何数字是，所以您的主要因素需要尽可能大。评论
$ \ begingroup $
好吧，我想。将2乘以1000的质数，再乘以1000的质数，得出的数字仍然很难分解。找到一个因素是很容易的，甚至是琐碎的，但不是所有因素。对于某些目的，这可能已经足够了，而对于其他目的，则可能并非如此。
$ \ endgroup $
–hvd
2014-12-17 14:15
$ \ begingroup $
@hvd将两个质数相乘时，乘积的唯一因数（一个和自身除外）是两个原始质数。
$ \ endgroup $
–马修
2014年12月17日的16:00
$ \ begingroup $
@mathh在我的示例中，找到因素（2）之一并除以后，确实得到了一个较小的数字，但没有一个明显较小的数字。寻找其他因素仍然很困难。这个答案声称分解因数的难度取决于它的最小素因数，但是我试图（当然不是很清楚）表明它也非常依赖于其他素因数。
$ \ endgroup $
–hvd
2014年12月17日下午16:34
$ \ begingroup $
@Matthew是的，我已经知道了。我看不到您要提出的观点，您能否详细说明？
$ \ endgroup $
–hvd
2014年12月17日下午16:36
$ \ begingroup $
您所做的陈述“找到一个因素是很容易的，甚至是琐碎的，但并非所有因素”似乎是错误的，或者至少是误导性的。由于只有两个因素，因此很难找到其中一个。
$ \ endgroup $
–马修
2014年12月17日下午16:42
#3 楼
对于加密的许多领域，您实际上确实希望尽可能地随机选择一个值。质数（或更准确地说，相对质数）仅在处理某些形式的非对称加密时才进入等式。非对称加密是指一个人使用公共密钥对邮件进行加密，然后再对收件人进行加密具有不同的私钥，使他们可以解密消息。对于这种类型的加密，您不能简单地使用随机数，因为公钥和私钥之间需要存在某种关系，很难通过公钥确定私钥，但是允许私钥成为相关，以便可以将其用于解密。
如果不需要这种关系，那么随机数会很多，更安全。这就是为什么对于诸如AES之类的对称算法来说，256位加密被认为是高度安全的，但是对于诸如RSA，2056甚至4092位加密之类的东西，则必须被认为是高度安全的。
这种关系公钥和私钥之间的加密使安全性降低，但它也是非对称加密功能起作用的唯一方法。
还值得注意的是，相对质数并不是唯一的“硬问题”。公钥和私钥之间的关系。还有其他难题，例如椭圆曲线密码学不是基于素数分解的。
评论
$ \ begingroup $
质数与ECC（通常和基于离散日志的系统）仍然非常相关：您希望以一组质数顺序操作，以逃避Pohlig-Hellman之类的算法。对于基于有限域中离散对数问题的系统而言，情况更是如此，因为索引演算算法本质上是整数分解算法。
$ \ endgroup $
–fkraiem
2014-12-18 4:39
$ \ begingroup $
@fkraiem-好的，也许我需要学习更多有关ECC的信息，但是如果它仍然是基于相对素因数分解的，那么为什么它更能抵抗量子因式分解呢？
$ \ endgroup $
– AJ亨德森
2014年12月18日下午4:50
$ \ begingroup $
Pohlig-Hellman之类的算法尝试通过分解组的顺序来加快离散对数的计算，但是，如果该组具有质数阶（在任何严重的实现中都是这种情况），则无法分解，因此这些算法完全没用，你很安全。但是我们确实需要接受一组素数的事实表明，素数是相关的，即使不是与RSA完全相同的方式也是如此。
$ \ endgroup $
–fkraiem
2014年12月18日下午4:57
$ \ begingroup $
@fkraiem-好的，这是有道理的，但对我来说有点数学，因为距离我上次获得研究生级别加密货币已有9年了，此后就没有再使用过。如果您有一个更好地重写最后一段的想法，请随时提出修改建议。我不确定我是否会纠正正确。
$ \ endgroup $
– AJ亨德森
2014年12月18日下午5:36
#4 楼
好问题。上面的大多数评论员基本上都正确，但是他们每个人都在讲故事的一部分，而不是在一篇文章中描述其他方面。这是一篇文章中更完整的原因：对于初学者来说，通常的理解是公钥密码术需要定量方法，特别是数论。这是使用模算术和质数作为此类数学的一部分的较大图片的一部分。尽管不必对特定理论的某些方面（例如组（Abelian））进行深入的了解才能使用密码学，但是它确实使公共密钥密码学更易于理解和使用。如果您不能使用模算法，这将是我的第一个建议。
首先，对于非对称密码，有两个定理适用：
1.）费马定理，它指出：$ m ^ {p-1}-1 \ bmod p = 0 $并且也可以用这种表示法看到：$ m ^ p \ equiv m \ pmod p $这意味着：对于任何素数$ p $和任何不能被$ p $整除的正整数$ m $，都会导致取回相同的余数。
2.）Euler的Totient函数又称phi函数：$ \ varphi（n） $，它是小于$ n $的整数，并且相对于$ n $质数。
与托勒（非商）相关的欧拉定理$ m ^ {\ varphi（n）} = 1 \ bmod n $。欧拉定理指出，至少有一个$ p $的值满足关系$ \ varphi（p）$；但是可能还有更多。
在对称加密中，Diffie Hellman利用质数，并且在公钥加密中发挥作用，但这似乎也很棘手...协议内通常有两部分进行密钥交换部分不对称，然后对称地形成/共享密钥。
Diffie Hellman使用质数的方法如下：整个基础像前面的例子一样是模算术，但它也结合了模幂。
现在是的，素数分解对于数复杂性理论中的某些应用可能很重要，但这不是通用的。
我将留下一个链接和有关质数的建议：
http://www.mersenne.org/
摘自算法（2009年），麻省理工学院出版社，第11章：大素数并非如此，可以相对容易地找到它们，但是由于不能考虑大素数的乘积，它们更安全。 。正如其他人提到的那样，离散对数就是一个例子。
我也强烈建议Daniel Boneh或Jonathan Katz的免费在线密码学Coursera课程。
评论
$ \ begingroup $
我将在以后添加有关Diffie Hellman的更多信息
$ \ endgroup $
–雅各布·麦克（Jacob E Mack）
2014年12月23日在22:34
#5 楼
考虑离散对数问题。如果组顺序不包含大素数，则可以解决每个小素数的问题，然后将它们“组合”为完整解。因此，可以描述这里素数为之所以需要，是因为它们无法分为更小的东西。
评论
$ \ begingroup $
可以对它们进行划分，但这是一个更复杂的多项式时间问题，有助于在某些条件成立时将攻击降低到可以忽略的程度。 –
$ \ endgroup $
–雅各布·麦克（Jacob E Mack）
2014年12月25日18:32
评论
素数在算术中已经非常重要，它们是一组非常特殊的整数。算术的基本定理与素因式分解有关（它说这种因式分解是唯一的）。现在，加密货币很大程度上基于算术。