# how to get number of possible public keys in RSA

I need to calculate the number of possible public keys.

The tuple for the public key is defined as: $Key_{Publ} = (n,a)$

So: Let $p:=83$ and $q:=163$

$n= p \cdot q = 83 \cdot 163 = 13529$

$\phi(n) = (p -1 )(q - 1) =(83 - 1)(163 - 1) = 13284$

Question: How is it possible to calculate the number of possible $a$'s in $\gcd(a , \phi(n))$ with $a \in [1, \phi(n)]$ ? So I will be able to calculate the possibilities with $n \cdot a$?

I have two possible ways to calculate $\phi(n):$ $$\phi(n)=(p-1)(q-1)$$ $$\phi(n)=\prod_{p \in \mathbb P}(p^{v_p(n)-1}(p-1))$$

I appreciate every hint.

• I don't understand the Question. Can you either clarify or check you have set it down correctly? Jan 15, 2017 at 22:03

$\phi(\phi(n))$ is the number of possible keys
• can you show an example how you would calculate that with the numbers $p:=83$ and $q=163$, please? Jan 30, 2017 at 22:39
• i believe in your exercise there is a Form how to calculate $\phi(n)$ Jan 30, 2017 at 22:41
• and then ? $phi(13284)=?$ That is not clear to me Jan 30, 2017 at 22:42
• exactly , now that you have 13428 = $2^{2} 3^{4} 41$ you can now find $\phi(13428)$ =$2^{(2-1)}*(2-1)*3^{(4-1)}*(3-1)*41^{(1-1)}*(41-1) = 2*3^{3}*2*40 = 4320$ Jan 30, 2017 at 23:01
• p is Prime number so in our care is 2 or 3 or 41 $v_{p}(n)$ is like $v_{2}(13284) =2$ and $v_{3}(13284) =4$ and $v_{41}(13284)=1$ Jan 30, 2017 at 23:06