Take the 2-minute tour ×
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.

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|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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.