本記事はQuantum Algorithm Zoo全訳シリーズの一部です。
以下のリンクから他の記事に飛べます。

• 前書き
• 代数アルゴリズム、数論アルゴリズム(本記事)
• オラクルアルゴリズム
• 近似アルゴリズム、シミュレーションアルゴリズム

Algorithm: 因数分解

Speedup: 超多項式的

詳細

$n$ ビットの整数が与えられたとき、その整数の素因数を計算する問題である。この問題は、Peter Shorによる量子アルゴリズムにより、 $\tilde{O}(n^3)$ [82, 125] で解けることが知られている。既知の最も高速な整数の因数分解の古典アルゴリズムは一般数体ふるい法であり、これは $2^{\tilde{O}(n^{1/3})}$ の時間を要すると信じられている。古典計算量において、厳密に証明された因数分解の最良の計算時間の上界はPolland-Strassenアルゴリズム [252, 362] によるもので、 $O(2^{n/4+o(1)})$ である。Shorの因数分解アルゴリズムはRSA公開鍵暗号を破る。また、このアルゴリズムと密接に関係した離散対数問題に対する量子アルゴリズムは、DSAやECDSAといったデジタル署名の手法、Diffie-Hellmanの鍵交換のプロトコルを破る。因数分解の問題の中でも、半素数を因数分解する問題は暗号で広く用いられている。入力が半素数である場合は、Shorのアルゴリズムよりもより高速な量子アルゴリズムがある [271] 。もし小さい素因数が存在する場合、Shorのアルゴリズムよりもグローバー探索を用いて楕円曲線法を高速化したほうが効率的である [366] 。Shorのアルゴリズムをさらに最適化したものが参考文献 [384, 386] で調べられている。例えば参考文献 [248] で、量子アルゴリズムによって破られないと信じられている公開鍵暗号方式が提案されている。Shorのアルゴリズムで因数分解を行うにあたって重要となるのは位数発見の問題である。位数発見の問題は可換隠れ部分群問題に帰着でき、可換隠れ部分群問題は量子フーリエ変換を用いて解くことが出来る。多くの他の問題が因数分解に帰着して解けることが知られている。例えば、奇数位数の体における行列群のメンバーシップ問題 [253] や、量子回路合成に関する或るディオファントス問題(diophantine problem) [254] などがある。

Algorithm: 離散対数問題

Speedup: 超多項式的

詳細

３つの $n$ ビット整数 $a,b,N$ が与えられる。これらは何らかの整数 $s$ について、 $b = a^s \mod N$ を満たす。離散対数問題は、そのような $s$ を求める問題である。Shorによって示されたように [82] , この問題は量子計算機によって ${\rm poly}(n)$ の計算時間で解くことが出来る。現在知られている最も高速な古典アルゴリズムは、 $n$ に対して超多項式的な時間を要する。参考文献 [82] と類似した手法を適用することで、量子計算機は楕円曲線上の離散対数問題を解くことが出来、これを用いて楕円曲線暗号 [109, 14] を破ることが出来る。Shorのアルゴリズムに対するさらなる改善が参考文献 [385] でなされている。超多項式的な量子計算による計算時間の加速は、半群上の離散対数問題に拡張することが出来る [203, 204] 。関連する内容として可換隠れ部分群問題を見よ。

Algorithm: ペル方程式

Speedup: 超多項式的

詳細

正で、かつ平方数でない整数 $d$ について、ペル方程式は $x^2 - dy^2 = 1$ と書ける。どのような $d$ についても、無限にこの方程式を満たす整数のペア $(x,y)$ が存在する。 $(x_1,y_1)$ を $x+y\sqrt{d}$ を最小化するペアだとする。もし $d$ が $n$ ビットの整数である (すなわち、$0 \leq d < 2^n$である)ならば、 $(x_1,y_1)$ を記述するには一般には指数的に多くのビットを要求するであろう。従って、 $(x_1, y_1)$ を多項式時間で求めることは一般には不可能である。 $R=\log(x_1 + y_1 \sqrt{d})$ という数を考える。 整数のペア $(x_1, y_1)$ は $\lfloor R \rceil$ から一意に定まる。Hallgrenによって示されたように [49] , 与えられた$n$ビットの整数 $d$ について量子計算機は$\lfloor R \rceil$を $ {\rm poly}(n)$ の時間で計算することが出来る。この問題について、多項式時間の古典アルゴリズムは知られていない。因数分解はこの問題に帰着することが出来る。この量子アルゴリズムはBuchman-Williams暗号方式を破る。関連する内容として可換隠れ部分群問題を見よ。

