|
| << vorige | volgende >> |
Tijdschrift beschrijving
Alle jaargangen van het bijbehorende tijdschrift
Alle afleveringen van het bijbehorende jaargang
Alle artikelen van de bijbehorende aflevering
Details van artikel 7 van 12 gevonden artikelen
| Titel: |
On the Optimality of the Binary Algorithm for the Jacobi Symbol |
| Auteur: |
Busch, J. |
| Verschenen in: |
Fundamenta informaticae |
| Paginering: | Jaargang 76 (2007) nr. 1-2 pagina's 1-11 |
| Jaar: |
2007-03-06 |
| Inhoud: |
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). |
| Uitgever: |
IOS Press |
| Bronbestand: |
Elektronische Wetenschappelijke Tijdschriften |
Details van artikel 7 van 12 gevonden artikelen
| << vorige | volgende >> |