We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Quantum circuits for $${\mathbb {F}}_{2^{n}}$$ -multiplication with subquadratic gate count.
- Authors
Kepley, Shane; Steinwandt, Rainer
- Abstract
One of the most cost-critical operations when applying Shor's algorithm to binary elliptic curves is the underlying field arithmetic. Here, we consider binary fields $${\mathbb {F}}_{2^n}$$ in polynomial basis representation, targeting especially field sizes as used in elliptic curve cryptography. Building on Karatsuba's algorithm, our software implementation automatically synthesizes a multiplication circuit with the number of $$T$$ -gates being bounded by $$7\cdot n^{\log _2(3)}$$ for any given reduction polynomial of degree $$n=2^N$$ . If an irreducible trinomial of degree $$n$$ exists, then a multiplication circuit with a total gate count of $${\mathcal {O}}(n^{\log _2(3)})$$ is available.
- Subjects
COMPUTER algorithms; COST analysis; ARITHMETIC; ELLIPTIC curve cryptography; COMPUTER software; POLYNOMIALS
- Publication
Quantum Information Processing, 2015, Vol 14, Issue 7, p2373
- ISSN
1570-0755
- Publication type
Article
- DOI
10.1007/s11128-015-0993-1