I was going through the diffe-hellman algorithm in cryptography . So the algorithm apart the mathematicality it hinges on is as follows :

If $ p $ is a prime number and $ g $ is another integer and $ a$ and $b$ are two integers then

($ g^a $ $mod p )^b$ $mod $ $p $ = ($ g^b $ $mod p )^a$ $mod $ $p $ ------$A$

I got the proof of it but before going through its proof I tried along the following lines :

let $g^a$ be $k_1$$p$ + $r_1$ where $r_1$ < $p$ and $g^b$ be $k_2$$p$ + $r_2$ where $r_2$ < $p$

so $g^a$ $mod$ $p$ = $r_1^a$ $mod$ $p$

and $g^b$ $mod$ $p$ = $r_2^a$ $mod$ $p$

Now similarly :

$(g^a$ $mod$ $p$)$^b$ $ mod p $ is ($r_1^a$)$^b$)$mod$$p$

and $(g^b$ $mod$ $p$)$^a$ $ mod p $ is ($r_2^a$)$^b$)$mod$$p$

If $A$ is true then that means ($r_1^a$)$^b$)$mod$$p$ should be equal to ($r_2^a$)$^b$)$mod$$p$ which of course is not true given the random choice of $a$ and $b$ .

I think I had made a mistake somewhere while moving along these lines . Where is it that I erred ?

As TonyK points out the mistake was the following :

$g^a$ $mod$ $p$ = $r_1^a$ $mod$ $p$

It should have been $g^a$ $mod$ $p$ = $r_1$ $mod$ $p$ .

So with this correction :

$(g^a$ $mod$ $p$)$^b$ $ mod p $ is ($r_1$)$^b$)$mod$$p$


$(g^b$ $mod$ $p$)$^a$ $ mod p $ is ($r_2$)$^a$)$mod$$p$ .

How to reason out ($r_1$)$^b$) being equal to ($r_2$)$^a$) ?

  • $\begingroup$ Typesetting tip: use g \bmod p ($g \bmod p$) instead of g mod p ($g mod p$). $\endgroup$ – Rahul Jun 25 '19 at 6:25

Here is your (first) mistake:

so $g^a \bmod p = r_1^a\bmod p$

This should be

so $g^a \bmod p = r_1\bmod p$

  • $\begingroup$ But in general , if $a$ $ \congr $ $b mod p$ then $a$ can be expressed as $ kp + b $ for some integer k , so $ a^n$ is $(kp+b)^n$ which on expansion yields an expression which contains powers of $p$ in all terms + $ b ^n$ , so $a^n$ - $b^n$ is divisible by $p$ . Isn't it so ? $\endgroup$ – Erwin Kairos Jun 25 '19 at 5:55
  • $\begingroup$ Found the mistake ... Editing it $\endgroup$ – Erwin Kairos Jun 25 '19 at 6:00

How to reason out $r_1^b$ being equal to $r_2^a$ ?

Both are equal to $g^{ab}\bmod p$. Easy!

  • $\begingroup$ Thanks a lot. Don't know what made me miss this $\endgroup$ – Erwin Kairos Jun 27 '19 at 2:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.