因数分解问题的一些技术讨论
发表于 ： 2023年 1月 31日 01:23
https://crypto.stackexchange.com/questi ... -not-secur
“Claus Peter Schnorr recently posted a 12-page factoring method by SVP algorithms. Is it correct?
It says that the algorithm factors integers N≈2^400
and N≈2^800
by 4.2⋅109
and 8.4⋅1010
arithmetic operations."
那篇量子计算文章based on一个有争议的经典算法Schnorr factoring。 业内专家的实验表明需要尝试的次数远大于论文claim。
This suggest that the approach may be sensible, but that not all short vectors give rise to factoring relations, and that obtaining a sufficient success rate requires much larger lattice dimension than claimed in [Sch21].
Personnal study (unfortunately, never written down cleanly) of this approach suggested me that this approach requires solving SVP in dimensions beyond reasonable, leading to a factorization algorithm much slower than the state of the art. My impression is that this is the consensus among experts having spent some time on it as well.
“Claus Peter Schnorr recently posted a 12-page factoring method by SVP algorithms. Is it correct?
It says that the algorithm factors integers N≈2^400
and N≈2^800
by 4.2⋅109
and 8.4⋅1010
arithmetic operations."
那篇量子计算文章based on一个有争议的经典算法Schnorr factoring。 业内专家的实验表明需要尝试的次数远大于论文claim。
This suggest that the approach may be sensible, but that not all short vectors give rise to factoring relations, and that obtaining a sufficient success rate requires much larger lattice dimension than claimed in [Sch21].
Personnal study (unfortunately, never written down cleanly) of this approach suggested me that this approach requires solving SVP in dimensions beyond reasonable, leading to a factorization algorithm much slower than the state of the art. My impression is that this is the consensus among experts having spent some time on it as well.