Classical and Quantum Algorithms for Exponential Congruences

Details Classical and Quantum Algorithms for Exponential Congruences Classical and Quantum Algorithms for Exponential Congruences

2008-04-07

arxiv.org/abs/0804.1109v1

Physics

Quantum Physics

12 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Classical and Quantum Algorithms for Exponential Congruences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Classical and Quantum Algorithms for Exponential Congruences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Classical and Quantum Algorithms for Exponential Congruences will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-729991