On computing ord(N)(2) and its application

doi:10.1016/j.ic.2006.04.003

CSpace

	On computing ord(N)(2) and its application
	Liu, LH ; Cao, ZJ
	2006-07-01
发表期刊	INFORMATION AND COMPUTATION
ISSN	0890-5401
卷号	204 期号:7 页码:1173-1178
摘要	Shor proposed a polynomial time algorithm for prime factorization on quantum computers. For a given number N, he gave an algorithm for finding the order r of an element x in the multiplicative group (mod N). The method succeeds because factorization can be reduced to finding the order of an element using randomization. But the algorithm has two shortcomings, the order of the number must be even and the output might be a trivial factor. Actually, these drawbacks can be overcome in a particular case, i.e., N is an RSA modulus. In this paper, we propose a new quantum algorithm for factoring RSA modulus without the two drawbacks. Moreover, we show that the cost of the algorithm mainly depends on the calculation of ord(N) (2). (c) 2006 Elsevier Inc. All rights reserved.
关键词	Shor's quantum algorithm RSA modulus repunit
DOI	10.1016/j.ic.2006.04.003
语种	英语
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Theory & Methods ; Mathematics, Applied
WOS记录号	WOS:000238782700006
出版者	ACADEMIC PRESS INC ELSEVIER SCIENCE
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/2825
专题	中国科学院数学与系统科学研究院
通讯作者	Cao, ZJ
作者单位	1.Shanghai Univ, Dept Math, Shanghai, Peoples R China 2.Chinese Acad Sci, Key Lab Math Mechanizat, Acad Math & Syst Sci, Beijing 100080, Peoples R China 3.Shanghai Jiao Tong Univ, Dept Math, Shanghai 200030, Peoples R China
推荐引用方式 GB/T 7714	Liu, LH,Cao, ZJ. On computing ord(N)(2) and its application[J]. INFORMATION AND COMPUTATION,2006,204(7):1173-1178.
APA	Liu, LH,&Cao, ZJ.(2006).On computing ord(N)(2) and its application.INFORMATION AND COMPUTATION,204(7),1173-1178.
MLA	Liu, LH,et al."On computing ord(N)(2) and its application".INFORMATION AND COMPUTATION 204.7(2006):1173-1178.