# Modulo in e-voting paper is wrong?

I am trying to run in my mind the registration phase that exists in the paper: Internet Voting Protocol Based on Improved Implicit Security (pdf).

I have chosen as parameters the following:

• the prime $p = 257$
• the primitive root $g = 233$
• the exponent $c = 200$
• the private key $x = 121$
• the random id $r_{id} = 100$
• the blinding factor $b = 123$.

Can anyone make it work? Use the numbers you want (if you prefer not to use mine), but lines 5, 6 that result to 7 do not work for me. I am trying to find if I am doing something wrong for over $8$ hours today... in an algorithm of just $7$ lines. There is also an online modulo calculator here if you want a tool to use.

Just a note. I think that at the bullet 4(b) it should be $u^x$ instead of $u$.

I will appreciate it a lot, if anybody could help me.

-
What exactly is the problem? First, one party computes $d = (r_{id}^x g^x)^c$ and then the other party computes $e = d^{1/x}$. What are the numbers you get for $d$ and $e$? – TMM May 10 '13 at 18:26
In your example, you should get $d \equiv (100^{121} \cdot 233^{121})^{200} \equiv 17$ and $e \equiv 17^{1/121} \equiv 15$, which is equal to $(r_{id} \cdot g)^c \equiv (100 \cdot 233)^{200} \equiv 15$. – TMM May 10 '13 at 18:31
I get d= 17 and e = 240... – Jasmin May 10 '13 at 18:37
@TMM thank you. I'll find what I am doing wrong now – Jasmin May 10 '13 at 18:38
@TMM I can not understand why 17^1/121 is 15. Isn't it the same with 17^17 which makes 240? – Jasmin May 10 '13 at 18:43

You computed $d \equiv 17$ and $e \equiv 17^{1/121} \equiv 240$, while the result should be $e \equiv 17^{1/121} \equiv 15$. What goes wrong here is that you computed $1/121$ modulo $p$, instead of $1/121$ modulo $p - 1$.
• Modulo $p = 257$ we have $$1/121 \equiv 17 \mod{257}$$ and thus you get a wrong answer: $$17^{1/121} \stackrel{?}{\equiv} 17^{17} \equiv 240 \mod{257}.$$
• But modulo $\phi(p) = 256$ we have $$1/121 \equiv 201 \mod{256}$$ and you get the correct answer: $$17^{1/121} \equiv 17^{201} \equiv 15 \mod{257}.$$
A rule of thumb to remember is that in the exponent, you have to do computations modulo $p - 1$ instead of modulo $p$. This is somewhat directly a consequence of Fermat's Little Theorem, which says that $a^{p} \equiv a$, i.e., $a^{p-1} \equiv a^0 \equiv 1$ for $a \neq 0$. So in the exponent, $p - 1 \equiv 0$ rather than $p \equiv 0$.