Algorithm: 主イデアル

Speedup: 超多項式的

詳細

$n$ビットの整数$d$と環$\mathbb{Z}[\sqrt{d}]$の可逆イデアル$I$が与えられているとする。$I=\alpha\mathbb{Z}[\sqrt{d}]$を満たす$\alpha\in\mathbb{Q}(\sqrt{d})$が存在する時、$I$を主イデアルと言う。$\alpha$は$d$の指数関数かもしれないので、一般には$\alpha$を多項式時間で書き下すことさえ出来ない。しかし、$\lfloor\log{\alpha}\rceil$によって$\alpha$は一意に決まる。ここで、$I$が主イデアルかどうかを決定し主イデアルである場合には$\lfloor\log{\alpha}\rceil$を求めるという問題を考える。Hallgrenは、量子計算機を使えばこの問題が多項式時間で解けることを示した [49] 。必要な量子ビットの数がより少なくなるように改良された量子アルゴリズムが参考文献 [131] で与えられた。その後、この主イデアル問題を任意の次元の数体に対して(次元の多項式時間で)解くための量子アルゴリズムが参考文献 [329] で与えられた。因数分解はペル方程式に帰着することが出来、ペル方程式は主イデアル問題に帰着することが出来る。従って、主イデアル問題は少なくとも因数分解と同じくらい難しく、Pにはおそらく属していない。可換隠れ部分群の項目も参照せよ。

Algorithm: 単元群

Speedup: 超多項式的

詳細

数体 $\mathbb{Q}(\theta)$ は、 $\theta$ が根であるような最低次の多項式の次数が $d$である時、次数が$d$ であると呼ぶ。$\mathbb{Z}[x]$ のモニック多項式の根であるような $\mathbb{Q}(\theta)$ の要素の集合 $\mathcal{O}$ は環をなす。この環は $\mathbb{Q}(\theta)$ の整数環と呼ばれる。環 $\mathcal{O}$ の単元 (逆元を持つ元) の集合は群をなす。この群を $\mathcal{O}^*$ と書く。Hallgren [50] によって、あるいはSchmidtとVollmer [116] によって独立に示されたように、定まった次数の任意の $\mathbb{Q}(\theta)$ に対し、量子計算機は与えられた $\theta$ の記述に対して多項式時間で $\mathcal{O}^*$ の生成元の集合を求めることが出来る。この問題を多項式時間で解く古典的アルゴリズムは知られていない。Hallgrenと彼の共著者は後に次数の多項式時間で解く方法も発見した [213] 。文献としては参考文献 [329] も見よ。このアルゴリズムは実数の加法群上の可換隠れ部分群問題が解けることに依存している。

Algorithm: 類群

Speedup: 超多項式的

詳細

数体 $\mathbb{Q}(\theta)$ は、 $\theta$ が根であるような最低次の多項式の次数が $d$である時、次数が$d$ であると呼ぶ。$\mathbb{Z}[x]$ のモニック多項式の根であるような $\mathbb{Q}(\theta)$ の要素の集合 $\mathcal{O}$ は環をなす。この環は $\mathbb{Q}(\theta)$ の整数環と呼ばれる。環において、素イデアルを法としたイデアルは類群と呼ばれる群をなす。Hallgrenによって示されたように [50] 、量子計算機は、任意の定数次数の数体の整数環の類群について、その生成元の集合を $\theta$の記述が与えられたもとで ${\rm poly}(\log(|\mathcal{O}|))$の時間で求めることが出来る。後に参考文献 [329] において、計算時間が$d$に関しても多項式になるように改善された量子アルゴリズムが与えられた。これらの問題を解く多項式時間の古典アルゴリズムは知られていない。可換隠れ部分群問題も参照せよ。

Algorithm: ガウス和

Speedup: 超多項式的

詳細

