Fast Computation of the Biquadratic Residue Symbol Original Research Article

This article describes an asymptotically fast algorithm for the computation of the biquadratic residue symbol. The algorithm achieves a running time of O(n(log n)2log log n) for Gaussian integers bounded by 2n in the norm. Our algorithm is related to an asymptotically fast GCD computation in image[i] which uses the technique of a controlled Euclidean descent in image[i]. At first, we calculate a Euclidean descent with suitable Euclidean steps xj−1=qjxj+xj+1 storing the qjʹs for later use. Then we calculate the biquadratic residue symbol of x0, x1 from the quotient sequence in linear time in the length of the qjʹs.