Wuhan University Journal of Natural Sciences
On Computing a for Order ( a, n ) and Its Application
Peng LI, Yue Wang, Xinxia WANG, Huanguo Zhang
Abstract
The order [see formula in PDF] of an element [see formula in PDF] in the multiplicative group [see formula in PDF], denoted by [see formula in PDF], or [see formula in PDF] for short, plays a significant role in the period of certain pseudo-random number generators and is particularly important in Shor's quantum integer factorization algorithm, as well as in various cryptographic applications. In this paper, we present some numerical results and evidence of suitable [see formula in PDF] for which [see formula in PDF] are small and relatively easy to obtain, in the light of quantum integer factorization. The results indicate that the higher the order, the larger of the number of [see formula in PDF]. Therefore, we propose a quantum algorithm for finding [see formula in PDF] in [see formula in PDF] with [see formula in PDF], explicitly excluding the trivial solution [see formula in PDF], based on Grover's search, but using fewer quantum bits. Moreover, the proposed algorithm achieves a success probability close to 1. As this type of [see formula in PDF] is commonly used as an RSA modulus, once such an [see formula in PDF] is found, RSA cryptographic system will be broken.