𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A symbolic algorithm for the automatic computation of

✍ Scribed by D. Akgün; İ. Çankaya; J. C. Peyton Jones

Publisher
Springer Netherlands
Year
2008
Tongue
English
Weight
593 KB
Volume
56
Category
Article
ISSN
0924-090X

No coin nor oath required. For personal study only.

📜 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 of three algorithms fo
On the worst case of three algorithms for computing the Jacobi symbol
✍ Jeffrey Shallit 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 803 KB

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 = 2