On the worst case of three algorithms for computing the Jacobi symbol
type: Item
instance of: scholarly article
title: On the worst case of three algorithms for computing the Jacobi symbol
zbMATH Open document ID: 0715.11072
DOI: 10.1016/S0747-7171(08)80160-5
published in: Journal of Symbolic Computation
publication date: 1990-01-01T00:00:00Z
review text: The author considers the worst case computation of the Jacobi symbol \((\frac{u}{v})\) by analogues of the Euclidean algorithm. One can insist on even quotients (Eisenstein), least remainders (Lebesgue), or the ordinary algorithm, (reducing even factors as they occur). For the first type the worst case is \(u=2n+1\), \(v=2n-1\), for the second and third types of the worst cases generate fascinating quadratic and sextic recurrences. The logarithmic character of the algorithm is easily upheld.
reviewed by: Harvey Cohn
Mathematics Subject Classification ID: 11Y16
Mathematics Subject Classification ID: 11A15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4177213
zbMATH Keywords: computation of the Jacobi symbol
zbMATH Keywords: algorithm
author: Jeffrey Shallit
MaRDI profile type: Publication
cites work: The Jacobi symbol algorithm
cites work: Q5612611
cites work: Q5613266
cites work: Q5585020
cites work: Q4145769
cites work: Q3832627
cites work: On a theorem of Heilbronn
cites work: Q4105726
cites work: Über die mittlere Schrittanzahl bei Divisionsalgorithmen
cites work: Über die Schrittanzahl beim Algorithmus von Harris und dem nach nächsten Ganzen
cites work: Q3949129
cites work: Prime numbers and computer methods for factorization
cites work: Q3337526
cites work: Fast computation of continued fraction expansions.
cites work: Erratum: A Fast Monte-Carlo Test for Primality
cites work: Computational problems associated with Racah algebra
cites work: A modification of the RSA public-key encryption procedure (Corresp.)
full work available at URL: s0747-7171(08)80160-5
OpenAlex ID: W1967135503
description: scientific article; zbMATH DE number 4177213