|
| << previous | next >> |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 7 of 12 found articles
| Title: |
On the Optimality of the Binary Algorithm for the Jacobi Symbol |
| Author: |
Busch, J. |
| Appeared in: |
Fundamenta informaticae |
| Paging: | Volume 76 (2007) nr. 1-2 pages 1-11 |
| Year: |
2007-03-06 |
| Contents: |
We establish lower bounds on the complexity of computing the following number-theoretic functions and relations from piecewise linear primitives: (i) the Legendre and Jacobi symbols, (ii) pseudoprimality, and (iii) modular exponentiation. As a corollary to the lower bound obtained for (i), an algorithm of Shallit and Sorenson is optimal (up to a multiplicative constant). |
| Publisher: |
IOS Press |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 7 of 12 found articles
| << previous | next >> |