$\mathbb{F}_q$ を有限体とする。 $\mathbb{F}_q$ の非零要素は積に関して群 $\mathbb{F}_q^{\times}$ をなす。 $\mathbb{F}_q$ は和に関しては(可換群だが巡回群とは限らない)群 $\mathbb{F}_q^+$ をなす。$\mathbb{F}_q^{\times}$ の指標 $\chi^{\times}$ と、 $\mathbb{F}_q^+$ の指標 $\chi^+$ を選ぶ。この時、対応するガウス和は $\sum_{x\neq0\in \mathbb{F}_q} \chi^+(x) \chi^{\times}(x)$ である。van DamとSeroussiによって示されたように [90] 、ガウス和は量子計算機を用いて多項式時間で多項式精度のもとで求めることが出来る。有限環は積に関して群をなさないものの、有限環の単元の集合は積に関して群をなす。環の加法群の表現を選び、環の単元の乗法群の表現の表現を選ぶ。すると、有限環の単元に関するガウス和が計算できる。これらも量子計算機を用いて多項式時間で多項式精度のもとで求めることが出来る [90] 。ガウス和を多項式時間で推定する古典アルゴリズムは知られていない。離散対数問題はガウス和の推定に帰着できる [90] 。ポッツ模型(Potts model)の或る分配関数はガウス和の近似計算を用いて量子アルゴリズムで多項式時間で計算することが出来る [47] 。

Algorithm: 指数関数の合同式を解く問題 (Solving Exponential Congruences)

Speedup: 多項式的

詳細

$a,b,c,f,g \in \mathbb{F}_q$が与えられた時、 $af^x + bg^y = c$ を満たす整数 $x,y$ を求める問題である。古典計算機の最も良いアルゴリズムはこの問題を $\tilde{O}(q^{9/8})$ で解くのに対し、 参考文献 [111] で示されているように量子計算機はこの問題を $\tilde{O}(q^{3/8})$ で解くことが出来る。参考文献 [111] のアルゴリズムは離散対数と探索の量子アルゴリズムをベースに作られている。

Algorithm: 群表現の行列要素

Speedup: 超多項式的

詳細

有限群とコンパクトな線形群の全ての表現は、適切な基底の元でのユニタリ行列で表される。群の正則表現に対して量子フーリエ変換で共役を取ると、群の既約表現の直和となる。従って、対称群に対する効率的な量子フーリエ変換 [196] は、アダマールテスト(Hadamard test)と一緒に用いることで加法的エラーのもとで近似された $S_n$ の任意の既約表現の個々の行列要素を得る高速な量子アルゴリズムを構成する。同様に、量子シュール変換(quantum Schur transform) [197] を用いることで、多項式的なウェイトを持つ${\rm SU}(n)$の既約表現の行列要素を効率的に近似することが出来る。 ${\rm U}(n), {\rm SU}(n), {\rm SO}(n), A_n$に対する個々の既約表現についての効率的な量子回路の直接的な実装は参考文献 [106] にて与えられている。既知の古典アルゴリズムでは指数的な時間を要すると思われる例についても参考文献 [106] で明らかにされている。

Algorithm: 行列積の検証

Speedup: 多項式的

詳細

$n \times n$ の行列$A,B,C$が与えられる。行列積の検証問題とは、$AB=C$を満たすかどうかを判定する問題である。既知の最も効率の良い行列積の古典アルゴリズムは $O(n^{2.373})$の時間を要するのに対して、この問題は既知の最良の古典アルゴリズムでは $O(n^2)$ で解くことが出来る。 Ambainisらはこの問題を $O(n^{7/4})$ の時間で解く量子アルゴリズムを発見した [6] 。後に、BuhrmanとŠpalekによってこのアルゴリズムは $O(n^{5/3})$に改善された [19] 。 後者のアルゴリズムは量子ウォークに関して示されている参考文献 [85] の結果をベースにしている。

Algorithm: 部分和問題

Speedup: 多項式的

詳細

整数列 $x_1, \ldots, x_n$ と、目的の整数 $s$ が与えられる。部分和問題とは、総和が $s$ になるような整数列の部分集合があるかどうかを判定する問題である。この問題はNP完全問題であり、従って古典アルゴリズムでも量子アルゴリズムでも最悪ケースでは効率的に解けないと考えられる。部分和問題の困難なインスタンス集合では、与えられる整数は $2^n$ のオーダーを持つ。参考文献 [178] にて、このような場合に多項式係数を無視して $2^{0.241n}$ の時間で問題を解く量子アルゴリズムが与えられている。この量子アルゴリズムはElement Distinctnessに関するAmbainisの量子ウォークのアルゴリズム [7] の変種を、この問題に対するHowgrave-GrahamとJouxによって提案された洗練された古典アルゴリズムに適用したものである。既知の部分和問題に関する最も高速な古典アルゴリズムは多項式係数を無視して $2^{0.291n}$ の時間を必要とする。

