現在広く利用されている公開鍵暗号は、素因数分解問題や離散対数問題の求解の難しさに安全性を依拠している。暗号に使用されるこれらの問題は、現在のコンピュータでは計算が困難であるものの、大規模な量子コンピュータが実現すれば容易に求解できることがわかっている。素因数分解問題や離散対数問題を求解できる量子コンピュータの規模は、求解に必要となる計算量に依存することから、暗号が解読され得る時期を予測するには、量子コンピュータのハードウェア開発に関する動向に加えて、求解の方法（アルゴリズム）の効率化にかかる研究の進展にも注目する必要がある。1994年に初めて素因数分解等を求解するアルゴリズムが提案されて以降、量子コンピュータによって容易に求解可能となる問題に関する研究は進展しており、その求解可能となる問題の範囲は、素因数分解問題や離散対数問題も含む可換群の隠れ部分群問題と呼ばれる問題にまで拡大している。こうした研究の進展を受け、これまでの想定より小規模な量子コンピュータで素因数分解問題の求解が可能となることもわかってきている。本稿では、こうした研究の進展によって明らかとなった、可換群の隠れ部分群問題、および、素因数分解問題と離散対数問題の関係について解説するとともに、これらの問題が量子コンピュータによって容易に求解できる仕組みを理解するため、そのアルゴリズムを解説する。
キーワード：隠れ部分群問題、素因数分解問題、耐量子計算機暗号、離散対数問題、量子アルゴリズム、量子コンピュータ
掲載論文等の内容や意見は、執筆者個人に属し、日本銀行あるいは金融研究所の公式見解を示すものではありません。