Classical and Quantum Algorithms for Exponential Congruences
| dc.creator | van Dam, Wim | |
| dc.creator | Shparlinski, Igor E. | |
| dc.date | 2008-04-07 | |
| dc.date.accessioned | 2026-07-07T09:30:51Z | |
| dc.date.available | 2026-07-07T09:30:51Z | |
| dc.description | We discuss classical and quantum algorithms for solvability testing and finding integer solutions x,y of equations of the form af^x + bg^y = c over finite fields GF(q). A quantum algorithm with time complexity q^(3/8) (log q)^O(1) is presented. While still superpolynomial in log q, this quantum algorithm is significantly faster than the best known classical algorithm, which has time complexity q^(9/8) (log q)^O(1). Thus it gives an example of a natural problem where quantum algorithms provide about a cubic speed-up over classical ones. | |
| dc.description | 12 pages | |
| dc.identifier | https://arxiv.org/abs/0804.1109 | |
| dc.identifier | http://arxiv.org/abs/0804.1109 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/158259 | |
| dc.subject | Quantum Physics | |
| dc.title | Classical and Quantum Algorithms for Exponential Congruences | |
| dc.type | text |