Optimized quantum implementation of elliptic curve arithmetic over binary fields
| dc.creator | Kaye, Phillip | |
| dc.creator | Zalka, Christof | |
| dc.date | 2004-07-13 | |
| dc.date.accessioned | 2026-07-07T06:10:16Z | |
| dc.date.available | 2026-07-07T06:10:16Z | |
| dc.description | Shor's quantum algorithm for discrete logarithms applied to elliptic curve groups forms the basis of a "quantum attack" of elliptic curve cryptosystems. To implement this algorithm on a quantum computer requires the efficient implementation of the elliptic curve group operation. Such an implementation requires we be able to compute inverses in the underlying field. In [PZ03], Proos and Zalka show how to implement the extended Euclidean algorithm to compute inverses in the prime field GF(p). They employ a number of optimizations to achieve a running time of O(n^2), and a space-requirement of O(n) qubits (there are some trade-offs that they make, sacrificing a few extra qubits to reduce running-time). In practice, elliptic curve cryptosystems often use curves over the binary field GF(2^m). In this paper, we show how to implement the extended Euclidean algorithm for polynomials to compute inverses in GF(2^m). Working under the assumption that qubits will be an `expensive' resource in realistic implementations, we optimize specifically to reduce the qubit space requirement, while keeping the running-time polynomial. Our implementation here differs from that in [PZ03] for GF(p), and we are able to take advantage of some properties of the binary field GF(2^m). We also optimize the overall qubit space requirement for computing the group operation for elliptic curves over GF(2^m) by decomposing the group operation to make it "piecewise reversible" (similar to what is done in [PZ03] for curves over GF(p)). | |
| dc.description | 23 pages, 9 figures | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0407095 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0407095 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/92213 | |
| dc.subject | Quantum Physics | |
| dc.title | Optimized quantum implementation of elliptic curve arithmetic over binary fields | |
| dc.type | text |