𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Fast Computation of the Biquadratic Residue Symbol

✍ Scribed by André Weilert

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
189 KB
Volume
96
Category
Article
ISSN
0022-314X

No coin nor oath required. For personal study only.

✦ Synopsis

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 n 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. # 2002 Elsevier Science (USA)

📜 SIMILAR VOLUMES

Fast Computation of the Bezout and Dixon
Fast Computation of the Bezout and Dixon Resultant Matrices
✍ Eng-Wee Chionh; Ming Zhang; Ronald N. Goldman 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 264 KB

Efficient algorithms are derived for computing the entries of the Bezout resultant matrix for two univariate polynomials of degree n and for calculating the entries of the Dixon-Cayley resultant matrix for three bivariate polynomials of bidegree (m, n). Standard methods based on explicit formulas re

A Preliminary Study of the Burgers Equat
A Preliminary Study of the Burgers Equation with Symbolic Computation
✍ Russell G. Derickson; Roger A. Pielke Sr. 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 204 KB

A novel approach based on recursive symbolic computation is introduced for the approximate analytic solution of the Burgers equation. Once obtained, appropriate numerical values can be inserted into the symbolic solution to explore parametric variations. The solution is valid for both inviscid and v