0

I'm trying to follow this proof about RSA

n is the product of two distinct primes. $ e * d$ mod $\phi(n)$ = 1 with $ e,d \in \Bbb{N}$

In the last line how does $(x^{ed} - x) $mod n $= 0$ simplify to $((x^e)^d) $mod $n = x$

from script (also meaning it follows in this context) enter image description here

CuriousIndeed
  • 439
  • Do you know Euler's Theorem ?. if yes try to apply it. – hamam_Abdallah May 09 '21 at 00:09
  • exponents, multiplication, addition, and substraction are preserved over modular arithmetic. So $x^{ed} - x \equiv 0 \pmod n \implies (x^e)^d \equiv x \pmod n$ for the exact same reasons $x^{ed}-x = 0\implies (x^e)^d = x$. – fleablood May 09 '21 at 00:47
  • Yes but the conclusion is (x^ed -x) mod n = 0 <=> x^ed mod n - x mod n = 0 <=> x^ed mod n = x mod n which is not the same as x^ed mod n = x... – CuriousIndeed May 09 '21 at 23:33

1 Answers1

1

$$x^{ed}-x \equiv 0 \pmod n\\ x^{ed} \equiv x \pmod n\\ (x^e)^d \equiv x \pmod n$$ The second line adds $x$ to each side, the third is by a property of exponents.

Ross Millikan
  • 374,822
  • In my script it states x^ed mod n = x (without mod n on this side) – CuriousIndeed May 09 '21 at 00:50
  • It is using $\bmod n$ as an operation, returning the remainder on division by $n$. That is a computer science way to write it because they have an operator, often written with the percent sign. In math we talk of equivalence modulo $n$. In most cases, including this one, they are equivalent. – Ross Millikan May 09 '21 at 01:03
  • I'm sorry I can't follow the reasoning..(x^ed -x) mod n = 0 <=> x^ed mod n - x mod n = 0 <=> x^ed mod n = x mod n which is not the same as x^ed mod n = x – CuriousIndeed May 09 '21 at 23:35
  • 1
    I gave the reasons in the answer. As long as $x \lt n$ they are equivalent. – Ross Millikan May 10 '21 at 02:20