zyl*_*024 13 performance cryptography rsa public-key-encryption factorization
我只是计算机科学的初学者.我学到了一些关于跑步的知识,但我无法确定我的理解是对的.所以请帮助我.
所以整数分解目前不是多项式时间问题,而是素数测试.假设要检查的数字是n.如果我们运行一个程序只是为了决定从1到sqrt(n)的每个数字是否可以除以n,如果答案是肯定的,则存储该数字.我觉得这个程序是多项式时间,不是吗？
我错误的一种可能方式是分解程序应该找到所有素数,而不是发现的第一个素数.也许这就是原因所在.
但是,在公钥加密中,找到大量的主要因素对于攻击密码学至关重要.由于通常大量(公钥)只是两个素数的乘积,找到一个素数就意味着找到另一个素数.这应该是多项式时间.那为什么攻击很难或不可能？
Rya*_*per 15
像"多项式因式分解算法"这样的复杂性的随意描述通常是指关于输入大小的复杂性,而不是输入的解释.所以,当人们说"没有已知的多项式算法保",他们的意思是有没有已知的算法融通ñ位,在多项式时间相对于运行自然数ñ.相对于该数字本身,它可以是最多2 ^不多项式Ñ.
分解的难度是那些美观的数学问题之一,这些问题很容易理解并且会立即带到人类知识的边缘.总结(今天)关于这个主题的知识:我们不知道为什么它很难,没有任何程度的证明,以及我们在多项式时间内运行的最佳方法(但也明显少于指数时间).其结果是素性测试是即使在P是非常近; 查看链接的维基百科页面.
我所知道的最好的启发式解释是素数是随机分布的.Dirichlet定理是一个比较容易理解的结果.这个定理说每个算术级数包含无限多个素数,换句话说,你可以认为质数在进化方面是密集的,这意味着你无法避免碰到它们.这是这类结果中最简单的一个大集合; 在所有这些中,素数的出现方式与随机数非常相似.
因此,分解的困难类似于不可能反转一次性垫.在一次性垫中,有一点我们不知道XOR与另一个我们没有.我们得知关于知道XOR结果的单个位的零信息.将"bit"替换为"prime"并将其与XOR相乘,您就会遇到因子分解问题.就好像你将两个随机数相乘,你从产品中获得的信息非常少(而不是零信息).