@inproceedings{b89f4daf2caa456a96eb8278993e28fa,

title = "Classical and quantum algorithms for exponential congruences",

abstract = "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 . A quantum algorithm with time complexity q 3/8 (logq) O(1) is presented. While still superpolynomial in logq, this quantum algorithm is significantly faster than the best known classical algorithm, which has time complexity q 9/8 (logq) O(1). Thus it gives an example of a natural problem where quantum algorithms provide about a cubic speed-up over classical ones.",

author = "{Van Dam}, Wim and Shparlinski, {Igor E.}",

year = "2008",

doi = "10.1007/978-3-540-89304-2_1",

language = "English",

isbn = "9783540893035",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Springer Nature",

pages = "1--10",

editor = "Yasuhito Kawano and Michele Mosca",

booktitle = "Theory of Quantum Computation, Communication, and Cryptography",

address = "United States",

note = "3rd Workshop on Theory of Quantum Computation, Communication, and Cryptography, TQC 2008 ; Conference date: 30-01-2008 Through 01-02-2008",

}