An exact version of Shor's order finding algorithm and its application to primitive finding problem

We present an efficient exact version of Shor's order finding algorithm when a multiple m of the order r is known. The algorithm consists of two main ingredients. The first ingredient is the exact quantum Fourier transform proposed by Mosca and Zalka. The second ingredient is an amplitude amplification version of Brassard and Hoyer combined with some ideas from the exact discrete logarithm procedure by Mosca and Zalka. As an application, we show how the algorithm serves as a subroutine of an efficient exact quantum algorithm for finding primitive elements in arbitrary finite fields.