Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is computing $g^{xy} \bmod{s}$ from $g^{x} \bmod{s}$ and $g^{y} \bmod{s}$ easier harder or the same level of difficulty as computing

$g\uparrow\uparrow(xy) \bmod s$ from from $g\uparrow\uparrow x$ and $g\uparrow \uparrow y$. Here $\uparrow\uparrow$ denotes tetration or repeated exponentiation, for example $5\uparrow\uparrow 3 = 5^{5^5}$

Is solving this tetration problem in BQP?

share|cite|improve this question
Just a note: What you are talking about is the (computational) Diffie-Hellman problem, and not the discrete logarithm problem. And why are you interested in these tetrations? They are not very efficient for cryptographic purposes. – TMM Apr 19 '13 at 20:19
How do you know we can compute $g\uparrow\uparrow (xy) \mod s$ from $g\uparrow\uparrow x \mod s$ and $g\uparrow\uparrow y \mod s$? – Alexander Gruber Apr 19 '13 at 20:21
I don't know whether it can be solved and also my curiosity comes from the fact that diffie Hellman is known to be in BQP, meaning a sufficiently large quantum computer, should they be made, can solve this fairly easily. Is tetration easily solvable? – frogeyedpeas Apr 19 '13 at 20:25
No other takes on this one? – frogeyedpeas Apr 20 '13 at 23:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.