✦ LIBER ✦

Efficient Algorithms for Computing the Jacobi Symbol

✍ Scribed by S.M. Eikenberry; J.P. Sorenson

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 464 KB
Volume: 26
Category: Article
ISSN: 0747-7171
DOI: 10.1006/jsco.1998.0226

No coin nor oath required. For personal study only.

✦ Synopsis

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 algorithm for computing greatest common divisors. In practice, we found our new algorithms to be about twice as fast for inputs of 100 to 1000 decimal digits in length. We also present parallel versions of both algorithms for the CRCW PRAM. One version takes O (n/ log log n) time using O(n 1+ ) processors, giving the first sublinear parallel algorithms for this problem. The other version takes polylog time using a subexponential number of processors.

📜 SIMILAR VOLUMES

A Parallel Ring Ordering Algorithm for E

A Parallel Ring Ordering Algorithm for Efficient One-Sided Jacobi SVD Computations

✍ B.B. Zhou; R.P. Brent 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 141 KB

In this paper we give evidence to show that in one-sided Jacobi SVD computation the sorting of column norms in each sweep is very important. An efficient parallel ring Jacobi ordering for computing singular value decomposition is described. This ordering can generate n(n -1)/2 different index pairs

An Algorithm for Computing the Integral

An Algorithm for Computing the Integral Closure

✍ Theo de Jong 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 267 KB

A new adaptive backstepping control algo

A new adaptive backstepping control algorithm for motion control systems — an implicit and symbolic computation approach

✍ Jen-te Yu; Jie Chang 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 169 KB 👁 2 views

The computational algorithm for the para

The computational algorithm for the parametric objective function

✍ Saul Gass; Thomas Saaty 📂 Article 📅 1955 🏛 John Wiley and Sons 🌐 English ⚖ 307 KB

Yet more image computations for SMV, the

Yet more image computations for SMV, the symbolic model verifier

✍ Hiromi Hiraishi 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB

This paper describes a collection of techniques to improve the efficiency of the pre-and postimage computations that are the core of the Symbolic Model Verifier (SMV), which is used for formal logic design verification. The proposed techniques aim mostly at improving the efficiency of the verificati

An efficient algorithm for computing the

An efficient algorithm for computing the transmission through highly conducting thin sheild in TLM

✍ Ch. Fuchs; G. Kopp; A. J. Schwab 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 489 KB

## Abstract This paper presents a new method in TLM for very efficient computation of highly conducting thin shielding walls. Firstly, the impulse response of a finite conducting sheet is computed analytically via inverse Laplace transform. Subsequently, a recursive convolution integral is formulat