𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the worst case of three algorithms for computing the Jacobi symbol

✍ Scribed by Jeffrey Shallit

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
803 KB
Volume
10
Category
Article
ISSN
0747-7171

No coin nor oath required. For personal study only.

✦ Synopsis

We study the worst-case behavior of three iterative algorithms for computing the Jacobi symbol (~). Each algorithm is similar in format to the Euclidean algorithm for computing gcd(u, v).

Eisenstein's algorithm chooses an even quotient at each step. It is shown that the worst case occurs when u = 2n + 1, v = 2n -1.

Lebesgue's algorithm is essentially the least-remainder Euclidean algorithm with powers of 2 removed at each step.

πŸ“œ SIMILAR VOLUMES

Efficient Algorithms for Computing the J
Efficient Algorithms for Computing the Jacobi Symbol
✍ S.M. Eikenberry; J.P. Sorenson πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 464 KB

We present two new algorithms for computing the Jacobi Symbol: the right-shift and left-shift k-ary algorithms. For inputs of at most n bits in length, both algorithms take O(n 2 / log n) time and O(n) space. This is asymptotically faster than the traditional algorithm, which is based in Euclid's al

On the worst-case divergence of the leas
On the worst-case divergence of the least-squares algorithm
✍ HΓΌseyin AkΓ§ay; Brett Ninness πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 371 KB

In this paper, we provide a ~-norm lower bound on the worst-case identification error of least-squares estimation when using FIR model structures. This bound increases as a logarithmic function of model complexity and is valid for a wide class of inputs characterized as being quasi-stationary with c