我只是计算机科学的初学者.我学到了一些关于跑步的知识,但我无法确定我的理解是对的.所以请帮助我.
所以整数分解目前不是多项式时间问题,而是素数测试.假设要检查的数字是n.如果我们运行一个程序只是为了决定从1到sqrt(n)的每个数字是否可以除以n,如果答案是肯定的,则存储该数字.我觉得这个程序是多项式时间,不是吗？
我错误的一种可能方式是分解程序应该找到所有素数,而不是发现的第一个素数.也许这就是原因所在.
但是,在公钥加密中,找到大量的主要因素对于攻击密码学至关重要.由于通常大量(公钥)只是两个素数的乘积,找到一个素数就意味着找到另一个素数.这应该是多项式时间.那为什么攻击很难或不可能？
performance cryptography rsa public-key-encryption factorization