Quantum algorithm for discrete logarithm over ZN

被引：0

作者：

Fu, Xiang-Qun ^{[1
]}

Bao, Wan-Su ^{[1
]}

Wang, Shuai ^{[2
]}

机构：

[1] PLA Information Engineering University

[2] Unit 73671, Liu'an

来源：

Jisuanji Xuebao/Chinese Journal of Computers | 2014年 / 37卷 / 05期

关键词：

Discrete logarithm; Information security; Network security; Public-key crypto; Quantum algorithm; Quantum Fourier transform; Quantum gate;

D O I：

10.3724/SP.J.1016.2014.01058

中图分类号：

学科分类号：

摘要：

By applying multiple Fourier transform and variable transform, a quantum algorithm for discrete logarithm problem over ZN is presented. The relationship between order r and success probability is quantitatively characterized, where r is the order of the selective element. Particularly, when r is a prime number, the success probability is close to 1 and the scale of elementary quantum gates is O(L3), where L=[log N]+1. The new algorithm doesn't need to perform inverse quantum Fourier transform on |f(x1, x2)>, which is superior to the existing algorithm.

引用

页码：1058 / 1062

页数：4

共 11 条

[1]

Bennett C.H., Brassard G., Quantum cryptography: Public-key distribution and coin tossing, Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing, pp. 175-179, (1984)

[2]

Zhang Y., Lu K., Gao Y.-H., Quantum algorithms and quantum-inspired algorithms, Chinese Journal of Computers, 36, 9, pp. 1835-1842, (2013)

[3]

Wan S.-S., Chen H.-W., Cao R.-J., An analogic selection storing algorithm for synthesis of reversible logic circuits, Chinese Journal of Computers, 33, 12, pp. 2343-2352, (2010)

[4]

Bao W.-S., Song Z., Zhong P.-C., Fu X.-Q., Quantum mechanical meet-in-middle algorithm for subset sum problem, Acta Electronica Sinica, 39, 1, pp. 128-132, (2011)

[5]

Deutsch D., Jozsa R., Rapid solution of problems by quantum computation, Proceedings of the Royal Society A, 439, 1907, pp. 553-558, (1992)

[6]

Shor P.W., Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing, 26, 5, pp. 1484-1509, (1997)

[7]

Grover L.K., A fast quantum mechanics algorithm for database search, Proceeding of the 28th ACM Symposium on Theory of Computation, pp. 212-219, (1996)

[8]

Wang X., Bao W.-S., Fu X.-Q., A quantum algorithm for searching a target solution of fixed weight, Chinese Science Bulletin, 56, 6, pp. 484-488, (2011)

[9]

Fu X.-Q., Bao W.-S., Zhou C., Song Z., t-bit semiclassical quantum Fourier transform, Chinese Science Bulletin, 57, 6, pp. 119-124, (2012)

[10]

Nielsen M.A., Chuang I.L., Quantum Computation and Quantum Information, (2000)

← 1 2 →