I am trying to dig as deep as I can into the RSA algorithm and trying to wrap my head around why the public key and it’s mod inverse have to be less than $\varphi(n)$. $\varphi(n)$ is the number of numbers that are co prime with $n$ right ? And not the actual number that is coprime. How is picking numbers less than $\varphi(n)$ helping ?
Asked
Active
Viewed 47 times
0
-
1Because $$(a^{\phi (n)} \bmod n)=1,,\quad \gcd(a,n)=1$$ see here. – Steven Clark Oct 15 '23 at 22:35
-
$\varphi(n)$ is the number of numbers that are co prime with $n$ right ? No, there are infinitely many numbers which are coprime to any given number $n$. :) – Nothing special Oct 15 '23 at 22:35
-
1Ok, then it’s the number of numbers that are coprime with n and less than n – user993797 Oct 15 '23 at 23:01