1

I would like to calculate $d^{1/x} \bmod n$ where $d$ and $x$ belong to $\Bbb Z_n$. Here $x$ is greater than one, thus $1/x$ is less than one. How can I do a computation like that? For example what is the result of

$$5^{0,23} \bmod 4?$$

(In fact I am trying to implement this in the language PHP, but this is not important.)

Thanks again.

TMM
  • 9,976
  • 1
    In modular arithmetic, $1/x$ usually does not correspond to dividing $1$ by $x$ in the "real" sense, but by computing the inverse of $x$ in the relevant field. – TMM May 10 '13 at 15:17
  • @TMM Thank you. I will try it now, and I will tell you if I can do this works. Thanks again –  May 10 '13 at 15:21
  • 1
    Your example doesn't fit your question, since $0.23$ is not of the form $1/x$. Also, in $\mathbb Z_n$, it is not generally true that $a^{m}=a^{m+n}$, so there is really no point in thinking of the exponent as being in $\mathbb Z_n$. – Thomas Andrews May 10 '13 at 15:23
  • @TMM Thank you very much. I was (and am) a little confused. If I have (100 ^ 121) mod 257 then ((100 ^ 121) mod 257) ^ (1/121) mod 257 than the result of the second equation is equal to 100? –  May 10 '13 at 16:26
  • @Andres: Yes. Note that $(a^x)^y = a^{xy}$, so $(a^x)^{1/x} = a^{x/x} = a^1 = a$. You should not compute $1/121 = 0.00826\ldots$ as that is irrelevant. – TMM May 10 '13 at 16:29
  • @TMM Thank you. However, when I try to do the equation above at the website http://ptrow.com/perl/calculator.pl it gives me 141 as final result instead of 100. The same does the program I have written as well (141 too!). I do not know what I am doing wrong... –  May 10 '13 at 16:32
  • @TMM Thanks a lot. I haven't found however any solution at my specific problem, if you want to take a look http://math.stackexchange.com/questions/387827/modulo-in-e-voting-paper-is-wrong . I do not have enough reputation yet to upvote your answer. If I get some, I'll upvote it for sure. :) –  May 10 '13 at 18:17

1 Answers1

0

As @TMM said, $\frac 1 x$ should be equal to $x^{-1}$ for some $x\in \mathbb{Z}_n$ in modular arithmetic. You can compute the inverse element in $\mathbb{Z}_n$, if $(x,n) = 1$, using the extended Euclid algorithm. If you find $(a, b)$, so that $ax+bn = 1$, then $ax = 1 (mod~n)$, $a = x^{-1}$.

gukoff
  • 1,500
  • Thank you very much. I was (and am) a little confused. If I have (100 ^ 121) mod 257 then ((100 ^ 121) mod 257) ^ (1/121) mod 257 than the result of the second equation is equal to 100? –  May 10 '13 at 16:19
  • $121^{-1} = 17 (mod 257)$, so $(100^{121})^{\frac {1}{121}} = (100^{121})^{17} = 100^{121\cdot 17} = 141 (mod~257)$ – gukoff May 10 '13 at 16:46
  • This isn't the root. The problem of getting the root is much harder. – gukoff May 10 '13 at 16:51
  • Thank you. However that's kind of strange... If I have the number 100 and the number 257 is my modulo number, then how I can choose the powers, in order to get number 100 bavk, when I apply these two powers? –  May 10 '13 at 16:52
  • You can use the Euler's criterion. Just note that $a^{256}=1~(mod~257)$ for any $a$, so $100^{256\cdot C+1}=100^{1} (mod~257)$ for any $C$. – gukoff May 10 '13 at 17:08
  • Thanks a lot. I haven't found however any solution at my specific problem, if you want to take a look http://math.stackexchange.com/questions/387827/modulo-in-e-voting-paper-is-wrong . I do not have enough reputation yet to upvote your answer. If I get some, I'll upvote it for sure. :) –  May 10 '13 at 18:16