On the worst case of three algorithms for computing the Jacobi symbol (Q752075): Difference between revisions
From MaRDI portal
Latest revision as of 10:08, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the worst case of three algorithms for computing the Jacobi symbol |
scientific article |
Statements
On the worst case of three algorithms for computing the Jacobi symbol (English)
0 references
1990
0 references
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.
0 references
computation of the Jacobi symbol
0 references
algorithm
0 references