Algorithm: 復号

Speedup: 問題による

詳細

古典誤り訂正符号では、情報を冗長に持つことによってどこにビットエラーが起きたのかを検知し、訂正することが出来る。任意の線形符号に対する最尤復号は最悪ケースでNP完全であることが知られている。しかし、良い構造を持った符号や、エラーが限定されている場合、効率的な復号アルゴリズムが知られている。畳み込み符号 [238] やシンプレックス符号 [239] に関して、復号を高速化する量子アルゴリズムが構成できる。

Algorithm: 制約充足問題

Speedup: 多項式的

詳細

制約充足問題の多くはNP困難であり、計算機科学においてしばしば現れる。制約充足問題の典型的な形態は3-SATである。全ての制約を充足するのではなく、できるだけ多くの制約を充足しようとする時、この問題は組合せ最適化問題となる。(関連する話題として断熱アルゴリズムの項を見よ。)制約充足問題に対する全探索による解法は、Groverの探索アルゴリズムを用いて時間のオーダーをルートまで改善できる。しかし、殆どの制約充足問題は古典アルゴリズムによって(依然として指数時間はかかるものの)全てのパターンを探索する全探索解法よりもルート以上に高速に解くことが出来る。それでもなお、既知の最も高速な3-SATに対する古典アルゴリズムを量子計算機で多項式的に加速する方法が与えられている [133] 。さらに、その他のいくつかの制約充足問題についても量子計算によって多項式的な加速を可能にする方法が参考文献 [134, 298] にて与えられている。古典アルゴリズムによる制約充足問題の解法で一般によく使われるアルゴリズムとしてバックトラッキングがある。そして、幾つかの制約充足問題について、このアルゴリズムは最も高速な既知の手法である。バックトラッキングのアルゴリズムを一般に量子加速する方法が参考文献 [264] で与えられている。

Algorithm: 量子計算による暗号解読

Speedup: 問題による

詳細

因数分解や離散対数問題に対するShorのアルゴリズム [82, 125] が、RSAやDiffie-Hellmanの暗号方式、あるいはそれらの楕円曲線ベースのバリエーション [109, 14] を完全に破ることはよく知られている。（多くの耐量子公開鍵暗号方式がこれらのプリミティブを置き換えるべく提案されている。これらの暗号方式が量子計算による攻撃に耐えるかは分かっていない。）Shorのアルゴリズムを超えて、暗号方式を攻撃するために特化してデザインされた量子アルゴリズムに関する研究がなされている。この試みは一般に３つのカテゴリーに分けることが出来る。一つ目は、標準的な仮定のもとで多項式的あるいは準指数的な時間での解読を可能にする量子アルゴリズムである。特に、Childs, Jao, Soukharevによる楕円曲線の同種(isogeny)を見つけるアルゴリズムは、Shorのアルゴリズムによって破られていなかったいくつかの楕円曲線暗号に対し、準指数的な時間での解読を可能にする [283] 。二つ目のカテゴリーは、グローバー探索、衝突問題の量子アルゴリズム、その他の量子アルゴリズムを用いて、既知の古典アルゴリズムによる暗号への攻撃を多項式的に高速化するものである。こうしたアプローチによる秘密鍵暗号 [284, 285, 288, 315, 316] や公開鍵暗号 [262, 287] のプリミティブに対する攻撃は、関連する暗号方式を排除するものではないが、選択するべき鍵長に影響を及ぼすかもしれない。三つ目のカテゴリーは重ね合わせ状態を用いた問い合わせによるブロック暗号への攻撃である。これらの攻撃は多くの場合、暗号プリミティブを完全に破る [286, 289, 290, 291, 292] 。しかしながら、殆どの現実的な状況では重ね合わせ状態を用いた問い合わせは実行できそうにない。

参考文献

6

A. Ambainis, H. Buhrman, P. Høyer, M. Karpinizki, and P. Kurur
Quantum matrix verification.
Unpublished Manuscript, 2002.

7

Andris Ambainis
Quantum walk algorithm for element distinctness.
SIAM Journal on Computing, 37:210-239, 2007.
arXiv:quant-ph/0311001

14

D. Boneh and R. J. Lipton
Quantum cryptanalysis of hidden linear functions.
In Don Coppersmith, editor, CRYPTO '95, Lecture Notes in Computer Science, pages 424-437. Springer-Verlag, 1995.

