Fast computation of the biquadratic residue symbol

JOURNAL OF NUMBER THEORY

卷:96

Article

Weilert, A

关键词: GCD calculation;    Euclidean algorithm;    reciprocity law;    power residue symbol;    biquadratic residue symbol;    Jacobi symbol;   

DOI  :  10.1006/jnth.2002.2783

来源: Elsevier

【 摘 要 】

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)(2)log log n) for Gaussian integers bounded by 2 in the norm. Our algorithm is related to an asymptotically fast GCD computation in Z[i] which uses the technique of a controlled Euclidean descent in Z[i]. At first, we calculate a Euclidean descent with suitable Euclidean steps x(j-1) = q(j)x(j) + x(j+1) storing the q(j)'s for later use. Then we calculate the biquadratic residue symbol of x(0), x(1) from the quotient sequence in linear time in the length of the q(j)'s. (C) 2002 Elsevier Science (USA).

【 授权许可】

Free