Having trouble with understand the following derived equation by Euler Theorem..

45 Views Asked by At

We have the following equations $$\begin{align} d_p=&\ d\mod{(p-1)}\tag5 \\ d_q=&\ d\mod{(q-1)}\tag 6 \\ x_p=&\ y^{d_p}\mod p\tag 7 \\ x_q=&\ y^{d_q}\mod q\tag 8 \\ x=&\ M_pqx_p+M_qpx_q\mod n\tag 9 \end{align} $$ Combining (5) and (7) gives $$x_p=y^{d\mod{(p-1)}}\mod p\tag{10}$$ Since $p$ is prime, $\phi(p)=p-1$. According to Euler's theorem, if $\gcd(a,p)=1$, then $a^{p-1}\equiv 1\pmod p$, which implies $$y^d=y^{\lfloor d/(p-1)\rfloor(p-1)+d\mod{(p-1)}}\equiv y^{d\mod{(p-1)}}\pmod p\tag{11}$$

I am having trouble with how the equation (11) is derived.

1

There are 1 best solutions below

0
On BEST ANSWER

The exponent of the middle expression

$\lfloor d/(p-1)\rfloor (p-1)+d\mod(p-1)$

is expressing $d$ as an integer multiple of $(p-1)$ plus its remainder. The significance of this is that, by Euler's Theorem, $y^{p-1}\cong 1\mod p$, hence, using exponent rules, we have that:

$y^{\lfloor d/(p-1)\rfloor (p-1)+d\mod p}$

$=y^{\lfloor d/(p-1)\rfloor (p-1)}\cdot y^{d\mod (p-1)}$

$=(y^{(p-1)})^{\lfloor d/(p-1)\rfloor}\cdot y^{d\mod (p-1)}$

$\cong 1^{\lfloor d/(p-1)\rfloor}\cdot y^{d\mod (p-1)}\mod p$

$=1\cdot y^{d\mod (p-1)}\mod p$

$=y^{d\mod (p-1)}\mod p$