Efficient quantum circuits for binary elliptic curve arithmetic: reducing T-gate complexity

Autor:	Amento, Brittanney, Steinwandt, Rainer, Roetteler, Martin
Rok vydání:	2012
Předmět:	Quantum Physics Computer Science - Data Structures and Algorithms Computer Science - Emerging Technologies
Zdroj:	Quantum Information & Computation 13(7-8): 631-644 (2013)
Druh dokumentu:	Working Paper
Popis:	Elliptic curves over finite fields GF(2^n) play a prominent role in modern cryptography. Published quantum algorithms dealing with such curves build on a short Weierstrass form in combination with affine or projective coordinates. In this paper we show that changing the curve representation allows a substantial reduction in the number of T-gates needed to implement the curve arithmetic. As a tool, we present a quantum circuit for computing multiplicative inverses in GF(2^n) in depth O(n log n) using a polynomial basis representation, which may be of independent interest. Comment: 14 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1209.6348 Zobrazit plný text záznamu View this record from Arxiv