dorsal/arxiv
View SchemaOptimized quantum implementation of elliptic curve arithmetic over binary fields
| Authors | Phillip Kaye, Christof Zalka |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0407095 |
| URL | https://arxiv.org/abs/quant-ph/0407095 |
Abstract
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)).
{
"annotation_id": "6c70829a-e856-4230-8962-8117e6d99f13",
"date_created": "2026-03-02T18:02:10.286000Z",
"date_modified": "2026-03-02T18:02:10.286000Z",
"file_hash": "e331d00c2b30688c8c01dedda1ac2b360f748a750423b141f28209b514f196f2",
"private": false,
"record": {
"abstract": "Shor\u0027s quantum algorithm for discrete logarithms applied to elliptic curve\ngroups forms the basis of a \"quantum attack\" of elliptic curve cryptosystems.\nTo implement this algorithm on a quantum computer requires the efficient\nimplementation of the elliptic curve group operation. Such an implementation\nrequires we be able to compute inverses in the underlying field. In [PZ03],\nProos and Zalka show how to implement the extended Euclidean algorithm to\ncompute inverses in the prime field GF(p). They employ a number of\noptimizations to achieve a running time of O(n^2), and a space-requirement of\nO(n) qubits (there are some trade-offs that they make, sacrificing a few extra\nqubits to reduce running-time). In practice, elliptic curve cryptosystems often\nuse curves over the binary field GF(2^m). In this paper, we show how to\nimplement the extended Euclidean algorithm for polynomials to compute inverses\nin GF(2^m). Working under the assumption that qubits will be an `expensive\u0027\nresource in realistic implementations, we optimize specifically to reduce the\nqubit space requirement, while keeping the running-time polynomial. Our\nimplementation here differs from that in [PZ03] for GF(p), and we are able to\ntake advantage of some properties of the binary field GF(2^m). We also optimize\nthe overall qubit space requirement for computing the group operation for\nelliptic curves over GF(2^m) by decomposing the group operation to make it\n\"piecewise reversible\" (similar to what is done in [PZ03] for curves over\nGF(p)).",
"arxiv_id": "quant-ph/0407095",
"authors": [
"Phillip Kaye",
"Christof Zalka"
],
"categories": [
"quant-ph"
],
"title": "Optimized quantum implementation of elliptic curve arithmetic over binary fields",
"url": "https://arxiv.org/abs/quant-ph/0407095"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "ab4350a0-eaca-4a15-b631-a070ad10ae44",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}