Rth Root Extraction In Finite Fields And A Heuristic Description Of FFT

This dissertation includes two parts. The first part focuses on the rth root ex-traction over Finite Field. In the second, we introduce a heuristic description of Fast Fourier Transform (FFT).In1977, Adleman, Manders and Miller had proposed a novel method to solve the quadratic residuosity problem. In their paper, they had mentioned that there was a way to extend their novel square root extraction method to the general rth root extraction over finite fields. Their extension, however, is lack of detailed proofs and corresponding complexity analysis. We have found that the process of extension from the square root extraction to the rth root extraction is not as smooth as they originally imagined. In fact, the intractable discrete logarithm problem would appear during the process. Moreover, there are some gaps to be filled when we apply the method to rth root extraction. In this paper, we will give an explicit description of the popular method and analyze its complexity in detail.In2006, Barreto and Voloch proposed a new algorithm to compute rth roots in Fqm for certain choices of m and q. If r‖q-1and (m,r)=1, they proved that the complexity of their method is O(r(log m+log log q)m log q). We shall extend the Barreto-Voloch algorithm to the general case that r‖qm-1, without the restrictions r‖q-1and (m,r)=1. We also specify the conditions that the Barreto-Voloch algorithm can be preferably applied.Currently, there exist two classical descriptions of Fast Fourier Transform (FFT). One is recursive, which is too vague to specify the working flow although it is very concise. The other is iterative, which is precise but barely reveal elegant designing ideas behind the algorithm. In the second part of this paper, we combine the merits of these two descriptions and introduce a new heuristic description of FFT, which graphically illustrates the designing ideas behind FFT.