「真偽はともかく、ちょっととんで...」、@a4lg さんからのスレッド

真偽はともかく、ちょっととんでもない論文が出てきたんだが。国際暗号学会の未査読論文だが、素因数分解を (RSA を破壊するレベルで) 劇的に高速化するアルゴリズムを開発したと主張している。
eprint.iacr.org/2021/232

このアルゴリズムの背景にある数学理論は完全に私の専門外だが、2^800 前後の数を因数分解するのに必要な算術演算数が事実だとすると、確かに RSA 破壊レベルだ ([G]NFS: 2.8126*10^23 → SVPベースの新アルゴリズム: 8.4*10^10)。

必要な算術演算の計算時間の細かなところを考えず、両アルゴリズムにおける 1 演算が同じ時間で完了するとした場合、2^800 前後の数で因数分解がおよそ 3 兆倍高速化ということに。実際には並列性の問題とかあるだろうし文字通り 3 兆倍速くなるわけではないだろうが、それでも半端ない。

というか、この論文の著者、シュノア (Schnorr) 署名で知られるシュノア氏じゃないか。明らかにぽっと出の数学者/暗号学者ではない。

「多分」再現実験できるレベルでアルゴリズムが書かれてるのでめっちゃ再現実験したいんだが、格子理論に全く詳しくないせいでしたくともできない……。歯痒い。

言いたいことは色々あるけど、ひとつだけ注釈。これは量子アルゴリズムではない (通常のコンピュータ向けのアルゴリズムだ)。

真偽については全く検証できそうにないが、少なくともシュノア署名で知られるシュノア氏自身による (彼を騙る馬の骨ではない)、イタズラでも何でもない論文投稿であることは海外の暗号学者が複数ルートで確かめたようだ。