On the worst case of three algorithms for computing the Jacobi symbol (Q752075): Difference between revisions

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.