Quantum circuits for F2n-multiplication with subquadratic gate count

© 2015, Springer Science+Business Media New York.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}$$F2n 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$$T-gates being bounded by $$7\cdot n^{\log _2(3)}$$7·nlog2(3) for any given reduction polynomial of degree $$n=2^N$$n=2N. If an irreducible trinomial of degree $$n$$n exists, then a multiplication circuit with a total gate count of $${\mathcal {O}}(n^{\log _2(3)})$$O(nlog2(3)) is available.