19

Harry Buhrman and Robert Špalek
Quantum verification of matrix products.
In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms, pages 880-889, 2006.
arXiv:quant-ph/0409035

47

Joseph Geraci and Daniel A. Lidar
On the exact evaluation of certain instances of the Potts partition function by quantum computers.
Comm. Math. Phys. Vol. 279, pg. 735, 2008.
arXiv:quant-ph/0703023.

49

Sean Hallgren
Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem.
In Proceedings of the 34th ACM Symposium on Theory of Computing, 2002.

50

Sean Hallgren
Fast quantum algorithms for computing the unit group and class group of a number field.
In Proceedings of the 37th ACM Symposium on Theory of Computing, 2005.

82

Peter W. Shor
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.
SIAM Journal on Computing, 26(5):1484-1509, 1997.
arXiv:quant-ph/9508027.

85

M. Szegedy
Quantum speed-up of Markov chain based algorithms.
In Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pg. 32, 2004.

90

Wim van Dam and Gadiel Seroussi
Efficient quantum algorithms for estimating Gauss sums.
arXiv:quant-ph/0207131, 2002.

106

Stephen P. Jordan
Fast quantum algorithms for approximating the irreducible representations of groups.
arXiv:0811.0562, 2008.

109

John Proos and Christof Zalka
Shor's discrete logarithm quantum algorithm for elliptic curves.
Quantum Information and Computation, Vol. 3, No. 4,pg.317-344, 2003.
arXiv:quant-ph/0301141.

111

Wim van Dam and Igor Shparlinski
Classical and quantum algorithms for exponential congruences.
Proceedings of TQC 2008, pg. 1-10.
arXiv:0804.1109.

116

Arthur Schmidt and Ulrich Vollmer
Polynomial time quantum algorithm for the computation of the unit group of a number field.
In Proceedings of the 37th Symposium on the Theory of Computing, pg. 475-480, 2005.

125

Peter Shor
Algorithms for Quantum Computation: Discrete Logarithms and Factoring.
In Proceedings of FOCS 1994, pg. 124-134.

131

Arthur Schmidt
Quantum Algorithms for many-to-one Functions to Solve the Regulator and the Principal Ideal Problem.
arXiv:0912.4807, 2009.

133

Andris Ambainis
Quantum Search Algorithms.
SIGACT News, 35 (2):22-35, 2004.
arXiv:quant-ph/0504012

134

Nicolas J. Cerf, Lov K. Grover, and Colin P. Williams
Nested quantum search and NP-hard problems.
Applicable Algebra in Engineering, Communication and Computing, 10 (4-5):311-338, 2000.

178

Daniel J. Bernstein, Stacey Jeffery, Tanja Lange, and Alexander Meurer
Quantum algorithms for the subset-sum problem.
from cr.yp.to.

196

Robert Beals
Quantum computation of Fourier transforms over symmetric groups.
In Proceedings of STOC 1997, pg. 48-53.

197

Dave Bacon, Isaac L. Chuang, and Aram W. Harrow
The quantum Schur transform: I. efficient qudit circuits.
In Proceedings of SODA 2007, pg. 1235-1244.
arXiv:quant-ph/0601001.

203

Andrew Childs and Gábor Ivanyos
Quantum computation of discrete logarithms in semigroups.
arXiv:1310.6238,2013.

204

Matan Banin and Boaz Tsaban
A reduction of semigroup DLP to classic DLP.
arXiv:1310.7903,2013.

213

Kirsten Eisenträger, Sean Hallgren, Alexei Kitaev, and Fang Song
A quantum algorithm for computing the unit group of an arbitrary degree number field
In Proceedings of STOC 2014 pg. 293-302.

238

Jon R. Grice and David A. Meyer
A quantum algorithm for Viterbi decoding of classicalconvolutional codes
arXiv:1405.7479

239

Alexander Barg and Shiyu Zhou
A quantum decoding algorithm of the simplex code
Proceedings of the 36th Annual Allerton Conference, 1998
Available at author's homepage.

248

Daniel J. Bernstein, Johannes Buchmann, and Erik Dahmen, Eds.
Post-Quantum Cryptography
Springer, 2009.

252

J. M. Pollard
Theorems on factorization and primality testing
Proceedings of the Cambridge Philosophical Society. 76:521-228, 1974.

253

