Paper 2021/980

Binary Field Montgomery Multiplication on Quantum Computers

Kyoungbae Jang, Gyeong Ju Song, Hyunji Kim, Hyeokdong Kwon, Wai-Kong Lee, Zhi Hu, and Hwajeong Seo

Abstract

Optimizing arithmetic operations into quantum circuits to utilize quantum algorithms, such as the Shor algorithm and Grover search algorithm for cryptanalysis, is an active research field in cryptography implementation. In particular, reducing quantum resources is important for efficient implementation. In this paper, binary field ($GF(2^n)$) Montgomery multiplication in quantum circuits is presented. We utilize the bit-level Montgomery algorithm to efficiently compute the Montgomery product $C = A \cdot B \cdot r^{-1}$ in the binary field $GF(2^n)$. Additionally, we also present an efficient Montgomery multiplication quantum circuit in the case where the modulus of $GF(2^n)$ is specified.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. Minor revision.
Keywords
Quantum ComputersMontgomery MultiplicationBinary Field
Contact author(s)
hwajeong84 @ gmail com
starj1023 @ gmail com
waikonglee @ gachon ac kr
huzhi_math @ csu edu cn
History
2021-07-22: received
Short URL
https://ia.cr/2021/980
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/980,
      author = {Kyoungbae Jang and Gyeong Ju Song and Hyunji Kim and Hyeokdong Kwon and Wai-Kong Lee and Zhi Hu and Hwajeong Seo},
      title = {Binary Field Montgomery Multiplication on Quantum Computers},
      howpublished = {Cryptology ePrint Archive, Paper 2021/980},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/980}},
      url = {https://eprint.iacr.org/2021/980}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.