こんにちは、量子コンピュータで最近暗号が解けるとか解けないとか話題になってますね。便乗して解説します。
中国の研究者が量子コンピューターでRSA暗号の解読手法を構築 - GIGAZINE
https://gigazine.net/news/20241015-rsa-encryption-quantum-computer
まず現在メジャーな解き方は三つあります。一番本格的なのはショアのアルゴリズムです。詳しい解説は、現NTTデータの加藤くんと理研の中田さんとの下記の資料にあります。
https://speakerdeck.com/gyudon/shorfalsearugorizumu
作り方は結構大変で量子ゲート方式の本格的な量子コンピュータが必要です。こちらにも過去の解説があります。
いちばんやさしい量子コンピュータで暗号を解くshorのアルゴリズム概要
https://blueqat.com/yuichiro_minato2/11c3f4fb-eaa7-48fa-bed0-e5daf39c02fe
また、具体的にpythonでもつくれます。すんごい大変です。下記に作成手順を書いたことがありますが、頑張れる人だけ頑張ってみてください。。。
量子ゲートで加算、減算、モジュロ演算
https://blueqat.com/yuichiro_minato2/487eb21d-27f9-4ba1-89f1-a0b0d7ec4d37
こちらのショアのアルゴリズムは本格的なもので、頑張って学べば習得できます！マシンの性能が全く追い付いてないので現在は全く素因数分解できてませんが、もっとも本格的で有望な方法です。
さて、今回話題になってる中国は上の方法ではなく、組合せ最適化を利用した亜流です。小さい問題は解けるが大きな問題は解けなさそうと言われています。
最適化を利用したものでも二つあります。ひとつは単純に(N-pq)^2=0を解いたものです。左の式がゼロになればオッケー。pとかqは適当な数を割り当てますが比較的この二つは桁数が近いとわかってるので、1+2x0+4x1+8x2+...のように二進数で計算します。掛け算すると複雑になりますが、こちらを根性で解きます。
じつはDwaveはこうした掛け算が苦手なのであんまりやられないのですが、それを無理矢理実行したのが今回の中国の方法です。正直何万回も実行できるので、そのうち一回くらいまぐれで解けることがあります。
もうひとつ今回は別の方法でも解かれていて、それは最近の方法ですが、そちらも今回は解くに新しいことはなく、やってみたくらいの感じでした。
こちらもブログでかいたことがあります。興味ある人はやってみてください。
https://blueqat.com/yuichiro_minato2/432d70af-d302-4878-a553-f5904a7eeb65
暗号解読は量子コンピュータアプリのなかでも最高難易度なのでつかれるのであんまりやりたくないですが、世の中にはすごい人たちがいるものです。