L. Babai, R. Beals, and A. Seress
Polynomial-time theory of matrix groups
In Proceedings of STOC 2009, pg. 55-64.

254

Neil J. Ross and Peter Selinger
Optimal ancilla-free Clifford+T approximations of z-rotations
arXiv:1403.2975, 2014.

262

T. Laarhoven, M. Mosca, and J. van de Pol
Solving the shortest vector problem in lattices faster using quantum search
Proceedings of PQCrypto13, pp. 83-101, 2013.
arXiv:1301.6176

264

Ashley Montanaro
Quantum walk speedup of backtracking algorithms
arXiv:1509.02374, 2015.

271

Frédéric Grosshans, Thomas Lawson, FrançoisMorain, and Benjamin Smith
Factoring safe semiprimes with a single quantum query
arXiv:1511.04385, 2015.

283

Andrew M. Childs, David Jao, and Vladimir Soukharev
Constructing elliptic curve isogenies in quantum subexponential time
Journal of Mathematical Cryptology, 8(1):1-29 (2014)
arXiv:1012.4019.

284

Markus Grassl, Brandon Langenberg, Martin Roetteler, and Rainer Steinwandt
Applying Grover's algorithm to AES: quantum resource estimates
arXiv:1512.04965, 2015.

285

M. Ami, O. Di Matteo, V. Gheorghiu, M. Mosca, A. Parent, and J. Schanck
Estimating the cost of generic quantum pre-image attacks onSHA-2 and SHA-3
arXiv:1603.09383, 2016.

286

Marc Kaplan, Gaetan Leurent, Anthony Leverrier, and Maria Naya-Plasencia
Quantum differential and linear cryptanalysis
arXiv:1510.05836, 2015.

287

Scott Fluhrer
Quantum Cryptanalysis of NTRU
Cryptology ePrint Archive: Report 2015/676, 2015.

288

Marc Kaplan
Quantum attacks against iterated block ciphers
arXiv:1410.1434, 2014.

289

H. Kuwakado and M. Morii
Quantum distinguisher between the 3-round Feistel cipher and the random permutation
In Proceedings of IEEE International Symposium on Information Theory (ISIT), pg. 2682-2685, 2010.

290

H. Kuwakado and M. Morii
Security on the quantum-type Even-Mansour cipher
In Proceedings of International Symposium on Information Theory and its Applications (ISITA), pg. 312-316, 2012.

291

Martin Roetteler and Rainer Steinwandt
A note on quantum related-key attacks
arXiv:1306.2301, 2013.

292

Thomas Santoli and Christian Schaffner
Using Simon's algorithm to attack symmetric-key cryptographic primitives
arXiv:1603.07856, 2016.

298

Salvatore Mandra, Gian Giacomo Guerreschi, and Alan Aspuru-Guzik
Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems
arXiv:1512.00859, 2015.

315

Gilles Brassard, Peter Høyer, and Alain Tapp
Quantum cryptanalysis of hash and claw-free functions
In Proceedings of the 3rd Latin American symposium on Theoretical Informatics (LATIN'98), pg. 163-169, 1998.

316

Daniel J. Bernstein
Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?
In Proceedings of the 4th Workshop on Special-purpose Hardware for Attacking Cryptographic Systems (SHARCS'09), pg. 105-116, 2009.
[available here]

329

Jean-François Biasse and Fang Song
Efficient quantum algorithms for computing class groups and solving the principal ideal problem in arbitrary degree number fields
Proceedings of the 27th Annual ACM-SIAM Symposium on DiscreteAlgorithms (SODA '16), pg. 893-902, 2016.

362

Volker Strassen
Einige Resultate über Berechnungskomplexität
In Jahresbericht der Deutschen Mathematiker-Vereinigung, 78(1):1-8, 1976/1977.

366

D. J. Bernstein, N. Heninger, P. Lou, and L. Valenta
Post-quantum RSA
IACR e-print 2017/351, 2017.

384

M. Ekerå and J. Håstad
Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers
Proceedings of PQCrypto 2017, pg. 347-363. (LNCS Volume 10346), 2017.

385

M. Ekerå
On post-processing in the quantum algorithm for computing short discrete logarithms
IACR ePrint Archive Report 2017/1122, 2017.

386

D. J. Bernstein, J.-F. Biasse, and M. Mosca
A low-resource quantum factoring algorithm
Proceedings of PQCrypto 2017, pg. 330-346 (LNCS Volume 10346), 2017.